停机问题和無窮迴圈

快捷方式: 差异，相似，杰卡德相似系数，参考。

停机问题和無窮迴圈之间的区别

停机问题 vs. 無窮迴圈

停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个 s \in S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不自洽性和不完备性，类似的命题有理发师悖论、全能悖论等。. 無窮迴圈（infinite loop）或稱為无限循环，是指程式的控制流程一直在重複執行某一段程式碼，無法結束的情形，其原因可能是因為程式中的迴圈沒有設結束迴圈條件，或是結束迴圈的條件不可能成立等。在合作式多工（cooperative multitasking）的作業系統中，無窮迴圈會使系統沒有反應，若是先占式（preemptive）多工的系統中，無窮迴圈會用掉所有可用的處理器時間，不過可以由使用戶結束程序。無窮迴圈是造成系統假死機的原因之一，其他的可能原因包括死鎖或是記憶體區段錯誤。 忙碌等待迴圈是在外界特定條件時（例如有按鍵輸入）才會離開的迴圈，有時忙碌等待迴圈也被稱為是無窮迴圈，但此情形和上述的不太一様。忙碌等待迴圈可以藉由外界事件而結束迴圈，但上述的無窮迴圈是無法結束的。.

程序

程序（procedure），指特定的一系列動作、行動或操作，而這些活動、動作或操作必須以相同方式執行，藉此在相同環境下恆常得出相同的結果（例如緊急應變程序）。粗略而言，程序可以指一序列的活動、作業、步驟、決斷、計算和工序，當它們保證依照嚴格規定的順序發生時即產生所述的後果、產品或局面。一個程序通常引致一個改變。現在小孩也可以寫程式。.

停机问题和程序 · 無窮迴圈和程序 · 查看更多 »

艾伦·图灵

艾伦·麦席森·图灵，OBE，FRS（Alan Mathison Turing，又译阿兰·图灵，Turing也常翻譯成--林或者杜林，）是英国計算機科學家、数学家、邏輯學家、密码分析学家和理论生物学家，他被视为计算机科学與人工智慧之父。 在第二次世界大战期间，图灵曾在“政府密码学校”（GC&CS，今政府通信总部）工作。政府密码学校位于布萊切利園，是英国顶级机密情报机构。图灵在这里从事密码破译工作，有一段时间，他领导了（Hut 8）小组，负责德国海军密码分析。 期间他设计了一些加速破译德国密码的技术，包括改进波兰战前研制的机器，一种可以找到恩尼格玛密码机设置的机电机器。 图灵在破译截获的编码信息方面发挥了关键作用，使盟军能够在包括大西洋战役在内的许多重要交战中击败纳粹，并因此帮助赢得了战争。 图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为《》的论文，提問「机器会思考吗？」（Can Machines Think?），作為一种用于判定机器是否具有智能的测试方法，即图灵测试。至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。 图灵是著名的男同性恋者，并因为其性倾向而遭到当时的英国政府迫害，职业生涯尽毁。他亦患有花粉过敏症。 图灵还是一位世界级的长跑运动员。他的马拉松最好成绩是2小時46分03秒（手動計時），比1948年奥林匹克运动会金牌成绩慢11分钟。1948年的一次跨国赛跑比赛中，他跑赢了同年奥运会银牌得主。.

停机问题和艾伦·图灵 · 無窮迴圈和艾伦·图灵 · 查看更多 »