TOC 中圖靈機的變體有哪些？

圖靈機 (TM)也可以是確定性或非確定性的，但這並不會使它們更強大或更弱。

然而，如果磁帶受到限制，你只能看到使用輸入部分的磁帶，那麼圖靈機就會變得不那麼強大(線性有界自動機)，並且只能識別上下文敏感語言。

許多其他的圖靈機變體都等價於原始的圖靈機。這包括以下內容：

  • 多軌

  • 多磁帶

  • 多磁頭

  • 多維磁帶

  • 離線圖靈機

多磁帶圖靈機

具有多個磁帶的圖靈機，我們稱之為多磁帶圖靈機。

每個磁帶都有自己的讀/寫磁頭。

對於 N 磁帶圖靈機

M={( Q,X, ∑,δ,q0,B,F)}

我們定義

δ=QxXN -> Q x XN x {L,R}N

示例

如果 n=2，當前配置 δ(q0,a,e)=(q1,X,Y,L,R)

δ=QxXN -> Q x XN x {L,R}N

非確定性圖靈機

它類似於確定性圖靈機，除了對於任何輸入和當前狀態，它都有多個選擇。

如果存在一系列移動導致最終狀態，則字串被 NDTM 接受。

轉移函式：

=Q x X -> 2QxXx(L,R)

NDTM 允許對於給定的磁帶符號具有多個轉移。

多磁頭圖靈機

它有多個磁頭而不是一個。

每個磁頭獨立地讀取/寫入符號並向左/右移動或保持靜止。

離線圖靈機

離線圖靈機有兩個磁帶，如下所示：

  • 一個磁帶是隻讀的，包含輸入。

  • 另一個是讀寫的，最初是空白的。

更新於：2023-11-04

33K+ 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告