Coding Record

 

deterministic Turing machine(DTM) 確定性圖靈機 Nondeterministic Turing machine (NTM) 非確定性圖靈機 最早的有限狀態機。 狀態儲存關於過去的資訊，就是說：它反映從系統開始到現在時刻的輸入變化。 轉移指示狀態變更，並且用必須滿足確使轉移發生的條件來描述它。 動作是在給定時刻要進行的活動的描述。 有多種類型的動作： 進入動作（entry action）：在進入狀態時進行 退出動作（exit action）：在退出狀態時進行 輸入動作：依賴於當前狀態和輸入條件進行 轉移動作：在進行特定轉移時進行 非確定型圖靈機和確定型圖靈機的不同之處在於，在計算的每一時刻， 根據當前狀態和讀寫頭所讀的符號，機器存在多種狀態轉移方案， 機器將任意地選擇其中一種方案繼續運作，直到最後停機為止。 如果給予 Turing machine 某個 state 和某個 symbol 下，...