Saya membangun komputer mekanik yang ditenagai kelereng. Apa keterbatasan teoretisnya?

8

Selama beberapa tahun terakhir, saya membangun sebuah komputer mekanik yang ditenagai oleh kelereng dan membuat game darinya. Ini mirip dengan Digi-Comp II yang lama, kecuali untuk dua perbedaan utama:

  1. Bagian dapat diposisikan di papan tulis.
  2. Anda dapat menghubungkan banyak 'bit' secara bersamaan menggunakan roda gigi. Ketika salah satu dari bit-bit ini dibalik, itu membalik bit-bit lain yang terhubung dengannya.

Tautan di atas menjelaskan cara kerjanya. Pertanyaan saya adalah, apa batasan teoretisnya? Latar belakang komputasi teoretis saya lemah, jadi tolong ELI5.

sunting: Saya tidak tertarik dengan batasan yang jelas: kecepatan (tidak akan memenangkan balapan di sana ...), ukuran papan, atau # kelereng. Saya lebih tertarik pada keterbatasan teoretisnya. Mungkin akan membantu untuk membaginya menjadi dua pertanyaan:

  1. Bagaimana bisa dibuktikan (atau tidak terbukti) menjadi Turing-complete?
  2. Jika lebih dari 3 bit gigi dihubungkan bersama, gesekan menjadi terlalu besar untuk sebuah kelereng untuk mengubah semuanya sekaligus. Apakah itu menciptakan batasan tambahan?

Terima kasih - Saya sangat senang membaca jawaban Anda! Saya sudah memikirkan hal ini sejak lama.

complexity-theory turing-machines computer-architecture computation-models Paul Boswell
sumber
3
Apakah Anda ingin mempertimbangkan model ideal (ukuran grid tak terbatas, kelereng tak terhingga banyaknya), atau mesin khusus yang ada? Melihat melagne dari tag yang Anda pilih, dapatkah Anda mempersempit pertanyaan yang ingin Anda atasi? Apa yang bisa dihitung? Seberapa cepat hal-hal dapat dihitung? Apa pertanyaan tentang arsitektur yang ada dalam pikiran Anda?
Raphael
1
Cara termudah untuk mempersempit kemampuan model Anda adalah menjawab pertanyaan-pertanyaan ini. 1) Apa itu input dan output? 2) Gerbang logis mana yang bisa Anda modelkan? Saya bertanya 2) karena jelas bahwa Anda tidak memiliki komputer universal di sana; setiap konfigurasi papan adalah program tetap, dan yang berhubungan erat dengan sirkuit. Jadi, jika Anda dapat mensimulasikan set lengkap gerbang (misalnya gerbang NAND), Anda memiliki model Turing-complete (dengan asumsi semuanya tak terbatas). Karena Anda tidak memiliki komponen statis dengan dua input dan satu output, saya tidak segera melihat apa yang terjadi.
Raphael
2
Yang mengatakan, proyek menarik! Harap beri tahu kami di Obrolan Ilmu Komputer saat diluncurkan.
Raphael
3
Dalam video, Anda berkata: jika Anda membuat papan yang cukup besar, itu bisa melakukan apa yang bisa dilakukan komputer mana pun. Ya, ya dan tidak: dengan komputer, Anda dapat (secara teoritis) membangun papan yang cukup besar, tetapi dengan papan, Anda dapat membangun komputer yang membutuhkan papan yang lebih besar - dan itu berarti papan Anda tidak Turing lengkap. Kelengkapan Turing membutuhkan pengoperasian pada memori besar yang sewenang-wenang , sesuatu yang tidak bisa dilakukan papan Anda. Setiap mesin Turing adalah batas rangkaian tak terbatas dari mesin Turing pita-terbatas, tetapi itu tidak membuat mesin Turing pita-terbatas Turing lengkap.
reinierpost
2
Jika Anda membuat memperbesar bagian papan dari operasi mesin, mereka menjadi Turing lengkap.
reinierpost

Jawaban:

3

Apa yang Anda miliki sekarang adalah komputer beton. Kami tidak dapat membandingkannya dengan model komputasi sampai itu diformalkan dengan benar.

Intuisi saya adalah bahwa papan bisa dimodelkan sebagai arsitektur aliran data . Model komputasi yang disusun sesuai dengan paradigma ini bisa menjadi Turing-complete, tetapi (seperti yang dikatakan dalam komentar) tidak ada komputer konkret yang akan setara dengan Turing, dan saya pikir Anda tidak perlu khawatir tentang hal ini. Semua komputer nyata hanyalah metafora yang berfungsi (tidak sempurna) dari model komputasi formal.

Jika Anda menemukan ide untuk meniru lebih dekat mesin dataflow setara Turing, ada beberapa masalah yang dapat diatasi untuk "memperkuat metafora", sehingga untuk berbicara. Memperkenalkan siklus dan komposisi mesin akan menjadi dua hal yang paling penting, menurut saya, tapi saya pikir mesin Anda sudah cukup luar biasa. Ini melayani tujuannya dengan sangat baik, dan "perbaikan" ini bisa mengorbankan kegunaannya.

André Souza Lemos
sumber
Terima kasih! Dan sangat membantu! Saya tidak tahu tentang perbedaan antara arsitektur dataflow dan, katakanlah, arsitektur Von Neumann sebelumnya. Saya hanya membayangkan bahwa, jika papannya lebih besar, arsitektur Von Neumann dapat dibangun. Adakah peluang Anda dapat menawarkan definisi atau tautan ke apa yang Anda maksud dengan "siklus" dan "komposisi"?
Paul Boswell
Untuk siklus, bayangkan bahwa ada cara untuk mengirim kembali kelereng, ke awal atau ke memori menengah di tengah. Itu akan memungkinkan Anda untuk menghitung beberapa jenis fungsi rekursif primitif. Komposisi mesin mirip dengan komposisi fungsi, bayangkan Anda bisa menyambungkan output satu papan ke input orang lain.
André Souza Lemos
Komputer von Neumann adalah siklus besar.
André Souza Lemos