A machine that multiplies two strings of ones and accepts if it completes: :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:

http://cs.marlboro.edu/ courses/ fall2006/ tutorials/ chomsky_hierarchy/ Sample_TM_inputs
last modified Friday November 10 2006 9:10 am EST