Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample TM inputs
Sample TM inputs edit
These examples are for use with the perl TM emulator provided at the bottom of Unrestricted Languages. That page also contains a description of what a TM is and how it works.
This machine accepts strings of the form . It creates a new string of ones whose size is the multiple of the sizes of the original two, then it halts and accepts. In essence, it is a multiplying machine. If only one string of ones is present, then the size of the resulting string will be zero.
Note that with this TM emulator, new tape sections are initialized to _, so _ is essentially a blank character.
: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
Some sample inputs:
These accept:
_ 1 1 _ 1 1 1 1 _
_ 1 1 1 1 1 _ 1 _
This input will cause the machine to run forever without looping:
_ _ _
This input will reject:
_ = _