Saya mencoba menjelaskan kepada seseorang bahwa C adalah Turing-lengkap, dan menyadari bahwa saya tidak benar-benar tahu apakah itu Turing-lengkap secara teknis. (C seperti dalam semantik abstrak, bukan seperti dalam implementasi aktual.)

Jawaban "jelas" (kira-kira: ia dapat mengatasi jumlah memori yang sewenang-wenang, sehingga dapat meniru mesin RAM, sehingga Turing-lengkap) sebenarnya tidak benar, sejauh yang saya tahu, seolah-olah standar C memungkinkan agar size_t menjadi besar secara sewenang-wenang, itu harus diperbaiki pada panjang tertentu, dan tidak peduli berapa lama itu diperbaiki masih terbatas. (Dengan kata lain, meskipun Anda bisa, diberi mesin penghenti Turing yang sewenang-wenang, pilih panjang size_t sehingga akan berjalan "dengan benar", tidak ada cara untuk memilih panjang size_t sehingga semua mesin penghenti Turing akan berjalan dengan benar)

Jadi: apakah C99 Turing-lengkap?

Saya tidak yakin tetapi saya pikir jawabannya tidak, karena alasan yang agak halus. Saya bertanya pada Theoretical Computer Science beberapa tahun yang lalu dan tidak mendapatkan jawaban yang melampaui apa yang akan saya sajikan di sini.

Di sebagian besar bahasa pemrograman, Anda dapat mensimulasikan mesin Turing dengan:

• mensimulasikan otomat terbatas dengan program yang menggunakan jumlah memori terbatas;
• mensimulasikan rekaman dengan sepasang daftar bilangan bulat yang ditautkan, mewakili konten rekaman sebelum dan sesudah posisi saat ini. Memindahkan penunjuk berarti memindahkan kepala salah satu daftar ke daftar lainnya.

Implementasi konkret yang dijalankan pada komputer akan kehabisan memori jika rekaman terlalu lama, tetapi implementasi yang ideal dapat menjalankan program mesin Turing dengan setia. Ini dapat dilakukan dengan pena dan kertas, atau dengan membeli komputer dengan lebih banyak memori, dan kompiler yang menargetkan arsitektur dengan lebih banyak bit per kata dan seterusnya jika program tersebut kehabisan memori.

Ini tidak berfungsi di C karena tidak mungkin memiliki daftar tertaut yang dapat tumbuh selamanya: selalu ada batasan jumlah node.

Untuk menjelaskan alasannya, saya pertama-tama perlu menjelaskan apa itu implementasi C. C sebenarnya adalah keluarga bahasa pemrograman. Standar ISO C (lebih tepatnya, versi spesifik dari standar ini) mendefinisikan (dengan tingkat formalitas yang dimungkinkan oleh bahasa Inggris) sintaks dan semantik keluarga bahasa pemrograman. C memiliki banyak perilaku tidak terdefinisi dan perilaku implementasi-didefinisikan. "Implementasi" dari C mengkodifikasi semua perilaku implementasi-didefinisikan (daftar hal-hal yang dikodifikasikan ada dalam lampiran J untuk C99). Setiap implementasi C adalah bahasa pemrograman yang terpisah. Perhatikan bahwa arti kata "implementasi" agak aneh: apa artinya sebenarnya adalah varian bahasa, mungkin ada beberapa program kompiler berbeda yang menerapkan varian bahasa yang sama.

Dalam implementasi C yang diberikan, byte memiliki nilai yang mungkin. Semua data dapat direpresentasikan sebagai array byte: suatu tipe memiliki paling banyak 2 nilai CHAR_BIT × sizeof (t) . Jumlah ini bervariasi dalam implementasi C yang berbeda, tetapi untuk implementasi C yang diberikan, ini adalah konstan.$2^{\texttt{CHAR_BIT}}$t$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(t)}}$

Khususnya, pointer hanya dapat mengambil paling banyak . Ini berarti bahwa ada jumlah objek terbatas yang terbatas.$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$

Nilai-nilai CHAR_BITdan sizeof(void*)dapat diamati, jadi jika Anda kehabisan memori, Anda tidak bisa hanya melanjutkan menjalankan program Anda dengan nilai yang lebih besar untuk parameter-parameter itu. Anda akan menjalankan program di bawah bahasa pemrograman yang berbeda - implementasi C yang berbeda.

Jika program dalam suatu bahasa hanya dapat memiliki jumlah status terbatas, maka bahasa pemrograman tidak lebih ekspresif daripada automata terbatas. Fragmen C yang terbatas pada penyimpanan yang dapat dialamatkan hanya memungkinkan paling banyak menyatakan di mana n adalah ukuran pohon sintaksis abstrak dari program (mewakili keadaan aliran kontrol), oleh karena itu ini Program dapat disimulasikan oleh robot terbatas dengan banyak negara. Jika C lebih ekspresif, itu harus melalui penggunaan fitur lain.$n \times 2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$$n$

C tidak secara langsung memaksakan kedalaman rekursi maksimum. Implementasi diizinkan untuk memiliki maksimum, tetapi juga diizinkan untuk tidak memilikinya. Tetapi bagaimana kita berkomunikasi antara panggilan fungsi dan induknya? Argumen tidak baik jika dapat dialamatkan, karena itu secara tidak langsung akan membatasi kedalaman rekursi: jika Anda memiliki fungsi int f(int x) { … f(…) …}maka semua kemunculan xpada frame aktif fmemiliki alamat sendiri sehingga jumlah panggilan bersarang dibatasi oleh nomor tersebut. kemungkinan alamat untuk x.

Program AC dapat menggunakan penyimpanan yang tidak dapat dialamatkan dalam bentuk registervariabel. Implementasi "Normal" hanya dapat memiliki sejumlah kecil, variabel terbatas yang tidak memiliki alamat, tetapi secara teori implementasi dapat memungkinkan jumlah registerpenyimpanan tidak terbatas . Dalam implementasi seperti itu, Anda dapat membuat jumlah panggilan rekursif tanpa batas ke suatu fungsi, selama argumennya ada register. Tetapi karena argumennya adalah register, Anda tidak dapat membuat pointer ke mereka, dan karenanya Anda perlu menyalin data mereka di sekitar secara eksplisit: Anda hanya bisa memberikan jumlah data yang terbatas, bukan struktur data berukuran sewenang-wenang yang terbuat dari pointer.

Dengan kedalaman rekursi yang tidak terbatas, dan batasan bahwa suatu fungsi hanya bisa mendapatkan data dari penelepon langsungnya ( registerargumen) dan mengembalikan data ke penelepon langsungnya (nilai pengembalian fungsi), Anda mendapatkan kekuatan automata pushdown deterministic .

Saya tidak dapat menemukan cara untuk melangkah lebih jauh.

(Tentu saja Anda dapat membuat program menyimpan konten kaset secara eksternal, melalui fungsi input / output file. Tetapi kemudian Anda tidak akan bertanya apakah C adalah Turing-complete, tetapi apakah C plus sistem penyimpanan tak terbatas adalah Turing-complete, untuk yang jawabannya adalah "ya" yang membosankan. Anda mungkin juga mendefinisikan penyimpanan untuk menjadi oruring Turing - panggilan  fopen("oracle", "r+"), fwriteisi rekaman awal untuk itu dan freadkembali konten rekaman akhir.)

Tambahan C99 untuk va_copyargumen variadic API dapat memberi kita pintu belakang untuk Turing-kelengkapan. Karena menjadi mungkin untuk beralih melalui daftar argumen variadic lebih dari sekali dalam suatu fungsi selain dari yang awalnya menerima argumen, va_argsdapat digunakan untuk mengimplementasikan pointer tanpa pointer.

Tentu saja, implementasi nyata dari argumen variadic API mungkin akan memiliki pointer di suatu tempat, tetapi dalam mesin abstrak kami dapat diimplementasikan menggunakan sihir sebagai gantinya.

Berikut ini demo yang menerapkan otomat pushdown 2-stack dengan aturan transisi sewenang-wenang:

#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

Catatan: Jika va_listadalah tipe array, maka sebenarnya ada parameter pointer tersembunyi ke fungsi. Jadi mungkin akan lebih baik untuk mengubah jenis semua va_listargumen wrapped_stack.

Aritmatika tidak standar, mungkin?

Jadi, tampaknya masalahnya adalah ukuran terbatas sizeof(t). Namun, saya pikir saya tahu jalan keluar.

Sejauh yang saya tahu, C tidak memerlukan implementasi untuk menggunakan integer standar untuk tipe integernya. Oleh karena itu, kita dapat menggunakan model aritmatika non-standar . Kemudian, kita akan menetapkan sizeof(t)ke beberapa angka yang tidak standar, dan sekarang kita tidak akan pernah mencapainya dalam jumlah langkah yang terbatas. Oleh karena itu, panjang pita mesin Turing akan selalu kurang dari "maksimum", karena maksimum secara harfiah tidak mungkin tercapai. sizeof(t)sama sekali bukan angka dalam arti kata yang biasa.

Ini adalah salah satu teknisnya saja: teorema Tennenbaum . Ini menyatakan bahwa satu-satunya model aritmatika Peano adalah yang standar, yang jelas tidak akan berhasil. Namun, sejauh yang saya tahu, C tidak memerlukan implementasi untuk menggunakan tipe data yang memenuhi aksioma Peano, juga tidak memerlukan implementasi yang dapat dihitung, jadi ini seharusnya tidak menjadi masalah.

Apa yang harus terjadi jika Anda mencoba untuk mengeluarkan integer yang tidak standar? Nah, Anda bisa mewakili integer tidak standar menggunakan string tidak standar, jadi cukup alirkan digit dari bagian depan string itu.

IMO, batasan yang kuat adalah ruang addressable (melalui ukuran pointer) terbatas, dan ini tidak dapat dipulihkan.

Orang dapat menganjurkan bahwa memori dapat "ditukar ke disk", tetapi pada suatu titik informasi alamat itu sendiri akan melebihi ukuran yang bisa dialamatkan.

Dalam praktiknya, pembatasan ini tidak relevan dengan kelengkapan Turing. Persyaratan sebenarnya adalah untuk memungkinkan rekaman itu panjang sewenang-wenang, bukan tanpa batas. Itu akan menciptakan masalah berhenti dari jenis yang berbeda (bagaimana alam semesta "menghitung" rekaman itu?)

Ini sama palsu dengan mengatakan "Python tidak Turing lengkap karena Anda tidak dapat membuat daftar yang jauh lebih besar".

[Sunting: terima kasih kepada Tn. Whitledge karena mengklarifikasi cara mengedit.]

Media yang dapat dilepas memungkinkan kita menghindari masalah memori yang tidak terbatas. Mungkin orang akan berpikir ini adalah penyalahgunaan, tapi saya pikir tidak apa-apa dan pada dasarnya tidak bisa dihindari.

Perbaiki setiap implementasi mesin Turing universal. Untuk rekaman itu, kami menggunakan media yang bisa dipindahkan. Saat head keluar dari ujung atau awal disk saat ini, mesin meminta pengguna untuk memasukkan yang berikutnya atau yang sebelumnya. Kami dapat menggunakan penanda khusus untuk menunjukkan ujung kiri dari pita simulasi, atau memiliki pita yang tidak terikat di kedua arah.

Poin kunci di sini adalah bahwa semua yang harus dilakukan oleh program C adalah terbatas. Komputer hanya membutuhkan cukup memori untuk mensimulasikan robot, dan size_thanya perlu cukup besar untuk memungkinkan mengatasi jumlah memori (yang sebenarnya agak kecil) dan pada cakram, yang dapat dari ukuran terbatas tetap apa pun. Karena pengguna hanya diminta untuk memasukkan disk berikutnya atau sebelumnya, kami tidak perlu bilangan bulat besar tanpa batas untuk mengatakan "Silakan masukkan nomor disk 123456 ..."

Saya kira keberatan utama kemungkinan adalah keterlibatan pengguna tetapi itu tampaknya tidak dapat dihindari dalam implementasi apa pun, karena tampaknya tidak ada cara lain untuk menerapkan memori tidak terikat.

Pilih size_tuntuk menjadi besar tanpa batas

Anda dapat memilih size_tuntuk menjadi besar tanpa batas. Tentu saja, tidak mungkin mewujudkan implementasi seperti itu. Tapi itu tidak mengherankan, mengingat sifat terbatas dari dunia tempat kita hidup.

Implikasi Praktis

Tetapi bahkan jika itu mungkin untuk mewujudkan implementasi seperti itu, akan ada masalah praktis. Pertimbangkan pernyataan C berikut:

printf("%zu\n",SIZE_MAX);

SIZE_MAXSIZE_MAX$O(2^{size\_t})$size_tSIZE_MAXprintf

Untungnya, untuk tujuan teoretis kami, saya tidak dapat menemukan persyaratan dalam spesifikasi yang jaminannya printfakan berakhir untuk semua input. Jadi, sejauh yang saya ketahui, kami tidak melanggar spesifikasi C di sini.

Tentang Kelengkapan Komputasi

Masih membuktikan bahwa implementasi teoretis kami adalah Turing Lengkap . Kami dapat menunjukkan ini dengan menerapkan "Mesin Turing sekali pakai".

Sebagian besar dari kita mungkin menerapkan Mesin Turing sebagai proyek sekolah. Saya tidak akan memberikan detail implementasi tertentu, tetapi inilah strategi yang umum digunakan:

• Jumlah status, jumlah simbol, dan tabel transisi status ditetapkan untuk setiap mesin yang diberikan. Jadi kita bisa mewakili negara dan simbol sebagai angka, dan tabel transisi keadaan sebagai array 2 dimensi.
• Rekaman itu dapat direpresentasikan sebagai daftar tertaut. Kami dapat menggunakan satu daftar tautan ganda, atau dua daftar tautan tunggal (satu untuk setiap arah dari posisi saat ini).

Sekarang mari kita lihat apa yang diperlukan untuk mewujudkan implementasi seperti itu:

• Kemampuan untuk mewakili beberapa set angka yang tetap, tetapi besar, sewenang-wenang. Untuk mewakili angka sembarang, kami memilih MAX_INTuntuk tidak terbatas juga. (Atau, kita bisa menggunakan objek lain untuk mewakili negara dan simbol.)
• Kemampuan untuk membuat daftar tertaut besar yang sewenang-wenang untuk rekaman kami. Sekali lagi, tidak ada batasan ukuran. Ini berarti kami tidak dapat membuat daftar ini di muka, karena kami akan menghabiskan selamanya hanya untuk membuat rekaman kami. Tetapi, kita dapat membuat daftar ini secara bertahap jika kita menggunakan alokasi memori dinamis. Kita bisa menggunakan malloc, tetapi ada sedikit lagi yang harus kita pertimbangkan:
  • Spesifikasi C memungkinkan mallocuntuk gagal jika, misalnya, memori yang tersedia telah habis. Jadi implementasi kami hanya benar-benar universal jika malloctidak pernah gagal.
  • Namun, jika implementasi kami dijalankan pada mesin dengan memori tak terbatas, maka tidak perlu mallocgagal. Tanpa melanggar standar C, implementasi kami akan menjamin bahwa malloctidak akan pernah gagal.
• Kemampuan untuk menunjuk pointer, elemen array pencarian, dan mengakses anggota dari node daftar tertaut.

Jadi daftar di atas adalah apa yang diperlukan untuk mengimplementasikan Mesin Turing dalam implementasi C hipotetis kami. Fitur-fitur ini harus diakhiri. Namun, hal lain mungkin diizinkan untuk tidak berakhir (kecuali diminta oleh standar). Ini termasuk aritmatika, IO, dll.

Argumen utama di sini adalah bahwa ukuran size_t terbatas, meskipun bisa sangat besar.

Ada solusi untuk itu, meskipun saya tidak yakin apakah ini bertepatan dengan ISO C.

Asumsikan Anda memiliki mesin dengan memori tak terbatas. Dengan demikian Anda tidak dibatasi untuk ukuran pointer. Anda masih memiliki tipe size_t Anda. Jika Anda bertanya kepada saya apa itu sizeof (size_t) jawabannya hanya sizeof (size_t). Jika Anda bertanya apakah lebih besar dari 100 misalnya jawabannya adalah ya. Jika Anda bertanya apa sizeof (size_t) / 2 karena Anda bisa menebak jawabannya masih sizeof (size_t). Jika Anda ingin mencetaknya, kami dapat menyetujui beberapa hasil. Perbedaan keduanya bisa NaN dan sebagainya.

Ringkasannya adalah bahwa mengendurkan kondisi untuk size_t memiliki ukuran hingga tidak akan merusak program yang sudah ada.

PS Mengalokasikan ukuran memori (size_t) masih dimungkinkan, Anda hanya perlu ukuran yang dapat dihitung, jadi katakanlah Anda mengambil semua genap (atau trik serupa).

Ya itu.

1. Jawaban yang dikutip

Sebagai reaksi atas banyaknya downvotes pada jawaban saya yang benar (dan lainnya) - dibandingkan dengan persetujuan yang sangat tinggi atas jawaban yang salah - saya mencari penjelasan alternatif yang kurang mendalam secara teoritis. Saya menemukan ini . Saya harap ini mencakup beberapa kesalahan umum di sini, sehingga sedikit lebih banyak wawasan ditampilkan. Bagian penting dari argumen:

[...] Argumennya adalah sebagai berikut: seandainya seseorang telah menulis program penghentian yang diberikan yang mungkin memerlukan, selama pelaksanaannya, hingga sejumlah penyimpanan sewenang-wenang. Tanpa mengubah program itu, ada kemungkinan posteriori untuk mengimplementasikan perangkat keras komputer dan kompiler C-nya yang menyediakan penyimpanan yang cukup untuk mengakomodasi perhitungan ini. Ini mungkin memerlukan pelebaran lebar char (via CHAR_BITS) dan / atau pointer (melalui size_t), tetapi program tidak perlu dimodifikasi. Karena ini mungkin, C memang Turing-Lengkap untuk mengakhiri program.

Bagian rumit dari argumen ini adalah bahwa argumen ini hanya berfungsi ketika mempertimbangkan untuk menghentikan program. Pengakhiran program memiliki properti bagus ini yang memiliki batas atas statis untuk persyaratan penyimpanannya, yang dapat ditentukan secara eksperimental dengan menjalankan program di atas input yang diinginkan dengan meningkatkan ukuran penyimpanan, hingga "cocok".

Alasan mengapa saya salah kaprah dalam pemikiran saya adalah karena saya mempertimbangkan kelas yang lebih luas dari program “non-terminating” [...]

Singkatnya, karena untuk setiap fungsi yang dapat dikomputasi ada solusi dalam bahasa C (karena batas atas yang tidak terbatas), setiap masalah yang dapat dikomputasi memiliki program C, sehingga C adalah Turing-complete.

2. Jawaban asli saya

Ada kebingungan luas antara konsep-konsep matematika dalam ilmu komputer teoretis (seperti Turing-kelengkapan) dan aplikasi dunia nyata mereka, yaitu teknik-teknik dalam ilmu komputer praktis. Kelengkapan Turing bukan milik mesin yang ada secara fisik atau model terbatas ruangwaktu. Ini hanyalah objek abstrak yang menggambarkan sifat-sifat teori matematika.

C99 adalah Turing-complete terlepas dari pembatasan berbasis implementasi, seperti hampir semua bahasa pemrograman umum lainnya, karena ia mampu mengekspresikan serangkaian koneksi logis yang lengkap secara fungsional dan pada prinsipnya memiliki akses ke jumlah memori yang tidak terbatas. Orang-orang telah menunjukkan bahwa C membatasi akses memori acak secara eksplisit menjadi terbatas, tetapi ini bukan sesuatu yang tidak dapat dihindari, karena ini juga dinyatakan sebagai pembatasan dalam standar C, sementara Turing-kelengkapan diperlukan tanpa mereka :

Berikut adalah hal yang sangat mendasar tentang sistem logis yang cukup untuk bukti yang tidak konstruktif . Pertimbangkan kalkulus dengan beberapa skema aksioma dan aturan, sehingga himpunan konsekuensi logis adalah X. Sekarang jika Anda menambahkan beberapa aturan atau aksioma, himpunan konsekuensi logis tumbuh, yaitu harus merupakan superset dari X. Inilah sebabnya, misalnya , modal logika S4 terkandung dalam S5. Demikian pula, ketika Anda memiliki subspesifikasi yang Turing-lengkap, tetapi Anda menambahkan beberapa batasan di atas, ini tidak mencegah salah satu konsekuensi dalam X, yaitu harus ada cara untuk menghindari semua pembatasan. Jika Anda ingin bahasa non-Turing-complete, kalkulus harus dikurangi, tidak diperpanjang. Ekstensi yang mengklaim bahwa sesuatu tidak mungkin terjadi, tetapi sebenarnya hanya menambah ketidakkonsistenan. Ketidakkonsistenan dalam standar C ini mungkin tidak menghasilkan konsekuensi praktis, sama seperti Turing-kelengkapan tidak terkait dengan aplikasi praktis.

Simulasi angka arbitrer berdasarkan kedalaman rekursi (yaitu ini ; dengan kemungkinan untuk mendukung beberapa nomor melalui penjadwalan / pseudo-utas; tidak ada batas teoritis untuk kedalaman rekursi dalam C ), atau menggunakan penyimpanan file untuk mensimulasikan memori program tidak terbatas ( ide ) adalah mungkin hanya dua dari kemungkinan tak terbatas untuk secara konstruktif membuktikan Turing-kelengkapan C99. Kita harus ingat bahwa untuk komputasi, kompleksitas waktu dan ruang tidak relevan. Secara khusus, dengan asumsi lingkungan terbatas untuk memalsukan kelengkapan Turing hanyalah alasan melingkar karena batasan itu tidak termasuk semua masalah yang melebihi batas kompleksitas yang disyaratkan sebelumnya.

( CATATAN : Saya hanya menulis jawaban ini untuk mencegah orang berhenti untuk mendapatkan intuisi matematis karena beberapa jenis pemikiran terbatas yang berorientasi pada aplikasi. Sangat disayangkan bahwa sebagian besar peserta didik akan membaca jawaban yang diterima salah karena itu dibatalkan berdasarkan pada kelemahan mendasar dari penalaran, sehingga lebih banyak orang akan menyebarkan keyakinan palsu tersebut. Jika Anda menurunkan jawaban ini, Anda hanyalah bagian dari masalah.)