1樓：櫻桃
點進來發現看到的不是我所期望的問題。我更想知道的是：「現實中是否可以設計出來比圖靈機能力更強的機器？
」如果答案是是，那麼基於圖靈機的現有理論不就一下子全部變得沒有意義了？圖靈機解決不了算啥，我更強的機器能解決就行。
2樓：pyj philippica
知乎是不是戾氣太重了些，雖說題主有些概念沒理解清楚但知乎不就是乙個看似簡單的問題無限開腦洞的地方麼？所有只噴人嘲諷但什麼乾貨都沒講的已經預防性拉黑
答題的分割線
至於題主說的計算能力弱於turing machine的，其它答主已經說的PDA, DFA之類一坨就不再贅述了。
我覺得這是個很好的題目啊，題主的直覺非常準，當turing machine(TM)的紙帶有限的時候計算能力的確弱於turing machine，有這樣限制的TM稱為LBA：Linear bounded automaton
在chomsky的等級中，LBA能夠接受context sensitive語言，能力弱於TM而強於PDA。
事實上LBA的能力已經是很強的了，例如A_DFA, A_DFA, A_CFG之類一幹語言都可以被LBA接受，你反而很難構造乙個語言屬於L(TM)而不屬於L(LBA)
當然強行構造也是可以的，比如語言EMPTY: 這種語言顯然LBA接受不來
3樓：hjiayz
一切通用計算機語言的表達能力是圖靈等價的。
計算機中，一切都和抽象密不可分。
圖靈機模型是計算機的抽象模型，代表了理論上計算機能夠達到的計算能力的上界。
我可以買一台一秒鐘算一次的計算機，也可以買一台一秒鐘計算100萬次的計算機。雖然都是計算機，但是作為實體顯然有不同的效能引數。
同樣，我們給這些機器程式設計，同樣乙個程式，雖然程式本身沒錯誤，但是有的機器會記憶體溢位，有的機器快速執行完了。
如果不懂什麼是抽象，那麼換個專業吧。
4樓：
現實中的計算機實際上是個巨大的有限狀態自動機。因為狀態實在是太多了,大約 2^(10^13)。在一些小規模的問題上能勝任圖靈機的工作。
有限狀態自動機與圖靈機之間的計算模型有確定下推自動機（弱）和非確定下推自動機（強）
5樓：
紙帶無限長只是為了保證能解決任意大小的有限輸入而已。一旦圖靈機紙帶有限，我只要弄乙個所需儲存空間大於紙帶長度的問題，圖靈機就沒法解決了，這還算什麼通用計算模型？
把「無限紙帶」這種說法換成「不限制紙帶長度」——這樣看起來就舒服多了。
6樓：靈劍
只要演算法能在有限步中結束，紙帶也就只會使用有限長度，實際上紙帶對應的是外存和輸入輸出，狀態機才是對應記憶體。可計算性上這幾種模型是互相等價的。
如何理解」圖靈機即演算法，演算法即圖靈機「這個論斷？
Xyan Xcllet 圖靈機即演算法，演算法即圖靈機 這一論斷跟人腦其實沒有多大聯絡，因為大腦是乙個物理實體，要跟可計算性相關聯需考慮 Church Turing Thesis 的 Physical Versions，人腦的可計算集合是否等價於圖靈機可計算集合目前未知，不應該摻和進來。我對於這乙個...
圖靈機是發明的還是發現的？
玄星 圖靈機算是計算機的一種抽象 類似的理論模型還有很多，參見Model of computation，其中lambda calculus是現在比較火的functional programming的基石 而計算機算是個 發明 吧。英文wiki裡很清楚，是 invented，不是discovered ...
為什麼圖靈機不能辨認HALT的補集？
MatthewYan 你把圖靈機想象成乙個程式，假設輸入圖靈機的 機器M和輸入X 分別是程式和引數，程式有可能陷入死迴圈但誰也不知道什麼輸入引數會造成死迴圈。好了，現在你讓乙個程式去 圖靈機 檢測另乙個程式 輸入M 是否會在輸入引數X的情況下停機，顯然你要去執行那個程式 輸入M 但是，如果你要檢測的...