Jika mesin abstrak dapat mensimulasikan dirinya sendiri, apakah itu membuatnya Turing lengkap?

Sebagai contoh, dalam bahasa pemrograman adalah umum untuk menulis kompiler / juru bahasa X-in-X, tetapi pada tingkat yang lebih umum banyak sistem Turing-complete yang dikenal dapat mensimulasikan diri mereka dengan cara yang mengesankan (misalnya mensimulasikan Game of Life Conway dalam Game of Life Conway ).

Jadi pertanyaan saya adalah: apakah suatu sistem dapat mensimulasikan dirinya sendiri cukup untuk membuktikan itu Turing lengkap? Ini tentu saja merupakan kondisi yang perlu.

Belum tentu. Sebagai contoh, otomat seluler blok dua dimensi dengan dua keadaan, di mana sel menjadi hidup hanya ketika empat pendahulunya memiliki tepat dua sel hidup yang berdekatan, dapat mensimulasikan dirinya dengan faktor dua perlambatan dan faktor dua ukuran ledakan, tetapi tidak diketahui Turing lengkap. Lihat B36 / S125 "2x2" Automa Seluler Seperti Hidup oleh Nathaniel Johnston untuk informasi lebih lanjut tentang robot blok ini dan aturan B36 / S125 untuk lingkungan Moore yang juga mampu mensimulasikan robot blok ini.

Tidak, tidak. Saya tahu dua kelas utama teknik untuk menghindari inkonsistensi / kelengkapan Turing.

1. Garis serangan pertama adalah mengatur sistem sehingga sintaksis dapat di-aritmetika, tetapi teorema titik tetap Godel tidak berjalan. Dan Willard telah bekerja secara luas dalam hal ini dan memberikan sistem logis verifikasi-diri yang konsisten. Caranya adalah dengan menghilangkan simbol fungsi multiplikasi dan tambahan, dan menggantinya dengan pembagian dan pengurangan. Ini memberi Anda tenaga kuda yang cukup untuk mewakili sintaks secara aritmatika, tetapi teorema titik tetap tidak berjalan karena perkalian tidak terbukti total.

   Lihat Dan Willard. Sistem Aksioma Verifikasi Diri, Teorema Ketidaklengkapan dan Prinsip Refleksi Terkait . Jurnal Symbolic Logic 66 (2001) hlm. 536-596.

2. Baris kedua serangan memungkinkan lebih banyak menggunakan titik-titik tetap, tetapi untuk mengatur semuanya sehingga sintaksis tidak ter-aritmetisasi. Sistem tercantik untuk ini adalah (IMO) berdasarkan varian logika linier. Sebagai contoh, dalam Teori Set Affine Set Kazushige Terui, bahkan prinsip pemahaman himpunan penuh yang tidak terbatas adalah masuk akal, tetapi karena logika ambient dari teori himpunan adalah linier (dan karenanya kontraksi tidak diperbolehkan), paradoks Russell tidak dapat diturunkan.

   Alasan intuitif mengapa aritmetisasi gagal adalah bahwa ruang fungsi linear cahaya diatur sehingga semua penghuninya adalah waktu polinomial. Akibatnya, versi linear cahaya dari aksioma Peano tidak dapat membuktikan total eksponensial (karena eksponensial bilangan unary membutuhkan waktu eksponensial), sehingga tidak ada lagi isomorfisme antara bilangan asli dan string bit.$A \multimap B$

   Kazushige Terui. Teori himpunan affine ringan: Teori himpunan naif waktu polinomial. Studia Logica, Vol. 77, No. 1, hlm. 9-40, 2004.

   Saya pikir makalah ini lebih mudah diakses setelah membaca makalah Yves Lafont berikut:

   Y. Lafont, Logika Linier Lembut dan Waktu Polinomial , Ilmu Komputer Teoretis 318 (edisi khusus tentang Kompleksitas Komputasi Implisit) p. 163-180, Elsevier (2004)

   Teori himpunan Terui sangat ekspresif, tetapi sulit untuk dibandingkan dengan teori himpunan tradisional, karena tata cara pembuktian-teori bukanlah alat yang baik untuk membandingkan sistem yang sangat lemah. Sebagai contoh, teori himpunan Terui jelas tidak dapat membuktikan total eksponensial, dan karenanya kekuatan teoritik pembuktiannya bahkan tidak dapat menjangkau hingga . Kelas kompleksitas mungkin lebih baik - ini lengkap untuk polytime (dapat membuktikan setiap total fungsi polytime, tetapi tidak lebih).$\omega$

   Saya cenderung menganggap sistem semacam ini sebagai pembuktian-konsep untuk gagasan bahwa teori kompleksitas dapat berfungsi sebagai landasan bagi jenis-jenis ultrafinitisme tertentu.

Pertimbangkan model mesin berikut. Mesin dengan kode , setelah input , menghasilkan selalu.x $i$$x$$0$

Perhatikan bahwa setiap mesin dalam model ini bersifat universal, karena untuk semua .$M$$M(\langle \ulcorner M' \urcorner, x \rangle ) = M'(x) = 0$$M', x$

Ini jelas bukan Turing lengkap tetapi juga jelas memiliki mesin universal.