
ペンローズ『皇帝の新しい心』(みすず書房 ; ISBN: 4622040964 ; 1994/12,
以下ENM)の万能テューリング機械(のための万能テューリング機械)をMathematicaで実装した。これは自己完結的な説明ではない。ENMを読んでいないと何をしているのかほとんどわからないと思う
用語:ユニバーサル(万能)・チューリング(テューリング)・マシン(機械),universal turing machine
まず、省略されている先頭の110と末尾の110を付け加える。次に、{0 → 0, 1 → 10, R → 110, L → 1110, STOP → 11110}のルールで符号化された2進数列を復号する(ENM p.60-61)
> henkan[input_List]:=Module[{i=input,result={}},
i=Join[{1,1,0},i,{1,1,0}];
While[i=!={},
If[Length@i>4&&Take[i,5]==={1,1,1,1,0},
i=Drop[i,5];
AppendTo[result,STOP],
If[Length@i>3&&Take[i,4]==={1,1,1,0},
i=Drop[i,4];
AppendTo[result,L],
If[Length@i>2&&Take[i,3]==={1,1,0},
i=Drop[i,3];
AppendTo[result,R],
If[Length@i>1&&Take[i,2]==={1,0},
i=Drop[i,2];
AppendTo[result,1],
i=Drop[i,1];
AppendTo[result,0]]]]]];
result]
実装上の問題から、XN*2のようにルールの数が奇数だったら、{R}を補うことにする。これによってENMでは適切でなかった記述が適切なものになってしまうことはあり得るが、適切だったものの振る舞いは変わらない。たとえば7はENMでは「正しい仕様が与えられていない」が、ここでは与えられる(止まらないが)
> henkan2[i_List]:=
Module[{result={},start=1,end=1},
While[end<=Length@i,
If[i[[end]]===R||i[[end]]===L||i[[end]]===STOP,
AppendTo[result,Take[i,{start,end}]];
start=end+1];
end++];
If[OddQ@Length@result,AppendTo[result,{R}]];
Partition[
Prepend[Take[#,-2],FromDigits[Drop[#,-2],2]]&
/@
(result/.{
{R}->{0,0,R},
{L}->{0,0,L},
{STOP}->{0,0,STOP},
{1,R}->{0,1,R},
{1,L}->{0,1,L},
{1,STOP}->{0,1,STOP}})
,2]]
10進数から変換テーブルへ
> decToTable[n_Integer]:=henkan2@henkan@IntegerDigits[n,2]
ペンローズの方法で記述されたテューリング機械を与えるとそのとおりに振る舞う
上記の方法で変換テーブルを作り、それにもとづくテューリング機械を動作させる
> tm[n_Integer, rightTape_List, stepLimit_:Infinity]:=tm[decToTable@n, rightTape, stepLimit]
このテューリング機械は、装置の右側テープが入力で、停止時の装置の左側(装置の場所も含む)テープが出力になるような仕様である。停止すると装置の{左のテープ, 状態, ステップ数}を返す
> tm[transitionTable_List, rightTape_List, stepLimit_:Infinity] :=
Module[{
state = 0,
head = First@rightTape,
rTape = Rest@rightTape,
lTape = {},
direction, rule, step = 0,
tTable = transitionTable /. {R -> 0, L -> 1, STOP -> 2} (* 高速化のため *)
},
While[step < stepLimit,
step++;
rule = tTable[[state + 1, head + 1]];
state = rule[[1]];
head = rule[[2]];
direction = rule[[3]];
If[direction == 0, (* right move *)
AppendTo[lTape, head];
If[rTape === {}, head = 0,
head = First@rTape;
rTape = Rest@rTape],
If[direction == 1, (* left move *)
PrependTo[rTape, head];
If[lTape === {}, head = 0,
head = Last@lTape; (* 並び方を反対にして実装しても速くはならない *)
lTape = Drop[lTape, -1]],
Break[]]]];
If[step < stepLimit,
AppendTo[lTape, head];
{If[MemberQ[lTape, 1],
FixedPoint[If[First@# == 0, Rest@#, #] &, lTape],
{0}],
state, step},
{Null, Null, stepLimit}]]
テープは0と1のみだから算術化してリストでなく整数として実装したほうが速いと思うかもしれないが、そうしてもたいして変わらない。逆にテープが長くなってもリストなら遅くならないが整数だと遅くなってしまうかもしれない。高速化したければC++で書き直せばよい。上のtmをそのまま書き直すだけでも100倍程度速くなる(g++ 3.3の場合、なぜかlistのback操作よりもfront操作のほうが速いということがあるかもしれない。そういう場合にはfront操作だけを使うように書き直してほうがいい。ちなみにこの現象はg++ 3.3.2では再現できなかった)。Intel C++ ver.7ならlistではなくstringを使って実装したほうが速いだろう(g++ 3.3だとおそらく遅くなる)
> un1 = 177642;
> decToTable@un2
{{{0, 0, R}, {1, 1, R}},
{{0, 1, STOP}, {1, 1, R}}}
> tm[un1, {1, 1, 1}]
{{1, 1, 1, 1}, 0, 4}
> xn2 = 10389728107;
> decToTable@xn2
{{{0, 0, R}, {1, 0, R}},
{{0, 1, R}, {2, 0, R}},
{{3, 1, R}, {0, 0, R}},
{{0, 1, STOP}, {0, 0, R}}}
> tm[xn2, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0}]
{{1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1}, 0, 17}
> un2 = 1492923420919872026917547669;
> decToTable@un2 // ColumnForm
{{{0, 0, R}, {1, 0, R}},
{{2, 1, L}, {1, 1, R}},
{{3, 0, R}, {4, 0, R}},
{{0, 1, STOP}, {3, 1, R}},
{{5, 1, L}, {4, 1, R}},
{{2, 1, L}, {5, 1, L}}}
> tm[un2, {1, 1, 1}]
{{1, 1, 1, 1, 1, 1}, 0, 25}
> xn1 = 450813704461563958982113775643437908;
> decToTable@xn1
{{{0, 0, R}, {1, 1, R}},
{{0, 0, R}, {2, 1, R}},
{{3, 0, L}, {2, 1, R}},
{{0, 1, STOP}, {4, 0, L}},
{{5, 1, L}, {4, 1, L}},
{{6, 0, R}, {2, 1, R}},
{{0, 0, R}, {7, 1, R}},
{{3, 1, R}, {7, 0, R}}}
> tm[xn1, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1}]
{{1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1}, 0, 57}
> euc = 267556252842584231926905232066896095708779077170409889426;
> decToTable@euc
{{{0, 0, R}, {1, 1, L}},
{{2, 1, R}, {1, 1, L}},
{{10, 0, R}, {3, 0, R}},
{{4, 0, R}, {3, 1, R}},
{{4, 0, R}, {5, 0, R}},
{{7, 0, L}, {6, 1, L}},
{{6, 0, L}, {1, 1, L}},
{{7, 0, L}, {8, 1, L}},
{{9, 0, L}, {8, 1, L}},
{{2, 0, R}, {1, 1, L}},
{{0, 0, STOP}, {10, 1, R}}}
> tm[euc, {1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0}]
{{1, 1, 0}, 0, 235}
Mathematicaで書いた万能テューリング機械に与えると、やはり万能テューリング機械として振る舞うような記述
ENM p.83には「私が計算したuの2進表現を10進形式に変換してくださったことで、デイヴィッド・ドイッチ氏にお礼を申し上げる」とある。こんなところで量子計算や『世界の究極理論は存在するか』で有名なドイッチが出てくるのは驚きである。彼にこんなことをやらせていいのだろうか。ここでは逆に次のように10進形式で与え(本から写せる)、2進形式に変換する
> u=7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613632359365644443458382226883278767626556144692814117715017842551707554085657689753346356942478488597046934725739988582283827795294683460521061169835945938791885546326440925525505820555989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234151056980262734686429921838172157333482823073453713421475059740345184372359593090640024321077342178851492760797597634415123079586396354492269159479654614711345700145048167337562172573464522731054482980784965126988788964569760906634204477989021914437932830019493570963921703904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498
変換はMathematicaなら簡単(おそらくドイッチも同じように変換しただけだろう)
> BaseForm[u,2]
10000000010111010011010001001010101101000110100010100000110101001101000101010010110100001101000101001010110100100111010010100100101110101000111010101001001010111010101001101000101000101011010000011010010000010101101000100111010010100001010111010010001110100101010000101110100101001101000010000111010100001110101000010010011101000101010110101001010110100000110101010010110100100100011010000000011010000001110101001010101011101000010011101001010101010101011101000010101011101000010100010111010001010011010010000101001101001010010011010010001011010100010111010010010101110100101000111010100101001001110101010100001101001010101011101010010001011010100001011010100010011010101010100010110100101010010010110101001001011101010100101011101010010100110101010000111010001001001010111010101001010111010101000001110101001000001101010101001011101010010101101000100100011101000000011101001010010101010111010010100100101011101000001010111010000100011101000001010100111010000101001110100000100010111010001000011101000010010100111010001000010110100010100101110100010100101101001000001011010001010100100110100010101010111010010000011101001001010101011101010101001101001000101011010010010010110100000001011010000010001101000001001011010000000001101001010001011101001010100011010010100101011010000010011101001010100101101001001110101000000101011101010000001101010100010101011010010101011010100001010111010100100101011101010001001011010100100001011101000000111010100100010110101001010011010101000101110101001010010111010101000001011101010100000101110100000011101010100001010111010010101011010101000010111010100010101011101010100100101110101010100001110101000000011101001001000011010010010001011010101010100111010000000010110100100001101010101010010111010010000110100100010101011101000010001110100010000111010000110100000001011010000010010111010101001010101101000100010010111010000010011101010100110100000101010110100001000011101001000010001110101010101010011101000010010011101000100100001110100001010010110100001010000111010101010101011101000100100110100010010011010100101001011101000100010101110100000001110100010010010111010011010010010000101101010101001101000101000101110100001101010000100010110101001101010100101001011010101001101001001010111010011010010000010110100010101010001110100100001010110100000010011010010001001011101001000011010100000100101110100100101001101001001010101101001101001001010010110100110100101000001011010010000011101010010011010101010000101110100101000010111010010101010111010100010010110100100111010010101000101110100010011101010000101101001001110100101010101011101001000111010010101010010111010010001110101000001010101110011010100000101101001001110101000000101110100101101010000010101101001010010111010100001001011101000011010100010000101101010011010100010001011010101010010111010100010100101101000101010101110100100001010110101000101110101001001010101110101010010010111010100011101010001110101001001001011101010001110101001010001011101010001011101010000100101110101000111010001010001011101001010010111010100101010010111010010101010101011010100001010101011010000100111010000101010101011101010100010101110101010001010111010000001110101010001001011101000000111010101001000101110101000000110101000010110100000011101001000000101110101000111010100100010101110101001101010101000101011010000011010101010010101011010000001001101010101001001110101001101010101001001011010100110100100100111010000011010101010100101011010100010011010001010010101011101000001101010101010100101101000100011101000101010101010110100010001110100001010111010001001000011101001101000000010011101000000100101110100010001010011101000000100101110100101010101001011010000101010101110100010010100101110100000100010111010101001011010001000100111010000010010101110100000010101011010000100011100111101000010000011101000010010011101000001010010111010000010100101101000010001010111010000100010011010001000011101011110100001001001011101000010010010111010000000101011101000010101000110100010010111010000100000111010000100111010001000001011101010100101101000100000101110100001010101011101000000101010111010001000010101110100010000101011101001000001110101001001001101000000101011101000100010010111010101000011101010010101101001010101000011010000010100110100000001110100000100100111010010110100100010100101101010100110100010100100101101010100110100010101000101100110101001001011101010100110100010101010101100110101000101010110011010010001010101011101000100011101001001010101010110100101001010001101001000000101110100000110101010010101010110100101010110100100010001011101000101010110101000001010110100010000011010010001010110100001001110101001010101010111010010110100100100010101100110100100100101010111010011010010010010101101001011010010010010010110100101101001001010001011001101001001010010101110100010101110100100101110011010010010101001011100110100101000101010111010001000111010000101001011010010100010111010010100010101101000100111010010100010010111010001001110100101001000101110011010010001000111010001001110100101001010101110011010010100000111001101010101010110100000001110100101010010101011101001000111010010101001010111001101000010100100110011010100000110100000001110100101010100101011100110101000100001101000000011101000100101010101110100010001110101010101010101011010000100111010010001001010111010010101000100110101000000010110100100111010100001010111010010000110101000000010110100100011101010010010111010000110101000010101011010100010111010100001010010111010100010111010100010101010111001101010001010110100001101010001001010
次の方が重要だろう。「また、氏が次のことを確かめてくださったことにもお礼を申し上げなくてはならない。uのこの2進数値は確かに万能テューリング機械をもたらす。」 “人間”が確かめたのである
膨大な状態数
> Length@decToTable@u 201
> decToTable@u
{{{0, 0, R}, {128, 1, L}},
{{1, 0, R}, {75, 1, R}},
{{2, 0, R}, {152, 0, R}},
{{3, 0, R}, {78, 1, R}},
{{4, 0, R}, {77, 1, R}},
{{5, 0, L}, {90, 1, L}},
{{6, 0, L}, {117, 1, L}},
{{7, 0, R}, {153, 1, R}},
{{8, 0, R}, {161, 1, R}},
{{9, 0, L}, {177, 1, L}},
{{10, 0, L}, {184, 1, L}},
{{11, 0, R}, {68, 0, L}},
{{12, 0, L}, {197, 0, L}},
{{19, 1, R}, {13, 1, R}},
{{8, 0, R}, {14, 1, R}},
{{42, 0, R}, {64, 0, R}},
{{16, 0, L}, {55, 1, L}},
{{17, 0, L}, {191, 1, L}},
{{35, 1, L}, {140, 1, L}},
{{19, 0, R}, {163, 0, R}},
{{45, 0, R}, {20, 1, R}},
{{12, 1, L}, {21, 1, L}},
{{22, 0, L}, {109, 0, L}},
{{60, 0, R}, {23, 1, L}},
{{52, 1, R}, {24, 1, R}},
{{25, 0, R}, {124, 1, R}},
{{186, 1, R}, {26, 1, L}},
{{29, 1, L}, {27, 0, R}},
{{28, 0, L}, {149, 1, L}},
{{29, 1, L}, {56, 0, L}},
{{104, 0, R}, {30, 1, L}},
{{13, 1, R}, {74, 0, L}},
{{32, 0, L}, {183, 1, L}},
{{181, 1, L}, {33, 1, L}},
{{34, 0, L}, {135, 0, L}},
{{35, 0, L}, {132, 1, L}},
{{36, 0, L}, {139, 0, L}},
{{72, 1, R}, {38, 1, L}},
{{38, 1, R}, {80, 1, R}},
{{157, 0, R}, {39, 1, L}},
{{40, 0, L}, {87, 1, L}},
{{15, 0, R}, {41, 1, R}},
{{42, 1, R}, {64, 1, R}},
{{66, 0, R}, {66, 1, R}},
{{128, 0, R}, {44, 1, L}},
{{46, 0, R}, {45, 1, R}},
{{33, 0, L}, {46, 1, R}},
{{5, 0, L}, {193, 1, L}},
{{48, 0, R}, {115, 1, R}},
{{11, 1, R}, {49, 1, L}},
{{53, 1, L}, {50, 1, R}},
{{104, 1, L}, {16, 0, L}},
{{52, 1, R}, {27, 0, R}},
{{28, 1, L}, {54, 1, L}},
{{112, 1, L}, {112, 1, L}},
{{16, 0, L}, {113, 1, L}},
{{11, 1, R}, {56, 1, L}},
{{51, 1, L}, {58, 1, L}},
{{60, 0, L}, {96, 0, L}},
{{84, 0, R}, {84, 1, R}},
{{31, 0, L}, {128, 1, R}},
{{20, 0, R}, {62, 1, L}},
{{20, 0, R}, {83, 1, L}},
{{34, 0, L}, {36, 0, L}},
{{4, 0, R}, {64, 1, R}},
{{66, 1, L}, {59, 1, R}},
{{146, 1, L}, {33, 0, L}},
{{7, 0, R}, {67, 1, R}},
{{68, 0, L}, {162, 0, L}},
{{63, 0, L}, {69, 0, L}},
{{148, 0, L}, {70, 1, R}},
{{140, 0, L}, {31, 1, L}},
{{37, 0, R}, {37, 0, R}},
{{54, 1, L}, {73, 1, L}},
{{32, 0, L}, {74, 1, L}},
{{1, 0, R}, {168, 1, R}},
{{15, 0, R}, {76, 1, L}},
{{4, 0, R}, {196, 1, R}},
{{3, 0, R}, {118, 1, R}},
{{7, 0, R}, {21, 1, L}},
{{1, 0, R}, {80, 1, R}},
{{158, 0, L}, {81, 1, R}},
{{65, 0, R}, {82, 1, L}},
{{20, 0, R}, {194, 1, L}},
{{43, 0, R}, {43, 1, R}},
{{1, 0, R}, {86, 1, R}},
{{1, 0, R}, {176, 1, R}},
{{40, 0, L}, {13, 0, R}},
{{120, 1, L}, {88, 1, L}},
{{23, 1, L}, {50, 1, R}},
{{5, 0, L}, {92, 1, L}},
{{9, 0, L}, {24, 1, R}},
{{5, 0, L}, {47, 1, L}},
{{10, 0, L}, {94, 1, L}},
{{10, 0, L}, {195, 1, L}},
{{0, 0, R}, {48, 1, R}},
{{5, 0, L}, {96, 1, L}},
{{2, 1, R}, {97, 1, R}},
{{22, 1, L}, {98, 1, L}},
{{4, 0, R}, {200, 1, R}},
{{3, 0, R}, {100, 1, R}},
{{30, 1, L}, {102, 1, R}},
{{39, 1, L}, {81, 1, R}},
{{12, 1, L}, {107, 1, L}},
{{58, 1, L}, {6, 0, L}},
{{6, 0, L}, {106, 1, L}},
{{6, 0, L}, {108, 1, L}},
{{12, 1, L}, {98, 1, L}},
{{6, 0, L}, {76, 1, L}},
{{22, 1, L}, {110, 1, L}},
{{95, 1, R}, {199, 1, R}},
{{17, 0, L}, {143, 1, L}},
{{57, 1, L}, {57, 1, L}},
{{16, 0, L}, {114, 1, L}},
{{16, 0, L}, {116, 1, L}},
{{48, 0, R}, {24, 1, R}},
{{16, 0, L}, {160, 1, L}},
{{6, 0, L}, {105, 1, L}},
{{3, 0, R}, {121, 1, R}},
{{8, 0, R}, {123, 1, R}},
{{65, 0, R}, {61, 0, L}},
{{3, 0, R}, {122, 1, R}},
{{3, 0, R}, {21, 0, L}},
{{8, 0, R}, {125, 1, R}},
{{25, 0, R}, {155, 1, L}},
{{8, 0, R}, {126, 1, R}},
{{18, 0, L}, {159, 1, R}},
{{18, 0, L}, {17, 1, L}},
{{148, 0, L}, {1, 0, R}},
{{129, 0, L}, {130, 1, L}},
{{147, 0, L}, {130, 1, L}},
{{190, 1, R}, {71, 1, L}},
{{150, 1, L}, {132, 1, L}},
{{14, 1, R}, {73, 0, L}},
{{133, 1, L}, {131, 1, R}},
{{34, 0, L}, {0, 0, STOP}},
{{136, 0, L}, {69, 0, L}},
{{134, 1, L}, {134, 1, R}},
{{137, 1, L}, {137, 0, R}},
{{36, 0, L}, {0, 1, STOP}},
{{138, 1, L}, {138, 1, L}},
{{129, 1, L}, {142, 0, R}},
{{18, 1, L}, {136, 0, L}},
{{17, 0, L}, {144, 1, L}},
{{14, 1, R}, {144, 1, L}},
{{71, 1, L}, {131, 1, L}},
{{145, 1, L}, {145, 1, L}},
{{40, 0, L}, {53, 0, R}},
{{65, 1, L}, {146, 1, L}},
{{28, 0, L}, {13, 1, R}},
{{188, 0, R}, {67, 0, R}},
{{32, 0, L}, {133, 0, L}},
{{2, 1, R}, {166, 1, R}},
{{7, 0, R}, {154, 1, R}},
{{7, 0, R}, {156, 1, R}},
{{0, 0, R}, {26, 1, L}},
{{7, 0, R}, {79, 1, R}},
{{0, 0, R}, {51, 1, R}},
{{0, 0, R}, {167, 1, L}},
{{18, 0, L}, {175, 1, R}},
{{182, 0, R}, {160, 1, L}},
{{8, 0, R}, {119, 1, R}},
{{11, 1, R}, {164, 1, L}},
{{19, 1, R}, {97, 1, R}},
{{72, 0, R}, {41, 1, R}},
{{17, 0, L}, {111, 1, L}},
{{2, 1, R}, {169, 1, R}},
{{0, 0, R}, {171, 1, L}},
{{1, 0, R}, {85, 1, R}},
{{2, 1, R}, {170, 1, R}},
{{2, 1, R}, {172, 1, R}},
{{0, 0, R}, {173, 1, L}},
{{9, 1, L}, {10, 1, L}},
{{0, 0, R}, {174, 1, L}},
{{0, 0, R}, {179, 1, L}},
{{18, 0, L}, {70, 1, R}},
{{44, 1, L}, {89, 1, R}},
{{9, 0, L}, {178, 1, L}},
{{9, 0, L}, {180, 1, L}},
{{0, 0, R}, {82, 0, L}},
{{9, 0, L}, {91, 1, L}},
{{0, 0, R}, {88, 0, L}},
{{0, 0, R}, {15, 1, R}},
{{32, 0, L}, {187, 1, L}},
{{10, 0, L}, {93, 1, L}},
{{0, 0, R}, {141, 0, R}},
{{0, 0, R}, {24, 0, R}},
{{32, 0, L}, {189, 1, L}},
{{0, 0, R}, {100, 0, R}},
{{32, 0, L}, {151, 1, L}},
{{18, 0, L}, {127, 1, R}},
{{17, 0, L}, {165, 1, L}},
{{185, 0, R}, {192, 1, R}},
{{5, 0, L}, {49, 1, L}},
{{20, 0, R}, {192, 1, R}},
{{10, 0, L}, {26, 1, L}},
{{4, 0, R}, {99, 1, R}},
{{12, 1, L}, {198, 1, L}},
{{12, 1, L}, {103, 1, L}},
{{0, 0, R}, {25, 1, R}},
{{4, 0, R}, {101, 1, R}}}
> tm[u,
Join[IntegerDigits[un1, 2],
{1, 1, 1, 1, 1, 0},
{1, 1, 1}]]
{{1, 1, 1, 1}, 0, 3301}
(ふつうにやった場合は4ステップで終わった)
> tm[u,
Join[IntegerDigits[xn2, 2],
{1, 1, 1, 1, 1, 0},
{1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0}]]
{{1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1}, 0, 11299}
(ふつうにやった場合は17ステップで終わった)
> tm[u,
Join[IntegerDigits[un2, 2],
{1, 1, 1, 1, 1, 0},
{1, 1, 1}]]
{{1, 1, 1, 1, 1, 1}, 0, 74158}
(ふつうにやった場合は25ステップで終わった)
> tm[u,
Join[IntegerDigits[xn1, 2],
{1, 1, 1, 1, 1, 0},
{1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1}]]
{{1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1}, 0, 156960}
(ふつうにやった場合は57ステップで終わった)
ペンローズによるテューリング機械の記述を解釈できるような万能テューリング機械tmに、万能テューリング機械Aの記述aとAへの入力bを与える。aがuだとするとAは万能テューリング機械になる。Aが万能テューリング機械ならば、Aへの入力(つまりb)はテューリング機械Cの記述cとCへの入力dからなる。cがuだとするとCは万能テューリング機械になる。Cが万能テューリング機械ならば、Cへの入力(つまりd)はテューリング機械Eの記述eとEへの入力fからなる。EがUN+1でfが{1,1,1}であるように全体を構成することはできるだろうか?
ヒント: できるならステップ数は25億程度になるだろう
ヒントではないけど、Mathematicaだけなら簡単。最終的にはたぶんこんな感じ
ReleaseHold[Hold[ReleaseHold[#1[#2]] &][Hold[Hold[ReleaseHold[#1[#2]] &], Hold[Hold[#1 + 1 &], 1]]]]
同じくLispだけの場合も簡単。ちょっと違うけどだいたいこんな感じ
(EVAL '((LAMBDA (X) (EVAL X)) '((LAMBDA (X) (EVAL X)) '((LAMBDA (X) (+ X 1)) '1))))
updated in 2003.10.31