圖靈論題

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

圖靈論題英文Turing thesis)係運算理論上嘅一個重要諗法。根據圖靈論題,一個施喺自然數身上嘅函數可以靠有效方法(指部運算機械會喺數量有效嘅時間之內計完)嚟計到答案 if and only if 個函數可以用圖靈機(Turing machine;一種同廿世紀數碼電腦有好多共通點嘅理論運算機械)嚟計到答案;用日常用語講嘅話,意思即係指任何物理上有可能計到嘅問題都可以用圖靈機嚟計[1]

[編輯]

  1. Ben-Amram, A.M. (2005). "The Church-Turing Thesis and its Look-Alikes" (PS). SIGACT News. 36 (3): 113-116.