這一部分只針對懂計算機編程的工程獅和程序猿看。
圖靈完備需要自動機的知識。人們很好奇需要什么樣的機器才能表達出某種語言。
大致可以分為有限狀態(tài)自動機，下推自動機和圖靈機那么幾檔。前者所能表達的語言是后者的真子集。
有限狀態(tài)自動機只能表達正則語言。下退自動機能夠表達上下文無關語言。而圖靈機的語言是遞歸可枚舉語言。不過也有語言不是圖靈機表達得了的，比如對角語言。
圖靈機可以對應到一個字符串，并被別的圖靈機模擬。能夠模擬圖靈機，則稱之為圖靈完備，當然，圖靈機可以模擬有限狀態(tài)自動機和下推自動機。
我們的電腦便是一臺通用圖靈機。這又涉及到生活中的問題到語言的一個轉換。
P和NP分別是確定型圖靈機和非確定型圖靈機在多項式的推演步驟下，所能表達的語言集合。
這兩類圖靈機所能表達的語言集合是一樣的。就是多項式推演步驟這個條件一加，就未解之謎了。
可判定性問題，許多問題還真不是圖靈機能解決的，比如：圖靈機不能表達的語言。著名的問題有圖靈機停機問題。
P與NP其實都是可判定問題，他們其實都是指多項式時間內可判定，只是需要動用非確定型圖靈機。
判定圖靈完備的方法就是看該編程語言能否模擬出圖靈機。
圖靈不完備的語言常見原因有循環(huán)或遞歸受限，比如：無法寫不終止的程序，無法實現(xiàn)類似數(shù)組或列表這樣的數(shù)據(jù)結構，使能寫的程序有限。
圖靈完備可能帶來壞處， 如C++模板語言是在類型檢查時執(zhí)行，如果編譯器不檢查，我們完全可以寫出使得C++編譯器陷入死循環(huán)的程序。
圖靈不完備也不是沒有意義，有些場景我們需要限制語言本身，比如：限制循環(huán)和遞歸，可以保證該編程語言能寫的程序一定是終止的。
（文章原標題：圖靈完備—《區(qū)塊鏈思維》第36塊 作者：袁曄 來源：簡書）
- 蜜度索驥：以跨模態(tài)檢索技術助力“企宣”向上生長
- 周星馳Web3.0團隊：下個月上線獨立App，“星爺”以創(chuàng)作者身份亮相
- 時隔一年半，比特幣交易價格再次站上4萬美元
- 狗狗幣投資人指控馬斯克內幕交易：賣力吆喝只為自己套現(xiàn)
- 報告：2022年加密貨幣非法交易犯罪金額超過200億美元
- Coinbase啟動第二輪大裁員 涉及950人
- 破產后的FTX又遇“糟心事”：10多億美元客戶資金不知去向
- 人民日報評論：數(shù)字藏品熱度退去？規(guī)范發(fā)展方能行穩(wěn)致遠
- 以太坊完成合并：這對區(qū)塊鏈意味著什么？
- 馬斯克2580億美元狗狗幣訴訟規(guī)模擴大 旗下多家公司成被告
- Forrester報告：Web3可能比現(xiàn)有網(wǎng)絡更容易遭受攻擊
免責聲明：本網(wǎng)站內容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準確性及可靠性，但不保證有關資料的準確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負責。本網(wǎng)站對有關資料所引致的錯誤、不確或遺漏，概不負任何法律責任。任何單位或個人認為本網(wǎng)站中的網(wǎng)頁或鏈接內容可能涉嫌侵犯其知識產權或存在不實內容時，應及時向本網(wǎng)站提出書面權利通知或不實情況說明，并提供身份證明、權屬證明及詳細侵權或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關文章源頭核實，溝通刪除相關內容或斷開相關鏈接。
