可計算性和複雜性/形式語言/喬姆斯基層次/示例圖靈機輸入
這些示例用於在無限制語言底部提供的 Perl 圖靈機模擬器中使用。該頁面還包含關於圖靈機是什麼以及它如何工作的描述。
該機器接受形式為的字串。它建立一個新的“1”字串，其大小是原始兩個字串大小的倍數，然後它停止並接受。本質上，它是一個乘法機器。如果只有一個“1”字串存在，則結果字串的大小將為零。
請注意，使用此圖靈機模擬器，新的磁帶部分被初始化為 _，因此 _ 本質上是一個空白字元。
:States: start passFirst readSecond passSecond writeThird passThirdLeft passSecondLeft resetSecond readSecond passFirstLeftA passFirstLeftB clearSecondA clearSecondB halt :Start State: start :Accept States: halt :alphabet: _ 1 + = :rules: start 1 passFirst _ right start _ start _ right passFirst 1 passFirst 1 right passFirst _ readSecond _ right readSecond 1 passSecond + right readSecond + readSecond + right readSecond _ resetSecond _ left passSecond 1 passSecond 1 right passSecond _ writeThird _ right writeThird 1 writeThird 1 right writeThird _ passThirdLeft 1 left passThirdLeft 1 passThirdLeft 1 left passThirdLeft _ passSecondLeft _ left passSecondLeft 1 passSecondLeft 1 left passSecondLeft + readSecond + right resetSecond + resetSecond 1 left resetSecond _ passFirstLeftA _ left passFirstLeftA 1 passFirstLeftB 1 left passFirstLeftA _ clearSecondA _ right passFirstLeftB 1 passFirstLeftB 1 left passFirstLeftB _ start _ right clearSecondA _ clearSecondB _ right clearSecondB 1 clearSecondB _ right clearSecondB _ halt = left
一些示例輸入
這些被接受
_ 1 1 _ 1 1 1 1 _
_ 1 1 1 1 1 _ 1 _
此輸入將導致機器永遠執行而不會迴圈
_ _ _
此輸入將被拒絕
_ = _