Ada beberapa gagasan yang berbeda (mungkin tidak setara) tentang universalitas komputasi (lihat misalnya beberapa halaman terakhir dari http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) dan tidak ada konsensus di antara ahli tentang gagasan mana yang paling benar (lihat misalnya http://cs.nyu.edu/pipermail/fom/2007-October/012148.html ).
Saya mencoba mengatakan sesuatu tentang model perhitungan biomolekuler tertentu. Saya ingin berpendapat bahwa ini "lebih universal" atau "lebih bermanfaat universal" daripada beberapa model lain, karena Anda dapat membangun mesin universal yang menjalankan program dan kemudian menghapus input pada akhirnya dan siap untuk menjalankan program lain. Bandingkan ini dengan, katakanlah, automata seluler, yang dapat meniru mesin Turing apa pun, tetapi kemudian pada akhir perhitungan, Anda memiliki konfigurasi final yang tidak dapat diubah. Untuk meniru TM lain, Anda perlu mendefinisikan CA yang benar-benar terpisah. Jadi saya ingin mengatakan sesuatu "universal dapat digunakan kembali" jika berperilaku seperti desktop Anda, bukan CA (yaitu, dapat menjalankan beberapa program tanpa perlu membuat ulang alam semesta). Apakah gagasan ini telah diformalkan di mana saja?
sumber
Jawaban:
Seperti yang Anda sebutkan dalam Topik Tesis / Teori Bahasa Automata Resmi, supervisor saya memiliki setidaknya beberapa intusi yang sama tentang "universalitas yang dapat digunakan kembali" sebagai "lebih baik" daripada gaya CA. Saya tidak yakin bahwa nama diberikan: http://www.diku.dk/~neil/blobentcs.pdf
Saya belum banyak fokus pada bagian itu, tetapi seperti yang saya lihat, ketika melalui literatur biocomputing, perbedaan utama terletak pada makna kata "pemrograman / programmable", misalnya apa sebenarnya yang dapat diprogram? Itu, dan bagian "program tersimpan" juga tapi saya menghargai nuansa yang ditimbulkan oleh pertanyaan Anda
Saya tidak punya jawaban yang tersedia untuk apa namanya
sumber
Telah ada pekerjaan dalam komunitas PL / sistem pada semantik dan pemodelan sistem operasi. Seperti yang Anda tunjukkan, apa yang Anda bicarakan mirip dengan OS: ia melakukan sesuatu, tetapi dijamin (yah, dalam kasus OS, dijamin-ish) untuk kembali ke "keadaan dasar". Orang-orang PL mungkin tidak memformalkan gagasan Anda tentang universal yang dapat digunakan kembali, tetapi Anda mungkin menemukan beberapa inspirasi di sana.
Formalisasi Anda harus menangkap perbedaan antara "mesin universal yang, setelah berjalan dengan satu input, jika Anda mengganti input dengan input lain, ia siap digunakan" dan "mesin universal yang, dengan urutan program input, menjalankannya berturut-turut. " Dan tentu saja, semua gagasan yang masuk akal tentang mesin universal mungkin memenuhi persyaratan yang terakhir. Jadi sepertinya cukup rumit ...
sumber