Jump to content

Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample TM inputs

From Wikibooks, open books for an open world

Sample TM inputs

[edit | edit source]

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:

_ = _

back