圖靈完備語言

来自中文百科专业版
(重定向自非圖靈完備語言
跳转至: 导航搜索

  繁体.png  简体.png  2022 年 8 月 14 日 星期日

中文名稱
語言特征
具有圖靈完備性
漢語拼音
Túlíng Wánbèi Yǔyán
包  括
過程式語言、面向對象語言、多范式語言、
英文名稱
Turing-complete language
深奧的語言等
圖靈完備語言

概述

  如果一個計算機語言具有圖靈完備性(Turing Completeness),那么這個語言就是圖靈完備語言

{Top}

背景

艾倫·麥席森·圖靈

艾倫·圖靈

  艾倫·麥席森·圖靈Alan Mathison Turing,1912.6.23 - 1954.6.7),英國數學家、邏輯學家、密碼學家和英國首位計算機科學家,被譽為計算機科學和人工智能之父。[1] [2]

  他對計算機科學的發展有著很高的影響力,他用圖靈機提供了算法和計算概念的形式化,圖靈機可以被視為通用計算機的模型。他的圖靈測試對人工智能的發展,作出了重要的、典型的、具挑戰性的和持久的貢獻。[3] [4]

{Top}

圖靈機

  在 1928 年第八屆國際數學家大會上,德國數學家希爾伯特(David Hilbert,1862 - 1943)提出了關于數學的三個精辟問題:[5]

  • First, was mathematics complete ...(數學是完備的嗎?)
  • Second, was mathematics consistent ...(數學是一致的嗎?)
  • And thirdly, was mathematics decidable ?(數學是可判定的嗎?)
圖靈機的模型

  希爾伯特的第三個問題又被稱為判定性問題(Entscheidungsproblem)。為了證否這個命題,1936 年,圖靈發表了一篇論文,題為《論可計算數,及其在判定性問題上的應用》(On Computable Numbers, with an Application to the Entscheidungsproblem)。在這篇論文里,圖靈提出了一種假設的計算裝置,他稱之為 A-Machine(Automatic Machine,自動機器),這就是圖靈機[6]

{Top}

可計算函數

  1938 年,在美國普林斯頓大學攻讀博士學位的圖靈,發表了一篇博士論文,題為《基于序數的邏輯系統》(Systems of Logic Based on Ordinals)。在這篇論文里,圖靈定義了可計算函數[7]

  • A function is effectively calculable if its values can be found by some purely mechanical process.
  • 如果一個函數的值可以通過某種純機械的過程找到,那么這個函數就可以有效地計算出來。

  在作為特定計算模型的圖靈機上產生的可計算函數,就被稱為圖靈可計算函數[8]

{Top}

圖靈完備性

  如果一個計算系統可以計算每一個圖靈可計算函數,那么這個系統就是圖靈完備的;或者說,這個系統可以模擬通用圖靈機。[9]

  圖靈完備性也可以用來描述計算機語言的計算能力。

{Top}

定義

  具有圖靈完備性的計算機語言,就被稱為圖靈完備語言。絕大多數的編程語言,都是圖靈完備語言。這包括:[10]

  • 廣泛使用的所有通用語言:
    • 過程式語言,如 FORTRAN、Pascal 等。
    • 面向對象語言,如 Java、Python 等。
    • 多范式語言,如 Ada、C++ 等。
  • 使用不太常見范式的大多數語言:
    • 函數式語言,如 Haskell、Mercury 等。
    • 邏輯式語言,如 Logtalk、Prolog 等。
    • 聲明式語言,如 SQL、XSLT 等。
    • 深奧的語言,一種奇特的數學娛樂形式,程序員用極其困難但數學上圖靈等價的語言來實現基本的編程結構。

{Top}

非圖靈完備語言

  并非所有的計算機語言都是圖靈完備的,例如標記語言,或者更恰當地稱為“容器語言”或“數據描述語言”,就不是圖靈完備的。[11]

  非圖靈完備語言Non-Turing-complete language),包括 HTML、JSON、XML、YAML 等。

{Top}

參考資料

  1. {} Alan Turing - Infogalactic
  2. {} 艾倫·圖靈——如謎的解謎者 - 科學松鼠會
  3. {} 148 封圖靈文件重現,稱自己厭惡美國 - 澎湃新聞
  4. {} “人工智能之父”圖靈登上 50 英鎊紙鈔 - 澎湃新聞
  5. {} 計算的極限(零):邏輯與圖靈機 - 科學松鼠會
  6. {} Turing machine - Infogalactic
  7. {} Alan Turing's a-(automatic-)machine - Infogalactic
  8. {} Computable function - Infogalactic
  9. {} Turing completeness - Infogalactic
  10. {} Examples - Infogalactic
  11. {} Non-Turing-complete languages - Infogalactic

{Top}