Bisakah ada program yang diimplementasikan secara mekanis?

13

Apakah mungkin untuk membangun implementasi mekanis tujuan tunggal (non Turing lengkap) dari kata, Microsoft Word? Apakah mungkin untuk mengimplementasikan hal-hal seperti iterator, fungsi tingkat pertama, keseluruhan keseluruhan teknik pemrograman? Bisakah roda gigi dan bagian mekanis lainnya mewakili struktur data atau bahkan objek program? Pada titik tertentu apakah ini mengharuskan membangun mesin Turing yang setara dengan tujuan umum, atau dapatkah masing-masing fungsi, variabel, dll, memiliki konstruksi mekanis yang unik dalam bentuk roda gaya dan / atau roda gigi, ratchet, apa yang Anda miliki? Singkatnya saya bertanya-tanya apakah ada perangkat lunak yang diberikan pada komputer standar dapat dikompilasi ke cetak biru mekanis.

computability pl.programming-languages machine-models ar.hardware-architecture Alex Nye
sumber
Saya pikir, sesuatu yang menjalankan Microsoft Word bahkan tidak perlu dijalankan pada Mesin Turing, karena semua prosedur di Word harus diketahui (terbukti) mengakhiri (kecuali jika ada bug ofc), selain dari loop acara utama.
Realz Slaw
1
Ya pak !
Pratik Deoghare
1
Jika ini mungkin - yang tampaknya mungkin - maka harus dimungkinkan untuk membuat mesin non-turing-complete yang bertindak sebagai kompiler, membuat cetak biru untuk mesin lain dari kode sumber. Mesin-mesin yang mungkin atau mungkin sendiri turing lengkap.
Nick Johnson
@Realz Slaw: tidak jika Anda menyertakan I / O, makro VBA, atau ekstensi. Misalnya, saya ragu Word akan mengeluh jika Anda memberinya dokumen Word yang tak terbatas. Mungkin OS yang mendasarinya akan mencapai batas.
reinierpost
@reinierpost tetapi setiap rutin tidak harus selesai sepenuhnya; mereka akan terbukti berakhir atau tidak terbukti. Yaitu jika Anda memberinya dokumen yang tak terbatas, itu akan terbukti tidak berakhir. Maksud saya adalah bahwa sebagian besar program yang kita buat tidak harus menggunakan bahasa lengkap Turing, karena kita dapat membatasinya pada program yang dapat kita buktikan berakhir, diberikan data yang tidak terbatas, dan tidak berakhir jika diberikan data yang tak terbatas; dan jika Anda bisa melakukan ini, tidak ada masalah dengan Masalah Pemutusan. TLDR; jika Anda tidak dapat membuktikan rutinitas Anda berakhir atau tidak, Anda adalah programmer yang buruk.
Realz Slaw

Jawaban:

23

Ya itu. Begini cara melakukannya:

Anda pada dasarnya dapat mengkompilasi program apa pun yang Anda suka ke sirkuit. Lihat misalnya karya Dan Ghica dan rekan-rekannya di Geometry of Synthesis, yang menunjukkan cara mengkompilasi program ke dalam sirkuit.

  1. Dan R. Ghica. Geometri Sintesis: Pendekatan terstruktur untuk desain VLSI
  2. Dan R. Ghica, Alex Smith. Geometri Sintesis II: Dari Permainan ke Sirkuit Tunda-Sensitif
  3. Dan R. Ghica, Alex Smith. Geometri Sintesis III: Manajemen sumber daya melalui inferensi tipe.
  4. Dan R. Ghica, Alex Smith, Satnam Singh. Geometri sintesis IV: menyusun rekursi affine menjadi perangkat keras statis.

Sirkuit kemudian berubah untuk muncul kembali berulang kali di bidang teknik. John Baez memberikan tabel besar analogi konsep, dan bekerja banyak koneksi, di This Week's Finds 288-296. Jadi diagram sirkuit yang dihasilkan kompiler Dan dapat dipakai sebagai sistem mekanik atau hidrolik, jika Anda benar-benar menginginkannya!

╔══════════════════════════════════════════════════════════════╗
║                 displacement  flow      momentum     effort  ║
╠══════════════════════════════════════════════════════════════╣
║ Mechanics      position      velocity  momentum     force    ║
║ (translation)                                                ║
║                                                              ║
║ Mechanics      angle         angular   angular      torque   ║
║ (rotation)                   velocity  momentum              ║
║                                                              ║
║ Electronics    charge        current   flux         voltage  ║
║                                        linkage               ║
║                                                              ║
║ Hydraulics     volume        flow      pressure     pressure ║
║                                        momentum              ║
╚══════════════════════════════════════════════════════════════╝
  1. http://math.ucr.edu/home/baez/week288.html
  2. http://math.ucr.edu/home/baez/week289.html
  3. http://math.ucr.edu/home/baez/week290.html
  4. http://math.ucr.edu/home/baez/week291.html
  5. http://math.ucr.edu/home/baez/week294.html
  6. http://math.ucr.edu/home/baez/week296.html
Neel Krishnaswami
sumber
12
Konsekuensi: paten perangkat lunak tidak masuk akal.
András Salamon
1
Jawaban yang fantastis untuk pertanyaan yang nyaris tidak saya tanyakan. Terima kasih untuk grafik yang ditambahkan!
Alex Nye
5

Contoh praktisnya adalah komputer Tic Tac Toe yang terbuat dari Tinker Toys di Boston Science Museum (awalnya dibuat oleh tim mahasiswa MIT). Tentu saja, ini jauh lebih sederhana daripada Microsoft Word.

Ini adalah artikel 1989 dari Scientific American yang menggambarkannya.

Ada juga mesin Turing yang terbuat dari lego (ini sedikit curang karena menggunakan listrik --- memang komputer --- untuk pergerakan, tapi saya pikir desainnya bisa dimodifikasi untuk menghindari ini) besi tua , dan banyak lagi.

SamM
sumber
Saya menikmati artikel dan mesin lego, terima kasih.
Alex Nye
1

Mencoba untuk membahas secara spesifik contoh Anda membuat editor dalam perangkat keras, ada komputer eksperimental awal yang dibangun yang mengimplementasikan sistem operasi dan editor sepenuhnya dalam perangkat keras. Kemudian editor diganti dengan perangkat lunak, yang secara substansial mengurangi perangkat keras yang dibutuhkan. Ini dijelaskan dalam buku tentang arsitektur dan sejarah komputer. Sayangnya saya lupa namanya dan belum menemukan kata kunci untuk melacak sumber aslinya.

Bill Simpson
sumber