資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究圖靈機中可識別和可判定之間的區別是什麼？
當我們談論圖靈機 (TM) 時，它可以接受輸入、拒絕輸入或繼續計算，這稱為迴圈。
現在，當提供的輸入屬於該語言時，當且僅當圖靈機接受該字串時，語言才是可識別的。
此外，如果圖靈機終止並拒絕字串或根本不終止，則語言可以被識別。這意味著當提供的輸入不屬於該語言時，圖靈機將繼續計算。
而語言是可判定的，當且僅當存在一臺機器，當提供的輸入屬於該語言時接受該字串，而當提供的輸入不屬於該語言時拒絕該字串。
示例
A = {hM, wi | M 是一個 DFA 且 w ∈ L(M)} 是可判定的。
A = {hM, wi | M 是一個 TM 且 w ∈ L(M)} 是可識別的。
圖靈機中可識別和可判定的主要區別如下：
| 序號 | 圖靈可識別 | 圖靈可判定 |
|---|---|---|
| 1 | 如果存在一臺機器只停機並接受該語言中的字串，而不接受該語言之外的字串，則該語言是圖靈可識別的；對於不在該語言中的字串，該圖靈機要麼拒絕，要麼根本不停止。 | 如果存在一臺機器接受語言中的字串並拒絕語言之外的字串，則稱該語言是可判定的。 |
| 2 | 如果某個圖靈機識別某個語言，則該語言稱為圖靈可識別。 | 如果某個圖靈機判定某個語言，則該語言稱為圖靈可判定。 |
| 3 | 如果存在一個圖靈機，當遇到該語言中的字串時，該機器會終止並接受該字串，那麼我們可以說這種型別的語言是圖靈可識別的。 | 如果存在一個圖靈機，當遇到該語言中的字串時，該機器會終止並接受該字串，那麼我們說這種型別的語言是圖靈可判定的。 |
| 4 | 如果存在一個圖靈機，當遇到該語言中不存在的字串時，該機器要麼終止並拒絕該字串，要麼根本不終止，那麼我們可以說它是圖靈可識別的。 | 如果存在一個圖靈機，當遇到該語言中不存在的字串時，該機器會終止並拒絕該字串，那麼我們可以說它是圖靈可判定的。 |
| 5 | 它不是比圖靈可判定更強的條件。 | 它是比圖靈可識別更強的條件。 |
更新於：2021年6月16日
12K+ 次瀏覽
廣告