以下のチューリングマシンを作成できるか試してみましょう．
Exercise t1: anbn
文字aとbからなる長さ2以上の文字列xが入力された時に，いくつかの連続したaの後に同数のbが続く文字列である場合に終了状態で停止するチューリングマシンを作成しなさい．
ab -> 受理
abab -> 拒否
aaab -> 拒否
bbaa -> 拒否
aabb -> 受理
aaabb -> 拒否
aaabbb -> 受理
作成したチューリングマシンは「デスクトップ」に保存します．ファイル名は「t1.txt」とします．
Exercise t2: equal
文字aを0, 文字bを1の代わりに使います．正の整数 x と y を2進数で表し(最上位は必ずb(1の代わり))文字列をそれぞれs
x, s
yとします．文字列s
xcs
y を入力として，x = y の時にのみ終了状態で停止するチューリングマシンを作成しなさい(x, y の文字列表現は一意に表せるので，文字列としてs
xとs
yが等しいと判定することができます)．
bbcbaa -> 拒否 (3 != 4)
bbbcbaa -> 拒否 (7 != 4)
babcbab -> 受理 (5 == 5)
bcb -> 受理 (1 == 1)
作成したチューリングマシンは「デスクトップ」に保存します．ファイル名は「t2.txt」とします．
Exercise t3: greater
文字aを0, 文字bを1の代わりに使います．正の整数 x と y を2進数で表し(最上位は必ずb(1の代わり))文字列をそれぞれs
x, s
yとしなさい．文字列s
xcs
y を入力として，x > y の時にのみ終了状態で停止するチューリングマシンを作成しなさい．
bbcbaa -> 拒否 (11(2) = 3 < 4 = 100(2))
bbbcbaa -> 受理 (111(2) = 7 > 4 = 100(2))
babcbab -> 拒否 (101(2) = 5 = 101(2))
baaacbbb -> 受理 (1000(2) = 8 > 7 = 111(2))
作成したチューリングマシンは「デスクトップ」に保存します．ファイル名は「t3.txt」とします．