Bisakah setiap algoritma modifikasi diri dimodelkan oleh algoritma non-selfmodifying?

Jika kita memiliki program komputer sewenang-wenang yang dapat memodifikasi instruksinya, apakah mungkin untuk mensimulasikan program itu dengan program yang tidak dapat memodifikasi instruksinya?

Edit:

Saya baru mengenal stackexchange jadi tidak yakin apakah saya diperbolehkan mengajukan pertanyaan BARU di sini, tapi begini: Ok jadi buktinya mungkin sebenarnya sebenarnya sangat sederhana seperti yang kalian tunjukkan. Sekarang, saya bertanya-tanya: Apakah ada masalah yang lebih efisien (dan sampai sejauh mana) untuk menggunakan algoritma pengubah-sendiri yang paling efisien untuk menyelesaikan masalah, versus algoritma non-self-termodifikasi yang setara dengan input-output yang paling efisien?

computability computation-models turing-completeness church-turing-thesis pengguna56834
sumber

Jawaban:

Iya itu mungkin. Anda dapat mensimulasikan program dengan menggunakan penerjemah untuk bahasa yang ditulisnya. Sekarang, program (penerjemah) sudah diperbaiki dan yang dulunya merupakan program modifikasi diri sekarang adalah data penerjemah.

Secara khusus, Anda dapat memiliki mesin Turing universal yang memungkinkan TM yang disimulasikan untuk memodifikasi deskripsi sendiri. (Deskripsi mesin yang disimulasikan, maksud saya; bukan UTM.)

David Richerby
sumber

Anda bahkan tidak memerlukan juru bahasa hipotetis. CPU yang menjalankan algoritme modifikasi-diri Anda sendiri merupakan mesin yang menjalankan algoritme tetap (yang menentukan bagaimana ia menjalankan instruksi)

Alexander - Reinstate Monica

@AlexanderMomchliov ada CPU yang dapat memodifikasi bagian dari instruksi mereka ditetapkan dengan cepat (tapi ya, idenya sama - bagian yang dapat diprogram adalah data, mikrokontroler yang menjalankannya adalah juru bahasa - meskipun menunjuk ke mikrokontroler di dalam sel FPGA mungkin rumit)

John Dvorak

untuk menanggapi: "Anda bisa memiliki mesin Turing universal yang memungkinkan TM yang disimulasikan untuk memodifikasi deskripsi sendiri." Saya berpikir: bukankah ini menimbulkan pertanyaan? karena sekarang Anda masih perlu membuktikan bahwa TM yang sedang disimulasikan sebenarnya dapat memodelkan algoritma modifikasi-diri, bukan? Mungkin masih ada kasus bahwa ada program modifikasi diri yang BUKAN itu sendiri mesin Turing, jadi kita tidak bisa menggunakan kelengkapan Turing untuk menunjukkan bahwa itu dapat disimulasikan, karena kelengkapan Turing berkaitan dengan simulasi TM dan modifikasi sendiri algo bukan TM.

user56834

@ Programmer2134 Tidak meminta pertanyaan sama sekali. Apa pun CPU yang Anda pikir Anda gunakan untuk menjalankan program modifikasi diri, saya dapat mensimulasikan CPU itu pada mesin Turing. Untuk menjelaskannya dengan cara yang berbeda, program awal adalah urutan instruksi yang terbatas, beberapa di antaranya terjadi memodifikasi program itu sendiri. Setiap instruksi dapat disimulasikan oleh UTM, masing-masing modifikasi dapat disimulasikan, dan masing-masing instruksi yang dimodifikasi dapat disimulasikan. Tidak ada, pada tahap proses ini, yang melampaui kekuatan mesin Turing.

David Richerby

Model komputasi Turing-complete yang tidak memiliki kode modifikasi (atau "kode") berfungsi sebagai bukti pernyataan itu. Aku tidak tahu bahwa salah satu model standar (TM, RAM, ...) jangan memiliki memodifikasi kode, jadi kita tidak perlu melihat terlalu jauh.

Untuk mendapatkan program dalam bahasa apa pun yang ada dalam pikiran Anda, kompilasi dari model seperti itu (dan pastikan bahwa kompiler tidak memperkenalkan modifikasi kode).

Hal ini, tentu saja, argumen eksistensial: ada adalah program setara. Tetapi kita juga tahu bahwa ada kompiler rekursif (yaitu komputable) antara dua bahasa Turing-complete, jadi itulah cara Anda mendapatkan program bentuk (baca: dalam bahasa) yang Anda inginkan.

Raphael
sumber

Untuk menambahkan jawaban David Richerby :

Jika memang benar bahwa tidak ada algoritma modifikasi diri tidak dapat dimodelkan oleh algoritma non-modifikasi diri, maka algoritma tersebut harus dijalankan pada sesuatu yang juga memodifikasi diri. Itu harus kura-kura sepanjang jalan.

Seperti yang saya sebutkan dalam komentar saya, algoritma modifikasi diri dapat dijalankan pada prosesor yang dengan sendirinya mematuhi aturan algoritma statis (yang dikodekan dalam desainnya) yang "memberi tahu" bagaimana cara menjalankan instruksi mesin.

Alexander - Pasang kembali Monica
sumber

Saya pikir itu mungkin garis pemisah yang menarik. Saya pikir orang bisa berpendapat bahwa "hidup" adalah algortihm pemodifikasi-sendiri yang tidak dapat dimodelkan oleh algoritma pemodifikasi-non-otomatis, tetapi sekali lagi, "kehidupan" biasanya tidak dianggap sebagai suatu algoritma.

Cort Ammon

@CortAmmon: Jika kita melihat "hidup" sebagai suatu algoritma, lalu apa input dan outputnya? Bagaimana seseorang dapat membuktikan bahwa algoritma apa pun yang setara (artinya, algoritma apa pun yang menghasilkan output yang sama ketika diberi input yang sama) harus memodifikasi sendiri?

ruakh

@ruakh Jika saya berpendapat bahwa hidup adalah algoritma modifikasi diri, input akan menjadi dirinya sendiri, dan outputnya akan menjadi dirinya sendiri. Membuktikan bahwa itu tidak dapat direduksi menjadi algoritma yang tidak memodifikasi sendiri akan lebih sulit, tapi saya pikir ini adalah hipotesis populer. Lagi pula, berapa banyak orang yang ingin percaya bahwa mereka dapat direduksi menjadi sebuah algoritma yang dapat berjalan di komputer?

Cort Ammon

@CortAmmon: Saya tidak dapat direduksi menjadi sebuah algoritma yang berjalan di komputer karena algoritma itu tidak lagi "saya"; Saya lebih dari input dan output saya. Tetapi jika kita mulai dari asumsi bahwa saya adalah hanya sebuah algoritma, maka penyambungan "yang dapat dijalankan pada komputer" tidak benar-benar perubahan apa-apa. Re: "Jika saya berpendapat bahwa hidup adalah algoritma modifikasi diri, input akan menjadi dirinya sendiri, dan outputnya akan menjadi dirinya sendiri": Dalam hal ini saya pikir Anda akan membelok jauh di luar CS, dan hampir mendekati crackpottery.

ruakh

@CortAmmon Program yang menampilkan dirinya sendiri hanya sebagai input cat. (Tidak ada permainan kata-kata yang dimaksudkan, meskipun kucing adalah makhluk hidup)

user253751