halting-problem

0熱度

1回答

我陷入了一個問題，並希望對解決方案有一點指導。我需要證明的是，接下來的問題是不可判定：輸入 - 一種程序問題 - 是否爲其程序暫停可能輸入的數量比那些該節目贏得了」大停止？我試圖建立一個減少（如果輸入是偶數）每個偶數停止，對每個奇數進行無限循環，並用輸入運行程序。或者，如果輸入是奇數，則相反 - 但它只在我能夠證明實際奇數的數量等於實數偶數時纔有效。

0熱度

1回答

流星 - 檢測無限循環

下面是一些代碼（具有相關聯的數據），用於計數東西流星應用的本質。計數可以連接在一起，這樣一是可以增加另： // The counting and linking code. Meteor.methods({ 'counts.increment'(countId) { const count = Counts.findOne(countId); Counts.up

1熱度

1回答

基於啓發式的病毒檢測如何實現？

停機問題指出，這是不可能的一個程序來預測的另一個輸出，或是否將被終止。這讓我想......怎麼辦啓發式爲主的掃描儀決定一個給定的可執行程序的指令是否是「病毒式」，看到這將完全涉及預測哪些程序該怎麼辦？

1熱度

1回答

「haltingproblem」矛盾證明

我最近碰到了停止問題的矛盾證明。在證明中，我們必須爲圖靈機提供一份程序副本和一份輸入副本，以決定程序是否停止輸入。在矛盾中，爲什麼它必須作爲程序和輸入的程序？對不起，如果聽起來很混亂。我可以簡單地給機器提供程序和隨機輸入，並得出相同的結論。有誰能告訴我爲什麼？有沒有我沒有想到的具體原因？

0熱度

2回答

非確定性運行時間真的很糟糕嗎？

當我在這裏談論暫停問題時，聽起來好像不可終止是需要避免的，暫停問題使得不可能知道程序/算法是否好。但是，當我仔細想想，不終止程序的異常，沒有規則？我可以想到一類應用程序在預計在有限的時間內終止：編譯器。從我正在使用的Web瀏覽器到桌面環境，文本編輯器，shell，服務器託管SO，到操作系統本身，其他一切都不應該自行終止。哎呀，即使是包管理者也應該要求用戶確認。除非用戶或系統管理員另有說明，否則它

2熱度

1回答

'試' 可以決定當一個程序暫停

我有這樣的功能： isUndefined ::() -> Bool isUndefined x = case unsafePerformIO $ (try (return $! x) :: IO (Either SomeException())) of Left _ -> True Right _ -> False 則： isUndefined() =

3熱度

2回答

圖靈機停機問題

我正在尋找圖靈機停機問題的簡單解釋。我對這個話題很陌生，但我知道TMs是如何工作的基礎，他們是如何枚舉事物，機器配置等的，但我沒有很好地處理暫停問題。有人可以提供一個很好的解釋這個話題嗎？

0熱度

1回答

對於某些有限功能，可以停止使用嗎？

這是我的理解是十分簡單的功能，讓我們說 function(boolean input){ while(input){ } } 就可以判斷它會阻止任何可能的輸入。很容易看出上述函數將終止爲false，而不是終止於haltingFinder（haltingFinder），並且本質上會產生一個悖論。我的理解是否正確？

0熱度

1回答

證明TM和DFA的等價性

我試圖用停止問題的減少來證明TM = DFA是不可判定的理論上我明白圖靈機捕獲所有可計算函數，而DFA只捕獲可以常量計算的函數因此TM = DFA是不可判定的。這裏是我的步驟：假設是R那個決定L（M）= L（d） EQ_DM = {[d，M] | L（M）= L（d）} 和我們創建一個圖靈機 HALT_TM = {[M，W] | （在輸入砂→M停止接受中號沒有輸入停止波→拒絕）} 如何構建一

3熱度

1回答

停止問題是否意味着程序無法檢查其他程序？

我正在參加理論課，我們剛剛討論了暫停問題。在我的理解，這個問題不能得到解決的原因是，如果有一個程序暫停，告訴我們沒有一個程序是否會停機，而你寫另一個程序證明這樣 function Proof (program, input) if (Halt(program, input)) loop infinitely; else return 1 對我來說，癥結問題在於if條件是程序無限循環，這是