資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究可判定問題和不可判定問題解釋
在瞭解計算理論 (TOC) 中的可判定問題和不可判定問題之前，我們必須先了解可判定語言和不可判定語言。因此，讓我們首先看看可判定語言是什麼意思。
可判定語言
如果存在一個判定器 M 使得 L(M) = L，則語言 L 稱為可判定的。
給定一個判定器 M，您可以瞭解字串 w 是否屬於 L(M)。
在 w 上執行 M。
儘管可能需要很長時間，但 M 最終會接受或拒絕 w。
集合 R 是所有可判定語言的集合。
如果 L 可判定，則 L ∈ R。
不可判定語言
如果所有“是”例項到問題 P 的語言 L 不可判定，則決策問題 P 不可判定。
不可判定語言可能是部分可判定的，但不是可判定的。假設，如果一種語言甚至不是部分可判定的，那麼對於該語言不存在圖靈機。
問題
確定下面給出的問題是可判定的還是不可判定的。
“假設給定的輸入是一些圖靈機 M 和一些字串 w。問題是要確定機器 M 在輸入字串 w 上執行時，其讀寫頭是否會連續三次連續向左移動。”
解決方案
定義 M' 是一個圖靈機，它以 (M,w) 為輸入，其中 M 是 M' 識別的圖靈機，w 是 M 的輸入。
每當模擬的機器 M 在處理輸入 w 時將讀寫頭向左移動時，M' 停止並接受 (M,w)。
對於 M' 的特定輸入 (M,w)，構造圖靈機 P 為 -
P 在 (M,w) 上執行 M'
如果 M' 接受 (M,w)，則 P 停止並接受任何輸入。
我們試圖將通用圖靈機 U 歸約到 P，因為我們知道 L(U) 不可判定，並且我們也得出結論 L(P) 不可判定。因此，M' 不可判定。
證明是透過反證法。
假設這個問題是可判定的，然後我們必須證明改變圖靈機 (ATM) 也是可判定的 -
ATM = {M 是一個 TM，並且 M 接受 w}。
設 R 是一個判定左端問題的圖靈機。
也就是說，R 決定語言
leftmost = {M 在輸入 w 上嘗試將讀寫頭移到最左側磁帶單元格時，其讀寫頭位於最左側磁帶單元格}。
現在，想法是構造一個圖靈機 S，它以這樣一種方式決定 ATM，即它使用 R。
在輸入時，S 首先將機器 M 修改為 M'，以便僅當 M 接受其輸入時，M' 才將其讀寫頭從最左側單元格向左移動。
為了確保在計算過程中，M' 不會從最左側位置向左移動讀寫頭，
首先，機器 M' 將輸入 w 向右移動一個位置，並在最左側磁帶單元格上放置一個特殊符號。M' 的計算從讀寫頭位於第二個磁帶單元格開始。
在計算過程中，M' 嘗試將其讀寫頭移動到最左側磁帶單元格時，M' 透過讀取特殊符號來發現這一點，並將讀寫頭放回第二個單元格，並繼續執行。如果 M 進入接受狀態，則 M' 進入一個迴圈，迫使讀寫頭始終向左移動。
在 S 構造完 M' 後，它在輸入 <M'; w> 上執行判定器 R。
如果 R 接受，則 S 接受，否則如果 R 拒絕，則 S 拒絕。
因此，ATM 是可判定的，這是一個矛盾。
10K+ 次檢視
