可计算性和复杂性/形式语言/乔姆斯基层次/示例图灵机输入
这些示例用于在无限制语言底部提供的 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 _
此输入将导致机器永远运行而不会循环
_ _ _
此输入将被拒绝
_ = _