Kekuatan komputasi maksimum dari implementasi C

Jika kita membaca buku (atau versi lain dari spesifikasi bahasa jika Anda mau), berapa banyak daya komputasi yang dapat dimiliki oleh implementasi C?

Perhatikan bahwa "implementasi C" memiliki arti teknis: itu adalah contoh khusus dari spesifikasi bahasa pemrograman C di mana perilaku yang ditentukan implementasi didokumentasikan. Implementasi AC tidak harus dapat berjalan di komputer yang sebenarnya. Itu memang harus mengimplementasikan seluruh bahasa, termasuk setiap objek yang memiliki representasi bit-string dan tipe yang memiliki ukuran implementasi yang ditentukan.

Untuk keperluan pertanyaan ini, tidak ada penyimpanan eksternal. Satu-satunya input / output yang dapat Anda lakukan adalah getchar(untuk membaca input program) dan putchar(untuk menulis output program). Juga setiap program yang memanggil perilaku tidak terdefinisi tidak valid: program yang valid harus memiliki perilakunya yang didefinisikan oleh spesifikasi C ditambah deskripsi implementasi dari perilaku yang didefinisikan implementasi yang tercantum dalam lampiran J (untuk C99). Perhatikan bahwa memanggil fungsi perpustakaan yang tidak disebutkan dalam standar adalah perilaku yang tidak ditentukan.

Reaksi awal saya adalah bahwa implementasi C tidak lebih dari otomat terbatas, karena memiliki batasan pada jumlah memori yang dapat dialamatkan (Anda tidak dapat menangani lebih dari sizeof(char*) * CHAR_BITbit penyimpanan, karena alamat memori yang berbeda harus memiliki pola bit yang berbeda ketika disimpan dalam byte pointer).

Namun saya pikir implementasi dapat melakukan lebih dari ini. Sejauh yang saya tahu, standar tidak menetapkan batasan pada kedalaman rekursi. Jadi, Anda dapat membuat panggilan fungsi rekursif sebanyak yang Anda suka, hanya semua kecuali sejumlah panggilan yang terbatas harus menggunakan registerargumen yang tidak dapat dialamatkan ( ). Dengan demikian implementasi C yang memungkinkan rekursi sewenang-wenang dan tidak memiliki batasan jumlah registerobjek dapat mengkodekan automata pushdown deterministik.

Apakah ini benar? Bisakah Anda menemukan implementasi C yang lebih kuat? Apakah implementasi C lengkap-Turing ada?

Seperti disebutkan dalam pertanyaan, standar C mensyaratkan bahwa ada nilai UCHAR_MAX sehingga setiap variabel tipe unsigned charakan selalu memiliki nilai antara 0 dan UCHAR_MAX, inklusif. Lebih jauh lagi mengharuskan setiap objek yang dialokasikan secara dinamis diwakili oleh urutan byte yang dapat diidentifikasi melalui pointer tipe unsigned char*, dan bahwa ada konstan sizeof(unsigned char*)sehingga setiap pointer dari tipe tersebut dapat diidentifikasi oleh urutan sizeof(unsigned char *)nilai tipe unsigned char. Jumlah objek yang dapat dialokasikan secara simultan secara dinamis dengan demikian terbatas pada . Tidak ada yang akan mencegah kompiler teoretis dari menetapkan nilai-nilai konstanta tersebut untuk mendukung lebih dari$UCHAR\_MAX ^{sizeof(unsigned\ char*)}$ objek, tetapi dari perspektif teoritis keberadaan ikatan apa pun, tidak peduli seberapa besar, berarti ada sesuatu yang tidak terbatas.$10^{10^{10}}$

Suatu program dapat menyimpan jumlah informasi yang tidak terbatas pada stack jika tidak ada yang dialokasikan pada stack yang pernah diambil alamatnya ; dengan demikian seseorang dapat memiliki program C yang mampu melakukan beberapa hal yang tidak dapat dilakukan oleh robot berapapun dengan ukuran berapa pun. Jadi, meskipun (atau mungkin karena) akses ke variabel stack jauh lebih terbatas daripada akses ke variabel yang dialokasikan secara dinamis, C berubah dari otomat terbatas menjadi otomat push-down.

Namun, ada potensi kerutan lain: diperlukan bahwa jika suatu program memeriksa urutan nilai-nilai karakter tetap terkait panjang yang terkait dengan dua pointer ke objek yang berbeda, urutan tersebut harus unik. Karena hanya ada $UCHAR\_MAX ^{sizeof(unsigned\ char*)}$kemungkinan urutan nilai karakter, program apa pun yang membuat sejumlah pointer ke objek berbeda melebihi yang tidak dapat memenuhi standar C jika kode pernah memeriksa urutan karakter yang terkait dengan pointer tersebut . Akan tetapi, dalam beberapa kasus mungkin bagi kompiler untuk menentukan bahwa tidak ada kode yang akan memeriksa urutan karakter yang terkait dengan pointer. Jika setiap "char" benar-benar mampu menahan bilangan bulat terbatas, dan memori mesin adalah urutan bilangan bulat tak terhingga [diberikan mesin Turing tanpa pita, orang dapat meniru mesin seperti itu meskipun akan sangat lambat], kemudian memang mungkin untuk membuat bahasa C-Turing lengkap.

Dengan pustaka threading C11 (opsional), dimungkinkan untuk membuat implementasi Turing yang lengkap mengingat kedalaman rekursi yang tidak terbatas.

Membuat utas baru menghasilkan tumpukan kedua; dua tumpukan sudah cukup untuk kelengkapan Turing. Satu tumpukan mewakili apa yang ada di sebelah kiri kepala, tumpukan lainnya apa yang ada di sebelah kanan.

Saya pikir itu Turing lengkap : kita dapat menulis sebuah program yang mensimulasikan UTM menggunakan trik ini (saya dengan cepat menulis kode dengan tangan sehingga mungkin ada beberapa kesalahan sintaksis ... tapi saya harap tidak ada kesalahan (utama) dalam logika :-)

• mendefinisikan struktur yang dapat digunakan sebagai daftar tautan ganda untuk representasi rekaman

    typdef struct {
      cell_t * pred; // sel di sebelah kiri
      cell_t * succ; // sel di sebelah kanan
      int val; // nilai sel
    } cell_t 

The headakan menjadi pointer ke cell_tstruktur

• mendefinisikan struktur yang dapat digunakan untuk menyimpan keadaan saat ini dan sebuah bendera

    typedef struct {
      keadaan int;
      bendera int;
    } info_t 

• kemudian tentukan fungsi loop tunggal yang mensimulasikan Universal TM saat head berada di antara batas-batas daftar yang ditautkan ganda; ketika kepala mencapai batas set bendera struktur info_t (HIT_LEFT, HIT_RIGHT) dan kembali:

membatalkan simulate_UTM (cell_t * head, info_t * info) {
  while (true) {
    head-> val = UTM_nextsymbol [info-> state, head-> val]; // tulis simbol
    info-> state = UTM_nextstate [info-> state, head-> val]; // keadaan selanjutnya
    if (info-> state == HALT_STATE) {// cetak jika menerima dan keluar dari program
       putchar ((info-> state == ACCEPT_STATE)? '1': '0');
       keluar (0);
    }
    int move = UTM_nextmove [info-> state, head-> val];
    if (move == MOVE_LEFT) {
      head = head-> pred; // bergerak ke kiri
      if (head == NULL) {info-> flag = HIT_LEFT; kembali; }
    } lain {
      head = head-> succ; // bergerak ke kanan
      if (head == NULL) {info-> flag = HIT_RIGHT; kembali; }
    }
  } // masih dalam batas ... terus
}

• kemudian tentukan fungsi rekursif yang pertama memanggil simulasi UTM rutin dan kemudian secara rekursif memanggil dirinya sendiri ketika pita perlu diperluas; ketika rekaman itu perlu diperluas di atas (HIT_RIGHT) tidak ada masalah, ketika rekaman itu perlu digeser di bagian bawah (HIT_LEFT) hanya menggeser nilai sel menggunakan daftar tautan ganda:

stacker kosong (cell_t * atas, cell_t * bawah, cell_t * head, info_t * info) {
  simulate_UTM (head, info);
  cell_t newcell; // sel baru
  newcell.pred = atas; // perbarui daftar ditautkan ganda dengan sel baru
  newcell.succ = NULL;
  top-> succ = & newcell;
  newcell.val = EMPTY_SYMBOL;

  switch (info-> hit) {
    huruf besar HIT_RIGHT:
      stacker (& newcell, bottom, newcell, info);
      istirahat;
    case HIT_BOTTOM:
      cell_t * tmp = newcell;
      while (tmp-> pred! = NULL) {// menggeser nilai
        tmp-> val = tmp-> pred-> val;
        tmp = tmp-> pred;
      }
      tmp-> val = EMPTY_SYMBOL;
      stacker (& newcell, bottom, bottom, info);
      istirahat;
  }
}

• rekaman awal dapat diisi dengan fungsi rekursif sederhana yang membangun daftar ditautkan ganda dan kemudian memanggil stackerfungsi ketika membaca simbol terakhir dari pita input (menggunakan readchar)

membatalkan init_tape (cell_t * atas, cell_t * bawah, info_t * info) {
  cell_t newcell;
  int c = readchar ();
  if (c == END_OF_INPUT) stacker (& atas, bawah, bawah, info); // tidak ada lagi simbol, mulai
  newcell.pred = atas;
  if (top! = NULL) top.succ = & newcell; lain bawah = & newcell;
  init_tape (& newcell, bottom, info);
}

EDIT: setelah berpikir sedikit tentang itu, ada masalah dengan petunjuk ...

jika setiap panggilan fungsi rekursif stackerdapat mempertahankan pointer yang valid ke variabel yang ditentukan secara lokal di pemanggil maka semuanya baik-baik saja ; jika tidak, algoritme saya tidak dapat mempertahankan daftar tautan ganda yang valid pada rekursi tak terbatas (dan dalam hal ini a tidak melihat cara untuk menggunakan rekursi untuk mensimulasikan penyimpanan akses acak tak terbatas).

Selama Anda memiliki ukuran tumpukan panggilan yang tidak terbatas, Anda dapat menyandikan rekaman Anda di tumpukan panggilan, dan mengaksesnya secara acak dengan memutar penumpukan tumpukan tanpa kembali dari panggilan fungsi.

Suntingan : Jika Anda hanya dapat menggunakan ram, yang terbatas, konstruksi ini tidak berfungsi lagi, jadi lihat di bawah.

Namun sangat dipertanyakan mengapa stack Anda bisa tidak terbatas tetapi ram intrinsiknya tidak. Jadi sebenarnya saya akan mengatakan Anda bahkan tidak dapat mengenali semua bahasa biasa, karena jumlah negara dibatasi (jika Anda tidak menghitung trik tumpukan-mundur untuk mengeksploitasi tumpukan tak terbatas).

Saya bahkan akan berspekulasi bahwa jumlah bahasa yang dapat Anda kenali adalah terbatas (bahkan jika bahasa itu sendiri bisa tak terbatas, misalnya a*tidak apa-apa, tetapi b^khanya berfungsi untuk sejumlah terbatas ks).

EDIT : Ini tidak benar, karena Anda dapat menyandikan status saat ini dalam fungsi tambahan, sehingga Anda benar-benar dapat mengenali SEMUA bahasa biasa.

Anda kemungkinan besar bisa mendapatkan semua bahasa Tipe-2 untuk alasan yang sama, tetapi saya tidak yakin apakah Anda bisa mengatur keduanya, state dan stack-constent pada call-stack. Tetapi pada catatan umum, Anda dapat secara efektif melupakan ram, karena Anda selalu dapat skala ukuran robot sehingga alfabet Anda melebihi kapasitas ram. Jadi jika Anda bisa mensimulasikan TM dengan hanya tumpukan, Tipe-2 akan sama dengan Tipe-0, bukan?

Saya memikirkan hal ini sekali, dan memutuskan untuk mencoba menerapkan bahasa bebas-konteks dengan menggunakan semantik yang diharapkan; bagian penting dari implementasi adalah fungsi berikut:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

$\{a^n b^n c^n\}$

Setidaknya, saya pikir ini berhasil. Mungkin saya membuat beberapa kesalahan mendasar.

Versi tetap:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

Sejalan dengan jawaban @ supercat:

Klaim ketidaklengkapan C tampaknya berpusat di sekitar bahwa objek yang berbeda harus memiliki alamat yang berbeda, dan set alamat diasumsikan terbatas. Seperti @supercat menulis

Seperti disebutkan dalam pertanyaan, standar C mensyaratkan bahwa ada nilai UCHAR_MAXsedemikian rupa sehingga setiap variabel dari tipe unsigned char akan selalu memiliki nilai antara 0 dan UCHAR_MAX, termasuk. Lebih jauh lagi mengharuskan setiap objek yang dialokasikan secara dinamis diwakili oleh urutan byte yang dapat diidentifikasi melalui pointer dari tipe unsigned char *, dan bahwa ada konstanta sizeof(unsigned char*)sehingga setiap pointer dari tipe tersebut dapat diidentifikasi oleh urutan sizeof(unsigned char *)nilai dari tipe unsigned arang.

unsigned char*$\mathbb{N}$$\{0, 1\}$sizeof(unsigned char*)$\{0, 1\}^{\operatorname{sizeof}(\mathit{unsigned\ char*})}$$\mathbb{N}$sizeof(unsigned char*)$\mathbb{N}$$\omega$

Pada titik ini, orang harus memeriksa bahwa standar C memang memungkinkan.

sizeof$\in \mathbb Z$