Apakah ada nama untuk "hal-hal fisik dari mana seseorang dapat membangun mesin Turing"?

Salah satu hal menakjubkan tentang ilmu komputer adalah bahwa implementasi fisik dalam beberapa hal "tidak relevan". Orang-orang telah berhasil membangun komputer dari beberapa substrat yang berbeda - relay, tabung hampa udara, transistor diskrit, dll. Orang mungkin akan segera berhasil membangun komputer lengkap Turing dari bahan optik non-linear, berbagai biomolekul, dan beberapa substrat lainnya. Pada prinsipnya, tampaknya mungkin untuk membangun komputer bola bilyar .

Namun, media fisik tidak sepenuhnya tidak relevan. Orang-orang telah menemukan bahwa set komponen tertentu - khususnya, dioda-resistor logika - "tidak lengkap": tidak peduli berapa banyak dari mereka yang Anda hubungkan ke catu daya dan satu sama lain, ada hal-hal tertentu yang sangat sederhana yang tidak dapat melakukan. (Logika diode-resistor dapat mengimplementasikan AND, OR, tetapi gagal untuk mengimplementasikan NOT). Juga, cara-cara tertentu untuk menghubungkan komponen - khususnya, single-layer perceptron s - adalah "tidak lengkap": ada beberapa hal yang sangat sederhana yang tidak dapat mereka lakukan. (Perceptron single-layer dapat mengimplementasikan AND, OR, NOT, tetapi gagal untuk mengimplementasikan XOR).

Apakah ada frasa yang kurang canggung untuk "hal-hal fisik yang darinya orang dapat membangun mesin Turing"? Atau sebaliknya, "hal-hal fisik yang, tidak peduli berapa banyak dari mereka yang dimiliki, tidak dapat membentuk mesin Turing"?

Untuk sementara saya menggunakan frase "set lengkap fungsional" atau "set universal gerbang" - atau, ketika berbicara dengan matematikawan, "hal-hal fisik yang dapat mengimplementasikan set fungsional lengkap" - tetapi saya telah diberitahu bahwa bukan t benar sekali. Beberapa perangkat komponen dapat mengimplementasikan perangkat fungsional lengkap; namun tidak mungkin untuk membuat mesin Turing-lengkap seluruhnya dari komponen-komponen ini. Misalnya, bola lampu dan sakelar lampu 4 arah yang dioperasikan secara manual dapat mengimplementasikan perangkat lengkap yang berfungsi (DAN, ATAU, BUKAN, XOR, dll.); namun tidak mungkin untuk membuat mesin Turing-lengkap seluruhnya dari sakelar lampu dan bola lampu, karena output (listrik atau optik) dari seseorang tidak dapat dimasukkan ke input (berputar secara mekanis) dari input berikutnya.

terkait: Apakah ada nama resmi untuk gagasan "universal dapat digunakan kembali"? dan Apakah ada nama untuk "chip yang dapat digunakan untuk membangun CPU"?

Saya percaya istilah yang tepat adalah "implementasi fisik Turing Machine".

$P \neq NP$, jadi tidak mungkin seorang ilmuwan komputer akan menyelesaikannya.

Anda dapat membaca lebih lanjut di makalah Scott Aaronson, Masalah NP-complete dan Realitas Fisik , terutama di bagian komputasi Analog dan Relativitas.

Anda juga dapat menemukan implementasi lego (dengan pita terbatas) di halaman berikut: http://legoofdoom.blogspot.com/

Fisika memodelkan realitas dengan teori-teori yang mendefinisikan konsep keadaan tergantung-waktu yang terkait dengan suatu sistem dan operator evolusi-waktu yang menggambarkan bagaimana keadaan ini berevolusi. Segera setelah Anda menemukan sistem fisik yang (setelah beberapa diskritisasi ruang-negara) mengimplementasikan ruang keadaan mesin Turing Anda, dan yang menampilkan istilah interaksi yang menerapkan (mungkin setelah diskretisasi waktu tertentu) evolusi waktu menurut tabel transisi keadaan dari mesin Turing Anda di ruang keadaannya, Anda telah menemukan model fisik Turing-lengkap dari sistem Anda. Dengan demikian Anda dapat diperdebatkan mengatakan, sistem Anda "adalah" Turing-complete.

Ketika melihat komputasi kuantum, Anda akan menemukan diskusi tentang implikasi teori fisik pada model komputasi Turing. Sebagai contoh, teori fisik harus dapat dibalik. Properti, yang tidak digunakan bersama oleh mesin Turing biasa. Namun tidak ada kerugian secara umum, karena setiap mesin Turing dapat disimulasikan dengan yang reversibel, dengan beberapa overhead yang dapat menukar waktu dengan ruang, dll.

Hanya berpikir saya akan menunjukkan bahwa kelengkapan media fisik untuk mensimulasikan logika yang diperlukan untuk membuat mesin komputasi lengkap Turing dapat dibangun hanya dalam kemampuannya untuk mewujudkan gerbang NAND, karena semua gerbang lain dapat berasal dari gerbang NAND (satu mungkin bertanya apa yang kemudian terdiri dari gerbang NAND, dan itu pertanyaan yang sangat pintar, tapi itu gerbang NAND sepenuhnya!).

Anda harus melihat karya Charles Babbage, dan orang-orang yang diilhaminya. Babbage membuat komputer fisik untuk mentabulasi fungsi polinomial ke dalam tabel yang dicetak untuk indeks Math (pada hari Anda akan memiliki tumpukan buku yang tidak memiliki apa-apa selain nama fungsi diikuti oleh lembaran nilai f (x)). Dia kemudian mulai bekerja pada apa yang akan telah menjadi komputer lengkap Turing menggunakan kamera penggerak dan semacamnya. Putranya, saya percaya itu adalah lanjutan dari pekerjaannya dan satu-satunya manifestasi fisik dari upaya gabungan mereka adalah ALU mekanik yang berfungsi penuh yang merupakan dasar dari kalkulator mekanik yang mungkin Anda ketahui atau tidak tahu. Namun dana untuk proyek-proyek ini menurun sebagai komputer mekanik dalam ukuran dan cara mereka dapat dibuat pada waktu itu sangat tidak praktis. Namun sejak itu, dan terutama dalam acara-acara terbaru, orang telah melewati dan melanjutkan penelitian Charles Babbage. Pendekatan ini mungkin memiliki tawa terakhir, karena ada orang-orang yang berpikir satu-satunya cara untuk membuat CPU serial lebih cepat daripada sekarang adalah dengan menerapkan beberapa pendekatan mekanis ini dalam CPU menghindari masalah yang muncul dari elektromagnetik pada skala yang lebih kecil daripada yang kita gunakan sekarang. Mekanika tampaknya bekerja pada skala apa pun.

Demikian pula, pekerjaan telah memasuki apa yang disebut komputer Quantum yang berupaya memfasilitasi komputasi besar melalui teori kuantum, saya tidak sepenuhnya yakin bagaimana semuanya bekerja. Tetapi secara fisik menarik bagi eksperimen fisika partikel yang mengandalkan teori kuantum.

Ada saya yakin banyak media komputasi yang berbeda sedang dieksplorasi, bahkan bebatuan di padang pasir, tetapi dari mereka saya tidak punya pengalaman.