Apakah C sebenarnya Turing-lengkap?

40

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?

TLW
sumber
3
Apa "semantik abstrak" dari C? Apakah mereka didefinisikan di mana saja?
Yuval Filmus
4
@YuvalFilmus - Lihat misalnya di sini , yaitu C sebagaimana didefinisikan dalam standar sebagai lawan dari "ini adalah bagaimana gcc melakukannya".
TLW
1
ada "teknis" bahwa komputer modern tidak memiliki memori tak terbatas seperti TM namun masih dianggap "komputer universal". dan perhatikan bahwa bahasa pemrograman dalam "semantik" mereka tidak benar-benar mengasumsikan memori yang terbatas kecuali bahwa semua implementasinya tentu saja terbatas dalam memori. lihat misalnya apakah komputer kita berfungsi sebagai mesin Turing . pokoknya semua bahasa pemrograman "arus utama" sudah lengkap.
vzn
2
C (seperti mesin Turing) tidak terbatas pada menggunakan memori komputer internal untuk perhitungannya, jadi ini benar-benar bukan argumen yang valid terhadap kelengkapan Turing C.
reinierpost
@reinierpost - itu seperti mengatakan teletype adalah sapient. Itu mengatakan bahwa "C + eksternal TM-setara" adalah Turing-lengkap, bukan bahwa C adalah Turing-lengkap.
TLW

Jawaban:

34

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.2CHAR_BITt2CHAR_BIT×sizeof(t)

Khususnya, pointer hanya dapat mengambil paling banyak . Ini berarti bahwa ada jumlah objek terbatas yang terbatas.2CHAR_BIT×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×2CHAR_BIT×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.)

Gilles 'SANGAT berhenti menjadi jahat'
sumber
Tidak segera jelas mengapa set alamat harus terbatas. Saya menulis beberapa pemikiran dalam jawaban untuk pertanyaan yang Anda tautkan: cstheory.stackexchange.com/a/37036/43393
Alexey B.
4
Maaf, tetapi dengan logika yang sama, tidak ada bahasa pemrograman Turing-lengkap sama sekali. Setiap bahasa memiliki batasan eksplisit atau implisit pada ruang alamat. Jika Anda membuat mesin dengan memori tak terbatas, maka pointer akses acak juga akan memiliki panjang tak terbatas. Oleh karena itu, jika mesin tersebut muncul, ia harus menawarkan set instruksi untuk akses memori sekuensial, bersama dengan API untuk bahasa tingkat tinggi.
IMil
14
@IMil Ini tidak benar. Beberapa bahasa pemrograman tidak memiliki batasan pada ruang alamat, bahkan tidak secara implisit. Untuk mengambil contoh yang jelas, mesin Turing universal di mana keadaan awal rekaman membentuk program adalah bahasa pemrograman Turing-lengkap. Banyak bahasa pemrograman yang sebenarnya digunakan dalam praktik memiliki properti yang sama, misalnya Lisp dan SML. Bahasa tidak harus memiliki konsep "penunjuk akses acak". (lanjt.)
Gilles 'SO- stop being evil'
11
@IMil (lanjutan) Implementasi biasanya dilakukan untuk kinerja, tetapi kami tahu bahwa implementasi yang berjalan pada komputer tertentu tidak selesai-Turing karena dibatasi oleh ukuran memori komputer. Tetapi itu berarti bahwa implementasi tidak mengimplementasikan seluruh bahasa, hanya sebagian (dari program yang berjalan dalam N byte memori). Anda dapat menjalankan program di komputer, dan jika kehabisan memori, pindahkan ke komputer yang lebih besar, dan seterusnya selamanya atau sampai berhenti. Itu akan menjadi cara yang valid untuk mengimplementasikan seluruh bahasa.
Gilles 'SANGAT berhenti menjadi jahat'
6

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.

feersum
sumber
Ini mungkin berhasil. Kekhawatiran yang mungkin adalah bahwa hal itu bergantung pada pengalokasian sejumlah va_listvariabel otomatis yang tidak terbatas stack. Variabel-variabel ini harus memiliki alamat &stack, dan kami hanya dapat memiliki jumlah yang terbatas. Persyaratan ini bisa dielakkan dengan mendeklarasikan setiap variabel lokal register, mungkin?
chi
@chi AIUI, variabel tidak perlu memiliki alamat kecuali seseorang mencoba mengambil alamat tersebut. Juga, itu ilegal untuk menyatakan argumen segera sebelum elipsis register.
feersum
Dengan logika yang sama, bukankah seharusnya seorang inttidak diharuskan memiliki ikatan kecuali seseorang menggunakan ikatan itu atau sizeof(int)?
chi
@ Ya, tidak sama sekali. Standar ini mendefinisikan sebagai bagian dari semantik abstrak yang intmemiliki nilai antara beberapa batas hingga INT_MINdan INT_MAX. Dan jika nilai intmelimpah yang terikat, perilaku tidak terdefinisi terjadi. Di sisi lain, standar sengaja tidak mengharuskan semua objek secara fisik hadir dalam memori di alamat tertentu, karena hal ini memungkinkan optimasi seperti menyimpan objek dalam register, hanya menyimpan sebagian dari objek, mewakili secara berbeda dari standar. tata letak, atau menghilangkannya sama sekali jika tidak diperlukan.
feersum
4

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.

PyRulez
sumber
Seperti apa bentuk implementasi?
reinierpost
@reinierpost Saya kira itu akan mewakili data menggunakan beberapa model PA yang tidak standar. Ini akan menghitung operasi aritmatika menggunakan gelar PA . Saya pikir model seperti itu harus memberikan implementasi C yang valid.
PyRulez
Maaf, ini tidak berhasil. sizeof(t)itu sendiri adalah nilai tipe size_t, jadi itu adalah bilangan bulat alami antara 0 dan SIZE_MAX.
Gilles 'SANGAT berhenti menjadi jahat'
@Gilles SIZE_MAX juga tidak alami.
PyRulez
Ini merupakan pendekatan yang menarik. Perhatikan bahwa Anda juga perlu mis. Intptr_t / uintptr_t / ptrdiff_t / intmax_t / uintmax_t agar tidak standar. Dalam C ++ ini akan bertabrakan dengan jaminan kemajuan masa depan ... tidak yakin tentang C.
TLW
0

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.

Yves Daoust
sumber
Bukankah ini poin utama dari jawaban yang diterima? Saya tidak berpikir itu menambahkan sesuatu yang baru ke jawaban pertanyaan 2016 ini.
chi
@ Ya: tidak, jawaban yang diterima tidak menyebutkan bertukar ke memori eksternal, yang mungkin diyakini sebagai solusi.
Yves Daoust
-1

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.]

dokter
sumber
7
Saya tidak berpikir ini menjawab pertanyaan. Pertanyaannya sudah mengantisipasi jawaban ini, dan menjelaskan mengapa itu tidak valid: "walaupun standar C memungkinkan untuk size_t menjadi besar secara sewenang-wenang, itu harus diperbaiki dengan panjang tertentu, dan tidak peduli berapa lama itu diperbaiki masih terbatas. ". Apakah Anda punya tanggapan terhadap argumen itu? Saya tidak berpikir kita dapat menghitung pertanyaan sebagai dijawab kecuali jawabannya menjelaskan mengapa argumen itu salah (atau benar).
DW
5
Pada waktu tertentu, nilai tipe size_tterbatas. Masalahnya adalah Anda tidak dapat membuat batasan untuk size_tyang valid di seluruh perhitungan: untuk batasan apa pun, sebuah program mungkin meluap. Tetapi bahasa C menyatakan bahwa ada batasan untuk size_t: pada implementasi yang diberikan, ia hanya dapat tumbuh hingga sizeof(size_t)byte. Juga, bersikap baik . Mengatakan bahwa orang yang mengkritik Anda "tidak bisa berpikir sendiri" tidak sopan.
Gilles 'SANGAT berhenti menjadi jahat'
1
Ini jawaban yang benar. Mesin Pembalik tidak membutuhkan pita tak terbatas, namun mesin ini membutuhkan pita "panjang sewenang-wenang". Artinya, Anda dapat mengasumsikan bahwa rekaman itu sepanjang perlu untuk menyelesaikan perhitungan. Anda juga dapat mengasumsikan bahwa komputer Anda memiliki memori sebanyak yang dibutuhkan. Rekaman tak terbatas sama sekali tidak diperlukan, karena perhitungan apa pun yang terhenti dalam waktu terbatas tidak mungkin menggunakan rekaman tak terbatas.
Jeffrey L Whitledge
Apa jawaban ini menunjukkan bahwa untuk setiap TM Anda dapat menulis implementasi C dengan panjang pointer yang cukup untuk mensimulasikannya. Namun itu tidak mungkin untuk menulis satu C implementasi yang dapat mensimulasikan setiap TM. Jadi spesifikasi melarang bahwa implementasi tertentu adalah T-complete. Ini juga bukan T-melengkapi sendiri, karena panjang pointer sudah diperbaiki.
1
Ini adalah jawaban lain yang benar yang hampir tidak terlihat karena ketidakmampuan sebagian besar individu di komunitas ini. Sementara itu, jawaban yang diterima salah dan bagian komentarnya dijaga oleh moderator menghapus komentar kritis. Sampai jumpa, cs.stackexchange.
xamid
-1

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.

David Richerby
sumber
3
Saya berpendapat bahwa, kecuali definisi C memerlukan penyimpanan eksternal yang tidak terbatas, maka ini tidak dapat diterima sebagai bukti kelengkapan Turing. (ISO 9899 tidak mengharuskan, tentu saja, ditulis untuk rekayasa dunia nyata.) Yang menjadi perhatian saya adalah bahwa, jika kita menerima ini, dengan alasan yang sama kita dapat mengklaim bahwa DFA sudah selesai, karena dapat digunakan untuk mengarahkan kepala melewati kaset (penyimpanan eksternal).
chi
@ Ya, saya tidak mengerti bagaimana argumen DFA mengikuti. Inti dari DFA adalah bahwa ia hanya memiliki akses baca ke penyimpanan. Jika Anda membiarkannya "mendorong kepala melewati pita", bukankah itu mesin Turing?
David Richerby
2
Memang, saya sedikit mengolok-olok di sini. Intinya adalah: mengapa tidak apa-apa untuk menambahkan "pita" ke C, biarkan C mensimulasikan DFA, dan gunakan fakta ini untuk mengklaim bahwa C adalah Turing lengkap, ketika kita tidak dapat melakukan hal yang sama pada DFA? Jika C tidak memiliki cara untuk mengimplementasikan memori tidak terikat sendiri, maka itu tidak boleh dianggap Turing lengkap. (Saya masih akan menyebutnya "secara moral" Turing lengkap, setidaknya, karena batas-batasnya begitu besar sehingga dalam praktiknya mereka tidak penting dalam kebanyakan kasus) Saya pikir bahwa untuk menyelesaikan masalah secara definitif, seseorang akan membutuhkan spesifikasi formal yang C (standar ISO tidak mencukupi)
chi
1
@ Ya tidak apa-apa karena C menyertakan rutinitas I / O file. DFA tidak.
David Richerby
1
C tidak sepenuhnya menentukan apa yang dilakukan rutinitas ini - sebagian besar semantik mereka didefinisikan oleh implementasi. Implementasi AC tidak diperlukan untuk menyimpan konten file, misalnya, saya pikir itu bisa berperilaku seolah-olah setiap file "/ dev / null", jadi untuk berbicara. Juga tidak diharuskan untuk menyimpan jumlah data yang tidak terbatas. Saya akan mengatakan bahwa argumen Anda benar, ketika mempertimbangkan apa yang dilakukan sebagian besar implementasi C, dan menyamaratakan perilaku itu ke mesin yang ideal. Jika kita benar-benar mengandalkan definisi C, hanya saja, melupakan praktiknya, saya pikir itu tidak berlaku.
chi
-2

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_MAXHAI(2ssayaze_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.

Nathan Davis
sumber
6
Apa yang akan printf("%zu\n",SIZE_MAX);dicetak pada implementasi seperti itu?
Ruslan
1
@Ruslan, implementasi seperti itu tidak mungkin, sama seperti tidak mungkin untuk mengimplementasikan mesin Turing. Tetapi jika implementasi seperti itu mungkin, saya membayangkan itu akan mencetak beberapa representasi desimal dari jumlah yang sangat besar - mungkin, aliran angka desimal yang tak terbatas.
Nathan Davis
2
@NathanDavis Memungkinkan untuk menerapkan mesin Turing. Kuncinya adalah bahwa Anda tidak perlu membuat kaset yang tidak terbatas - Anda hanya perlu membuat bagian kaset yang digunakan secara bertahap sesuai kebutuhan.
Gilles 'SANGAT berhenti menjadi jahat'
2
@Gilles: Di alam semesta yang terbatas di mana kita hidup ini, tidak mungkin untuk menerapkan mesin Turing.
gnasher729
1
@NathanDavis Tetapi jika Anda melakukan itu, maka Anda telah berubah sizeof(size_t)(atau CHAR_BITS). Anda tidak dapat melanjutkan dari negara baru, Anda harus mulai lagi, tetapi pelaksanaan program mungkin berbeda sekarang karena konstanta-konstanta itu berbeda
Gilles 'SO-stop being evil'
-2

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).

Eugene
sumber
1
"Perbedaan keduanya bisa NaN". Tidak, itu tidak mungkin. Tidak ada yang namanya NaN bertipe integer di C.
TLW
Menurut standar, sizeofharus mengembalikan a size_t. Jadi, Anda harus memilih nilai tertentu.
Draconis
-4

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.)

xamid
sumber
4
Saya tidak mengikuti paragraf terakhir Anda. Anda mengklaim bahwa menambahkan pembatasan meningkatkan kekuatan ekspresif, tetapi itu jelas tidak benar. Pembatasan hanya dapat mengurangi daya ekspresif. Misalnya, jika Anda mengambil C dan menambahkan batasan bahwa tidak ada program yang dapat mengakses lebih dari 640 kb penyimpanan (dalam bentuk apa pun), maka Anda telah mengubahnya menjadi otomat terbatas hingga mewah yang jelas-jelas bukan Turing-lengkap.
David Richerby
3
Jika Anda memiliki jumlah penyimpanan tetap, Anda tidak dapat mensimulasikan apa pun yang membutuhkan lebih banyak sumber daya daripada yang Anda miliki. Hanya ada banyak konfigurasi yang memungkinkan memori Anda, yang berarti hanya ada banyak hal yang dapat Anda lakukan.
David Richerby
2
Saya tidak mengerti mengapa Anda merujuk ke "mesin yang ada secara fisik". Perhatikan bahwa Turing-kelengkapan adalah sifat dari model komputasi matematika, bukan sistem fisik. Saya setuju bahwa tidak ada sistem fisik, yang menjadi objek yang terbatas, dapat mendekati kekuatan mesin Turing, tetapi itu tidak relevan. Kita masih dapat mengambil bahasa pemrograman apa pun, mempertimbangkan definisi matematika dari semantiknya, dan memeriksa apakah objek matematika itu Turing lengkap. Permainan kehidupan Conway sangat kuat bahkan jika tidak ada implementasi fisik yang memungkinkan.
chi
2
@xamid Jika Anda memiliki masalah terkait kebijakan moderasi situs ini, bawa ke Computer Science Meta . Sampai saat itu, tolong bersikap baik . Pelecehan verbal terhadap orang lain tidak akan ditoleransi. (Saya telah menghapus semua komentar yang tidak berkaitan dengan masalah yang dihadapi.)
Raphael
2
Anda mengatakan memodifikasi lebar pointer tidak akan mengubah program, tetapi program dapat membaca lebar pointer dan melakukan apa pun yang mereka inginkan dengan nilai itu. Sama untuk CHAR_BITS.
Draconis