Sirkuit Logika Combinasional dan Teori Komputasi

Saya mencoba untuk menghubungkan Combinational Logic Circuits (komputer berdasarkan hanya pada gerbang logis) dengan semua yang saya pelajari baru-baru ini dalam Theory of Computation.

Saya bertanya-tanya apakah sirkuit logika kombinasional dapat mengimplementasikan komputasi dengan cara yang sama seperti mesin negara terbatas. Mereka tampak sangat berbeda:

Finite State Machines, bagaimanapun, memiliki memori yang terdefinisi dengan baik dalam bentuk keadaan yang bisa masuk. Sirkuit logika kombinasional, bagaimanapun, tidak memiliki memori yang terdefinisi dengan baik sehingga untuk mengimplementasikan algoritma yang membutuhkan memori mereka agak menggunakan beberapa metode koneksi serial yang aneh (lihat caranya $C_{out}$ dari penambah sebelumnya terhubung ke $C_{in}$ penambah saat ini pada gambar di bawah).

Betapapun berbeda secara radikal tampaknya, mereka berdua tampaknya melakukan perhitungan. Sebagai contoh, keduanya dapat mengimplementasikan algoritma untuk penambahan biner (dan bahkan perkalian biner) namun perbedaan implementasi tersebut adalah:

FSM:

Sirkuit Logika Combinasional (C, seperti pada$C_{in}$ dan $C_{out}$, singkatan dari Carry):

Saya bahkan berpikir (walaupun masih sangat tidak pasti) bahwa kita dapat mengubah setiap FSM menjadi Sirkuit Logika Combinasional yang sesuai.

Jadi, saya bertanya pada diri sendiri:

Bisakah Sirkuit Logika Combinasional juga dianggap sebagai model komputasi sesaat? Bisakah kita menerapkan semua konsep yang kita pelajari dalam Teori Komputasi dan Teori Kompleksitas Komputasi, seperti kompleksitas ruang dan komputabilitas, untuk itu?

Di satu sisi, sepertinya mereka tidak cocok sebagai model perhitungan karena mereka tidak memiliki operasi dasar (seperti membaca / menulis kaset, pengurangan fungsi, langkah-langkah pencarian bukti paradigma pemrograman logis), mereka menerapkan perhitungan mereka secara instan.
Tetapi di sisi lain, mereka tampaknya cocok sebagai model perhitungan karena kita dapat memodelkan semua jenis perhitungan dengan mereka (penambahan biner adalah salah satu contoh), dan mereka dapat dilihat secara abstrak (dengan hanya berfokus pada tabel kebenaran dan gerbang logis dan lupa tentang sirkuit fisik yang mungkin mengimplementasikannya).
Jadi, apa yang kalian pikirkan?

Juga, jika memang dapat dianggap sebagai model komputasi (instan), apakah kalian punya contoh model komputasi lain yang serupa (juga instan)?

Terima kasih banyak sebelumnya

Sirkuit logika umum dalam teori kompleksitas, di mana mereka pergi dengan sirkuit nama . Ada perbedaan besar antara rangkaian dan model perhitungan seperti mesin Turing: setiap rangkaian hanya dapat menangani input dengan ukuran tetap. Untuk memperbaikinya, di bawah model perhitungan sirkuit, untuk setiap panjang input$n$ ada sebuah sirkuit $C_n$, dan bersama-sama mereka menghitung fungsi pada string yang panjangnya sewenang-wenang. Model perhitungan ini, seperti yang disebutkan, terlalu kuat: ia dapat menghitung fungsi yang tidak dapat dihitung, memang semua fungsi. Masalahnya adalah urutan rangkaian yang tidak terbatas tidak harus memiliki deskripsi yang terbatas. Untuk memperbaiki masalah ini, kami biasanya menuntut bahwa sirkuitnya seragam , yaitu, bahwa mereka dihasilkan oleh beberapa mesin Turing, yang pada input$n$ menghasilkan $C_n$.

Model sirkuit sangat populer dalam teori kompleksitas, bahkan tanpa batasan keseragaman. Alasannya adalah pengamatan berikut: mesin Turing yang berjalan dalam waktu polinom dapat dikonversi ke urutan (seragam) rangkaian ukuran polinom, dengan menggunakan ide-ide teorema Cook (yang menunjukkan bahwa SAT adalah NP-complete). Oleh karena itu jika Anda ingin membuktikan bahwa masalah tertentu tidak dapat diselesaikan dalam waktu polinomial, itu sudah cukup untuk menunjukkan bahwa itu tidak dapat diselesaikan oleh sirkuit ukuran polinomial.