關鍵點和可判定性的重要性

Question

語言是可判定的如果TM識別語言並進入接受或拒絕狀態。作爲開發者。我認爲這很重要，因爲這意味着我們可以確定程序是否包含緩衝區溢出或死鎖。此外，下列問題是不可判定的：

• 程序是否曾經訪問未初始化的變量。
• 兩個上下文無關文法是否描述相同的語言。
• 是否有所作爲，如果參數子程序通過引用或複製的結果通過

在你會說什麼都是可判定的關鍵點，爲什麼是可判定的重要判定性方面（尤其是一個開發者）。

注意：子彈點在答案上很好 - 我可以自己查看這些主題。我只想知道什麼是主要觀點。

Answer 1

也許這屬於cstheory exchange，但我會盡力去做。關鍵點是：有些問題是不可判定的，即不能通過算法解決，因此應該通過其他方法來解決。在這些問題中有很多涉及計算機語言的「元問題」，例如detecting a virus的問題。

已經確定的一個問題是不可判定的，有作用的幾個可能的課程：

1. 某些問題可能是半可判定，即存在半 -algorithm，解決了一些案件，但環永遠在其他情況下。當執行半算法時，在其上放置一個定時器，並在時間用完時返回no answer。
2. 通過簡化問題解決問題，希望解決問題的關鍵部分。
3. 2 +當問題變得太複雜時，要求用戶輸入。
4. 使用啓發式，得到正確答案大部分的時間。
5. 使用不同的語言，也許是非圖靈完整的語言。

1到3是流行的自動推理工具，包括程序驗證程序。 4是病毒掃描程序所做的。 5是允許用戶編寫腳本以自動執行更大系統時的good choice;而不是給他們完整的JavaScript/Scheme/Lua /任何，給他們一個限制子集，不允許無限遞歸/循環。

Answer 2

假設您必須編寫一些滿足條件的軟件：「在運行時，任何函數都不會直接或間接地調用它自己」。

該條件將是不可判定的，但更嚴格的條件可能是可判定的，例如：「不應使用函數指針並且函數不得包含直接或間接調用自身」。

這是爲了強調有時可以交易可判定性的靈活性，以便系統的某些必需屬性可以強制執行。

如果一種編程語言是可確定的，那麼總是可以決定一個程序是否是該語言的有效程序。

但即使一個程序是該語言的有效程序，它仍然是不可判定的，無論該程序是否會導致緩衝區溢出或死鎖。