ペンローズ『皇帝の新しい心』の万能テューリング機械

万能テューリング機械の状態遷移図

皇帝の新しい心―コンピュータ・心・物理法則ペンローズ『皇帝の新しい心』（みすず書房 ; ISBN: 4622040964 ; 1994/12, 以下ENM）の万能テューリング機械（のための万能テューリング機械）をMathematicaで実装した。これは自己完結的な説明ではない。ENMを読んでいないと何をしているのかほとんどわからないと思う

用語：ユニバーサル（万能）・チューリング（テューリング）・マシン（機械），universal turing machine

変換テーブルの作成

2進数列の復号

まず、省略されている先頭の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]

万能テューリング機械（Mathematica）

ペンローズの方法で記述されたテューリング機械を与えるとそのとおりに振る舞う

10進数で機械を指定した場合

上記の方法で変換テーブルを作り、それにもとづくテューリング機械を動作させる

> 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だとおそらく遅くなる）

例（ENM p.61）

UN+1

> 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}

XN*2

> 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}

UN*2

> 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}

XN+1

> 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 （ユークリッドの互除法）

> 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で書いた万能テューリング機械に与えると、やはり万能テューリング機械として振る舞うような記述

10進数定義（ENM pp.65-66）

世界の究極理論は存在するか―多宇宙理論から見た生命、進化、時間ENM p.83には「私が計算したuの2進表現を10進形式に変換してくださったことで、デイヴィッド・ドイッチ氏にお礼を申し上げる」とある。こんなところで量子計算や『世界の究極理論は存在するか』で有名なドイッチが出てくるのは驚きである。彼にこんなことをやらせていいのだろうか。ここでは逆に次のように10進形式で与え（本から写せる）、2進形式に変換する

> u=7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613632359365644443458382226883278767626556144692814117715017842551707554085657689753346356942478488597046934725739988582283827795294683460521061169835945938791885546326440925525505820555989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234151056980262734686429921838172157333482823073453713421475059740345184372359593090640024321077342178851492760797597634415123079586396354492269159479654614711345700145048167337562172573464522731054482980784965126988788964569760906634204477989021914437932830019493570963921703904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498

2進数定義（ENM pp.83-85）

変換は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}}}

動作例

UN+1
> tm[u,
  Join[IntegerDigits[un1, 2],
    {1, 1, 1, 1, 1, 0},
    {1, 1, 1}]]

{{1, 1, 1, 1}, 0, 3301}

（ふつうにやった場合は4ステップで終わった）

XN*2
> 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ステップで終わった）

UN*2
> tm[u,
  Join[IntegerDigits[un2, 2],
    {1, 1, 1, 1, 1, 0},
    {1, 1, 1}]]

{{1, 1, 1, 1, 1, 1}, 0, 74158}

（ふつうにやった場合は25ステップで終わった）

XN*2
> 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

TOP