万能チューリングマシンの創り方

#自己紹介
こんにちは。ぱたろうです。Twitterはこちらです。
現在中学3年生のCPUアーキテクト(自称)です！
電磁石式自作CPUを複数機作って互いに接続させてネットワークにしたりしてました。
それに関する記事はこちらです！低レイヤに興味ある方はぜひ！

実はチューリングマシンが大好きです！

#はじめに
この章では、私のチューリングマシンに対する熱い気持ちを語るだけですので、興味のない方は #チューリングマシン・チューリング完全とは までとばしていただいて構いません。

私はチューリングマシンというものが大好きです。私がチューリングマシンに出会ったのは、2019年(中学二年生の時)の夏休みでした。

「チューリングマシン」や「チューリング完全」と言った言葉は、元々プログラミング言語の自作に興味があり(挫折しました😭)、プログラミング言語に必要な要素とは何かを調べているときにブチ当たった言葉でした。最初は「チューリングマシン、チューリング完全とはなんぞや！？」と、思っていたのですが、チューリングマシンは意外と簡単でした(チューリングマシンを理解したら誰でもチューリング完全を理解できるでしょう)。

チューリングマシンから自作CPUなどの低レイヤに興味を持ち、自作CPUができたからこそ未踏ジュニアにも応募して採択されたりで、チューリングマシンこそ私の原点だと思っています。
そこで！私としては実に二年(弱)ぶりにその原点に立ち返り、チューリングマシンを布教したいと考えているのです。

本記事では、チューリングマシン・チューリング完全を理解し、チューリングマシンを使った二進数の任意の数同士の足し算をしたり、万能チューリングマシンの自作までを目標にしたいと考えています。みなさんには是非ともチューリングマシンでのプログラミングを堪能してもらいたいのです！

チューリングマシン・チューリング完全とは

##チューリングマシン
チューリングマシンとは！それは、
「チューリングマシン (英: Turing machine) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である。」(出典:Wikipedia)
だそうです。
アラン・チューリングという人物が考えたこと以外何を言っているのだかさっぱりです😃

では！私がわかりやすく解説しましょう！
まず、チューリングマシンには下図のような無限に伸びるテープがあります！現実には無限に続くものなんてありませんが「抽象機械」というのは多分そういうことです。

テープの一マスには、"0", "1", " "の三種類(最後のは空白)を書き込むことができます。
そして、テープを読んでいくヘッドというのもあります。

ヘッドは「状態」という情報を常に保持していて、ヘッドはテープを読むたびに左や右に、もしくはそのまま止まったりすることができます。
どうやってヘッドの動きを制御しているのかと言えば、ヘッドは「状態遷移図」(状態遷移表と言ったりもする)というものに従って保持している「状態」の内容を変更したり、ヘッドを左右もしくはそのままにしたりしているのです。
つまり、状態遷移図はプログラミング言語でいう「コード」です。

状態遷移図は5つの情報から成っています。

1. 今の状態はこれですか？
2. 今テープから受け取った情報はこれですか？
3. 1. と2. が両方trueだった時、次の状態はこれにしてください。
4. 1. と2. が両方trueだった時、ヘッドがいる場所のテープをこれに書き換えてください。
5. 1. と2. が両方trueだった時、ヘッドをこっちに動かしてください。

ここでチューリングマシンにおけるプログラミングの例を示したいと思います。が、その前に、今後この記事で使う表記法(オレオレ法)を書かせてください。

テープとヘッド、状態の表記

例

00101-10
  ^
  A
  

• 一行目はテープです。空白は読みづらいので"-"で代用します。「8文字しかなくて有限じゃん」と、思うかもしれませんが、両端には無限に"-"が続いてると考えてください。
• 二行目はヘッドの位置です。今は1の場所にいます。
• 三行目はヘッドが保持している「状態」の中身です。今は"A"という状態を保持しています。

状態遷移図の表記

例

AA10R
AA00L
AB-0R
BH10S

状態遷移図はこんな感じで記述していきます。
この状態遷移図では4つの遷移が記述されています。三行目をみてみてください。
"AB-0R"と書かれていますね。

• 一文字目の"A"は、先程の説明で、1. です。
• 二文字目の"B"は、先程の説明で、3. です。
• 三文字目の"-"は、先程の説明で、2. です。
• 四文字目の"0"は、先程の説明で、4. です。
• 五文字目の"R"は、先程の説明で、5. です。RはRight(右), LはLeft(左), SはStop(その場に留まる)

四行目の二文字目が"H"ですが、状態が"H"になった時、チューリングマシンはHalt(停止)します。

表記法の説明は以上です！それではチューリングマシンのHello, World(適当)とも言うべく、「ヘッドを右に動かして、0を1に書き換えて行き、-を読んだら停止する状態遷移図」を書いてみましょう！

まず、テープには

テープ

01100-011
^
A

が、書き込まれているとしましょう(一番最初の状態はAとし、ヘッドも一文字目の場所にあるとします)。
で、私たちが結果として欲しいのは

結果

11111-011
     ^
     H

これですよね！(最後のヘッドの位置は、先程の表記法の五文字目がSの場合です。別にそこをRやLにしてヘッドが一個右とか左にズレていても構いません。)

では、どうしたらいいのでしょうか⁉️
テープを右に移動しながら、0を全て1にかえ、-を見つけたら停止と言うことは、以下の三つの状態遷移が必要だと思いませんか？

1. 0を1にして右へ
2. 1を読んだらスルーして右へ
3. -を読んだら状態をHにする

と言うことで、先程の表記法を使って書いていきます！

状態遷移図

AA01R
AA11R
AH--S

解読していきましょう。
まず一行目で、1. の「0を1にして右へ」を行なっています。
二行目で、2. の「1を読んだらスルーして右へ」を行なっています。
三行目で、3. の「-を読んだら状態をHにする」と、その場でのストップも行なっています。
アレ❗️簡単じゃないですか！

####チューリングマシンを機械的に実行させたいな
私が、この表記法の通りに動くチューリングマシンを(2年前に)開発したので、そのコードを貼っておきます。

TuringMachine.py

alg = "1"
stopState = "H"
if alg != "optional":
    alg = int(alg)
fom = "SS" #SS(StateStateCharCharHead), SC(StateCharStateCharHead)
if fom == "SS":
    gHed = 2 #getProgram2
    nSta = 1 #new state
    mHed = 4 #move head
    nCha = 3 #new char
else:
    gHed = 1
    nSta = 2
    mHed = 4
    nCha = 3


tape = str(input())

headPosition = 0

state = 'A'

programs = []

program = ""

file = open("StatesList.txt", "r", encoding = "utf-8")
for line in file:
    programs.append(line)

"""
while (program != "RUN"):
    program = str(input())
    if program != "RUN":
        programs.append(program)
"""

getProgram = programs[0]

selectedPrograms = []

while (state != stopState):
    if headPosition >= len(tape):
        for j in range(headPosition + 1 - len(tape)):
            tape = tape[:len(tape)] + '-' + tape[len(tape) + 1:]

    elif headPosition < 0:
        # for k in range(abs(headPosition) + 1 - len(tape)):
        tape = tape[:0] + '-' + tape[0:]
        headPosition = 0

    print("Tape: " + tape)
    print("      " + " " * headPosition + "^")
    print("      " + " " * headPosition + state)

    
    selectedPrograms = []

    for i in range(len(programs)):
        getProgram = programs[i]
            
        if getProgram[0] == state:
            if getProgram[gHed:gHed + alg] == tape[headPosition]:
                selectedPrograms.append(getProgram)
            elif getProgram[gHed:gHed + alg] == '０' and tape[headPosition] == '0':
                selectedPrograms.append(getProgram)
            elif getProgram[gHed:gHed + alg] == '１' and tape[headPosition] == '1':
                selectedPrograms.append(getProgram)
            elif getProgram[gHed:gHed + alg] == 'ー' and tape[headPosition] == '-':
                selectedPrograms.append(getProgram)


    if len(selectedPrograms) == 1:
        error = False
        getProgram = selectedPrograms[0]
        state = getProgram[nSta:nSta + alg]
        if getProgram[nCha:nCha + alg] == '０' or getProgram[nCha:nCha + alg] == '0':
            tape = tape[:headPosition] + '0' + tape[headPosition + 1:]
        elif getProgram[nCha:nCha + alg] == '１' or getProgram[nCha:nCha + alg] == '1':
            tape = tape[:headPosition] + '1' + tape[headPosition + 1:]
        elif getProgram[nCha:nCha + alg] == 'ー' or getProgram[nCha:nCha + alg] == '-':
            tape = tape[:headPosition] + '-' + tape[headPosition + 1:]
        
        if getProgram[mHed:mHed + alg] == 'R' or getProgram[mHed:mHed + alg] == 'r' or getProgram[mHed:mHed + alg] == 'ｒ':
            headPosition += 1
        elif getProgram[mHed:mHed + alg] == 'L' or getProgram[mHed:mHed + alg] == 'l' or getProgram[mHed:mHed + alg] == 'ｌ':
            headPosition -= 1
        elif getProgram[mHed:mHed + alg] == 'S' or getProgram[mHed:mHed + alg] == 's' or getProgram[mHed:mHed + alg] == 'ｓ':
            headPosition = headPosition

    if len(selectedPrograms) == 0:
        print("No applicable line found")
        state = stopState
        error = True

    if len(selectedPrograms) >= 2:
        print("Duplicated line has detected: " + str(len(selectedPrograms)))
        print("State: " + str(state))
        state = stopState
        error = True

if error == False:
    print("Tape: " + tape)
    print("      " + " " * headPosition + "^")
    print("      " + " " * headPosition + state)

コードの上の方にある"StatesList.txt"を書き換えれば任意のファイルを開けます。Pythonのバージョンは3.9.2。IDLEで動かしています！

実行したらテープの内容を入力してください。テープに書かれていない以上(テープの両端の先)は、全て-があるとみなされ、きちんとそこにヘッドが動くこともできます！

##チューリング完全
チューリングマシン、理解していただけたでしょうか？チューリングマシンと密接な関係にある「チューリング完全」について理解していきましょう！

「チューリング完全とは、計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であることをいう。」(出典:Wikipedia)

だそうです☺️
やっぱりわかりません。「「同じ計算能力」って何！？じゃあ計算能力がある電卓もチューリング完全なんですか？！」と思うかもしれません。

この説明は、数学がわからない人や、初心者には不親切です。これを翻訳すると、要するに「万能チューリングマシンと同じことができたらそれはチューリング完全である！」と言うことです。

実は、チューリングマシンというのは、何か特定のことをする機械のことで(この辺については私も十分な理解をしていないかもしれません。間違っていたら教えてください)、先ほどの、「チューリングマシンでのHello, World」としたやつは「0を1に書き換えて、-を読んだら停止するという特定用途のチューリングマシン」で、万能チューリングマシンは、「どんなチューリングマシンも動かせるというチューリングマシン」のことです。

Pythonで動くPythonみたいな感じかなあ！

#チューリングマシンでプログラミングをする！
私たちはチューリングマシンでのユニークで素敵なプログラミングをするにあたって、これまで培ってきた現代的でモダンなプログラミング、if文, for文, 関数, クラス, オブジェクト思考...そんな思考は清算しなければなりません。これらのような、現代的でモダンで難しい概念は一切必要ありません。チューリングマシンでのプログラミングは状態遷移という単純明快なもののみで完結します。

##小規模チューリングマシンプログラミングを嗜む
本章では、任意の二つの二進数を足し合わせるプログラムを作ります。

それでは早速考えていきましょう！
まず、足し算とはどのように行われているのでしょうか。私たちは筆算をするにも暗算をするにも、言葉では説明できない「何か」を使っているように思います。が、実際はそんな難しいことではありません。

X + Yをしたければ、Xが0になるまでXから1引いてYに1を足していけばいいのではないでしょうか。
チューリングマシンでは"1", "0", " "の3つしか文字を表せませんから、二進数で表すことにしましょう。

私が思うに、チューリングマシンでプログラミングをするときは、まずテストケースを考えて、それの通りに動くものを作ろうと意識すると作りやすいと思います。
今回では、1010 + 111 = 10001をテストケースとしてみましょう。
なぜこの数字にしたかというと、このテストケースでは、繰り上がり、一桁上がる繰り上がりが試せるからです。色々な場合を考えてテストケースを作るのがおすすめです。
二つの任意の数字は区切る必要がありますから、私はこう表記することにしました。

testCase

1010-111

この場合の"-"を私は区切り文字と呼んでいます。「引く」という意味ではありません。

では、左の数字から1を引いていくのか、それとも右の数字から1を引いていくのか、どちらが良いでしょうか。私は右の数字から1を引いていくのがいいと思います。左から引いていくと、右に足した時に、右が繰り上がり処理で、一桁数字が増えた場合、区切り文字がなくなってしまいます。それを防ぐためには、右の数字が一桁繰り上がりするたびに一文字ずつ右にずらしていく処理が必要になってきます。それは非常に面倒くさいです。ですから、右から1ずつ引いていって、左に無限に伸びている左側の数字に足していくべきだと思うのです。

ですから、このテストケースの結果は、以下のようになるべきでしょう。

結果

10001-000

それでは！ついに！状態遷移図を書いていこうじゃありませんか！
状態遷移図に必要なもの

1. 右側の数字が0であるならば停止
2. 右側の数字から1引いていく処理
3. 左側の数字に1足していく処理

この3つです！と、思いきや、2. と3. は少しややこしいです。
2. では、例えば右側の数字が1011とかならば、1010とする、すなわち末尾を1から0に置き換えればいいだけなのですが、例えば10100とかだと、10011と、末尾二桁を1にして、その一個前を1から0にする必要があります。
3. でも同様に、1010とかならば1011とする、すなわたい末尾を0から1に置き換えるだけですが、例えば10111とかだと、11000と、末尾三桁を1から0にして、その一個前を0から1に置き換える必要があります。

では！私が書いた状態遷移図を見てください！！

足し算チューリングマシン

#右側の数字が0でないことを確認

#最初のヘッドの位置が左側の数字の先頭なので、まず区切り文字まで移動する
AA00R
AA11R
#区切り文字を超えた
AB--R
#右側の数字に入ったので、0だけのまま-に到達したら停止。そうでなければ引くために状態を変更
BB00R
BH--S
BC11R
CC00R
CC11R
CD--L


#右側の数字から1引く

#右側の数字の末尾が1ならば
DF10L
#右側の数字が末尾が0ならば
DD01L


#左側の数字に1足すために区切り文字を渡る
FF00L
FF11L
FG--L


#左側の数字に1足す

#左側の数字の末尾が0の場合
GA01R
#左側の数字の末尾が1の場合
GG10L
GA-1R

へっへっへ、コメント付きです！Pythonで書いたチューリングマシンでは、テキストにコメントをつけても大丈夫なようにしておきました。#をつければコメントになります。

結果はこんな感じになるかと思います！他のケースも試してみればわかると思いますが、ちゃんと動きますね！

##大規模プログラミングの味を知る
前章までで、チューリングマシンでのプログラミングに少しは慣れたかと思います(慣れていなかったら掛け算するプログラムを作ってみてもいいかもしれません)。
ですから、この章では、本記事の最終目標である「万能チューリングマシンの自作」を行いたいと思います！

まず、万能チューリングマシンというのは、どんなチューリングマシンも動くチューリングマシン、要するにエミュレータのことでしたよね。ですから、万能チューリングマシンに必要な要素は、以下の4つであると言えます。

1. 状態
2. 状態遷移図
3. テープ
4. ヘッド

###大まかな仕様の決定
本記事での万能チューリングマシンの設計思想は「汎用性が高く、わかりやすい」です。「汎用性が高い」というのは、例えば使える状態の数が無限で、テープも両端に無限に広がっていて・・・です。「わかりやすい」というのは、その言葉の通り、この記事を読んでいる人にわかりやすく！です。

万能チューリングマシンに必要な先程の4つの要素はもちろん全てテープに記述されます。
以下は、私が考えた、テープにどのように4つの要素を置くか、です。

[状態][区切り文字][(状態遷移)(区切り文字)(状態遷移)・・・(状態遷移)(区切り文字)(状態遷移)][区切り文字][(テープ一マス)(テープ一マス)・・・(テープ一マス)(テープ一マス)]

と、しましょう。状態・状態遷移図・テープにはそれぞれ区切り文字を置いて、隔てることにします。
アレ❓ヘッドがないですね...と、思ったかもしれません。その話は後でします！

###情報の処理方法
データの処理にはいろいろな方法があります。私が今話したいのは、データの「長さ」についてです。
データの長さには「固定長」と「可変長」の二種類があります。固定長は、データの長さが決まっていることです。普通の(?)詩と、俳句の違いみたいな感じ(俳句はたまに57577から外れたりするけれど...)。

固定長と可変長だったら、固定長だったら、全ての場合を記述してしまうこともできてしまうわけです。ですから、正直固定長と可変長だったら固定長の方が楽ではあるのです。じゃあ状態・状態遷移・テープのデータの処理方法をどうしようか、こうします↓

• 状態は可変長
• テープの一マスは固定長
• 状態遷移図は、固定長と可変長からなる、つまり可変長

###大まかな仕様の決定 でも書いたように、この万能チューリングマシンでは汎用性が求められます。
例えば状態を10bit固定長にしても絶対に困らないと思いますが、それでも汎用性を求めたいので固定長にします。

テープは固定長です。テープは固定長にしても汎用性は失われないからです。また、このテープは、「ヘッドの位置」と「テープの内容」を持った二つの情報を持ったものにします。

状態遷移図は、最初に話した5つの要素からなっています。状態に関する二つの情報は可変長、テープと動きに関する情報は固定長で表せますから、結局可変長になります。

###細かい仕様の決定

• 状態は、"1"だけを使って一進数で記述することにする。Haltは1
• 区切り文字は-を使う。-はそれ以外の場所では使わない
• 状態遷移図は、このチューリングマシンと同じ表記法を使う
• 状態遷移の途中の3番目の要素は、二つの条件がtrueかどうかを示している(0=false, 1=true)。
• 状態遷移図の最後の2bitは、00は左01は右10はその場に停止の意味
• テープは、二文字で表し、一文字目について、一文字目がが0の場合、そこにヘッドはなく、1の場合はそこにヘッドがあることを示し、二文字目は、"1", "0", "-"をかく
• 状態遷移図の中のテープの表記は、"1"を"01", "0"を"00", "-"を"10"と表記する。
• ---は状態と状態遷移図を区切る、-は状態遷移図の中の5つの要素を区切る、--は状態遷移図同士を区切る、----は状態遷移図とテープを区切る

とゆー感じです

###テストケース

11--- 11-11-1-00-01-01-- 11-11-1-01-01-01-- 11-1-1-10-10-10-- --11 01 00 00 01 0- 01
_____ __________________ __________________ _________________ ____ __ __ __ __ __ __
 1.                              2.                                       3. 

読みやすくするために空白を置いていますが、実際はそんなものありません。

1. は状態
2. は状態遷移図(この場合は3個)
3. はテープ(この場合は7個)

さて、このテストケース、何をしているかわかったでしょうか？なんと❗️例のHello, Worldをやっています。読みにくいですね。

念の為、1. ~ 3. を分解してみていきます

1. を分解

1.

11 ---
__ ___
1.  2.

1. は、今の状態を表しています

2. は、「状態」と「状態遷移図」の区切り文字です。

3. 要素が三つあるので最初の一つだけみてみます。

2.を分解

2.

11 - 11 - 1 - 00 - 01 - 01 --
__ _ __ _ _ _ __ _ __ _ __ __
1. 2 3. 2 4 2 5. 2 6. 2 7. 8.

1. は、「今の状態はこれですか？」
2. は、状態遷移中の隣の要素との区切り文字
3. は、「次の状態はこれにしてください。」
4. 二つの条件がtrueかどうかを示してます(0=false, 1=true)。最初は全てtrue。これを「状態遷移図のフラグ」と呼ぶことにします。
5. は、「今テープから受け取った情報はこれですか？」
6. は、「ヘッドがいる場所のテープをこれに書き換えてください。」
7. は、「ヘッドをこっちに動かしてください(00は左01は右10はその場に留まる)。
8. 隣の状態遷移との区切り文字

3.を分解

3.

--11 01 00 00 01 0-
  __ __ __ __ __ __
  1. 2. 3. 3. 2. 4.

1. 11の一文字目は、ヘッドがどこにあるかを示している。1の場合は、そこにヘッドがあることを示していて、0の場合はそうではない。1を示している
2. 1を示している。ここにヘッドはない
3. 0を示している。ここにヘッドはない
4. -を示している。ここにヘッドはない

これからは、ヘッドがどこにあるのか(0か1のやつ)、を「ヘッドのフラグ」と呼ぶことにします。

###つくる！
実際に作っていきます！

初めに、万能チューリングマシンが踏むべきステップを整理しましょう

1. 状態と一致する状態遷移を選り分ける(前章の最後の4. を使う)
2. ヘッドがあるテープの位置の内容と一致する状態遷移を選り分ける。1. と2. の操作によって、使うべき状態遷移が一つに絞られた
3. 1. 1. で絞った状態遷移のところへ行き、テープへ何を書き込めばいいのかのデータ取得など準備をする
4. 1. で得たデータをもとに、テープを書き換える
5. 1. と同様にして、ヘッドの移動させる方向のデータを得て移動する。万能チューリングマシンの使用上右端はないが、左端はあるのでその場合の処理を気をつける（後述）
6. 状態を書き換えて最初に戻るor停止する

なんて面倒くさいのでしょうか！

作っていきましょう！

####1. をやる
テストケースを示します。

テストケース

11--- 1-11-1-00-01-01-- 11-11-1-01-01-01-- 111-1-1-10-10-10-- --11 01 00 00 01 0-

空白は見やすくするためです。

状態11を読んで、その後に続く三つの状態遷移図を選り分けるにはどうしたら良いでしょうか？
以下のようにすると良いでしょう

1. 読んだ状態には印をつける(1を0にする)
2. 状態遷移図の読まれた側にも印をつける(1を0にする)
3. 1. で、すでに全て0になってしまっていたら、それを不適当なものとして状態遷移図のフラグをfalseにする
4. 1. に戻る
5. もし、読んだ状態が全て0になったら、状態遷移図のうち、まだ1が残っているものを不適当なものとして、状態遷移図のフラグをfalseにする

つまり、先程のテストケースが、こうなればいいわけです。

テストケース結果

-00---1-11-0-00-01-01--11-11-1-01-01-01--111-1-0-10-10-10----11010000010-

書いた

状態遷移図

#1. 

AB10R #状態の読んだものを0にしている

AA00R #これと
AP--S #これは、状態を読み終わった時

##ここから
BB11R
BC--R
CC--R
CD00S
CD11S
##ここまでは、状態遷移図まで移動

##ここから
DD00R
DF--R
FF11R
FG--R
GI10R
##ここまでは、不適当なものの状態遷移のフラグをfalseにしている

DI10R #適当だったら通りすぎる

##ここから
II11R
II00R

IJ--R #-が一個だけだった時の処理
JI00R
JI11R

JK--R #-が二個だった時の処理
KD11S
KD00S
##ここまでは、次の状態遷移へ向かう

##ここから
KL--L #-が三個だった時(さっきの続き)
LL00L
LL11L

LM--L #-が一個だった時(さっきの続きではない、戻り始める)
ML00L
ML11L

MN--L #-が二個だった時
NL00L
NL11L

NO--L #-が三個だった時(=状態に戻ってきた！)

OO11L
OO00L
OA--R
##ここまでは、最初に戻っている。

##状態より多いものが記述されている(=不適当なやつ)を排除する
PP--R
PQ01R #状態遷移図まで移動しつつ、元の状態に戻す。

QQ01R #全て0だった時(=true)、通り過ぎながら元の状態に戻す。
QR--R

QS11R #1が会った時(=false)、状態遷移のフラグをfalseにする。
SS11R
ST--R
TT00R
TT11R
TU--R
UR10R

RR00R #通り過ぎてゆく
RR11R

RV--R #-が一個の時
VR00R
VR11R

VW--R #-が二個の時
WP01R

WX--R #-が三個の時
XP00S #次が-でないなら、それを状態遷移だと見なして読んでいく
XP11S

XY--S #-が四個の時、状態遷移図とテープとの区切り文字なので、ストップ

結果はこうなったと思います！成功ですね！

結果

-00---1-11-0-00-01-01--11-11-1-01-01-01--111-1-0-10-10-10----11010000010-
                                                            ^
                                                            Y

####2. をやる

どうするのかといえば

1. テープの場所に行く
2. ヘッドのフラグが0だったら、次のマスに行く
3. ヘッドのフラグが1だったら、そのマスの内容を記憶したまま戻る
4. 状態遷移図を戻りながら読み、不適当(=false)なものの状態遷移図のフラグを0にする
5. 適切なものはそのままスルーする

テープに書かれている内容が"0", "1", "-"の三つがあるので、三つのテストケース・結果を示しておきます。

テストケース"0"

11---11-11-1-00-01-01--11-11-1-01-01-01--11-1-1-10-10-10----0110010-010-

テストケース"0"の結果

-00---11-11-1-00-01-01--11-11-0-01-01-01--11-1-0-10-10-10----0110010-010-
   ^
  状態

テストケース"1"

11---11-11-1-00-01-01--11-11-1-01-01-01--11-1-1-10-10-10----0111010-010-

テストケース"1"の結果

-00---11-11-0-00-01-01--11-11-1-01-01-01--11-1-0-10-10-10----0111010-010-
   ^
  状態

テストケース"-"

11---11-11-1-00-01-01--11-11-1-01-01-01--11-1-1-10-10-10----011-010-010-

テストケース"-"

-00---11-11-0-00-01-01--11-11-0-01-01-01--11-1-1-10-10-10----011-010-010-
   ^
  状態

作った！
同じものを三回記述しないといけないのはちょっと辛かったです...

#2.

YZ--R #テープに移動

Za00R #テープのフラグが0
aZ00R
aZ11R
aZ--R

Zb11R #テープのフラグが1
bc00l #内容が0
bd11l #内容が1
be--l #内容が-

###状態遷移図のフラグをいじりにいく
##内容が0の時
cc00l
cc11l
cf--l
fc00l
fc11l
fg--l
gg--l #状態遷移図とテープの間を渡った

gh00l 
gh11l
hh00l
hh11l
hi--l #「ヘッドを左・右・その場に留まる」を渡った

ii--l

ij00l
ij11l
jj00l
jj11l
jk--l #「テープの次の内容はこれにしてください」を渡った

#テープの内容が適当か不適当かを見定める
kt11l #"X1"でfalse

km00l #"X0"で今のところtrue
mt11l #"10"でfalse
mn00l #"00"でtrue

tt00l
tt11l

to--l
op10l
op00l #falseだっとき、状態遷移のフラグを1→0 or 0→0にする

nq--l
qp11l
qp00l #tureだった時、スルーする

#次の状態遷移へ移動
pp00l
pp11l
pr--l
rp00l
rp11l
rs--l
sg00l
sg11l
sく--s #-が三つあったら状態遷移図終了

##内容が1の時
dd00l
dd11l
du--l
ud00l
ud11l
uv--l
vv--l #状態遷移図とテープの間を渡った

vw00l
vw11l
ww00l
ww11l
wx--l #「ヘッドを左・右・その場に留まる」を渡った

xx--l

xy00l
xy11l
yy00l
yy11l
yz--l #「テープの次の内容はこれにしてください」を渡った

#テープの内容が適当か不適当か見定める
z100l #"X0"でfalse
z211l #"X1"で、Xは0しかないからtrue

1100l
1111l
13--l
3210l
3200l #状態遷移のフラグを1→0 or 0→0

2200l
2211l
24--l #-一つ
4200l
4211l
45--l #-ふたつ
5v00l
5v11l
5く--s #-三つ

##内容が-の時
ee00l
ee11l
e6--l
6e00l
6e11l
67--l
77--l #テープと状態遷移図の間を渡った

7800l
7811l
8800l
8811l
89--l #「ヘッドを左・右・その場に留まる」を渡った

9900l
9911l
9あーーl #「テープの次の内容はこれにしてください」を渡った

あい１１l #"X1"なのでfalse
あう００l #"X0"なので今のところtrue
うい００l #"00"だからfalse
うえ１１l #"10"だからtrue

いい００l
いい１１l

いおーーl
おえ１０l #状態遷移のフラグを1→0 or 0→0
おえ００l

ええ００l
ええ１１l
えかーーl #-一個
かえ００l
かえ１１l
かきーーl #-にこ
き7００l
き7１１l
きくーーs #-三個

###3. 4. 5. をやっていく！
この三つは大きな山場です！とても面倒くさいですが、単純作業ばかりだし色々なパターンが考えられるのでテストケースは載せませんでした。状態遷移図を書いて動きを自分で確かめてみてください！
####3. をやる
テープの書き換えや、ヘッドの移動の準備をします！
状態遷移図の中から使うやつを抽出して、テープを何に書き換えるかのデータを保持します。

#3. 11---11-11-1-00-01-01--11-11-1-10-00-01--11-1-1-01-10-10----011-010-010-
テープの書き換え準備を行っていきます！

##左側の0を-にしていく
くくーーl
くけ０ーl
けけ０ーl


##状態遷移図のフラグが1なのを探しにいく
けけーーr #状態遷移図まで移動

けこ１１r #状態遷移図の一番最初のデータ
ここ１１r
こさーーr #状態遷移図の二番目のデータにいく
さし１１r
しし１１r
しすーーr #状態遷移図のフラグへ！

すせ００r　＃状態遷移図のフラグが０
すつ１１l　＃状態遷移図のフラグが１

##状態遷移図のフラグが０だった時
せせーーr　＃状態遷移図の四番目のデータを通り越す
せそ００r
せそ１１r
そそ００r
そそ１１r
そたーーr　＃状態遷移図の五番目のデータを通り越す
たた００r
たた１１r
たちーーr　＃状態遷移図の六番目のデータを通り越す
ちち００r
ちち１１r

ちけーーr　#次の状態遷移へ

##状態遷移のフラグが１だった時
#印をつける。一番目のデータの先頭位置文字を0にする。
つつーーl　＃二番目のデータを通り越す
つて１１l
てて１１l
てとーーl　＃一番目のデータを通り越す。
とと１１l
となーーr
なに１０r

##次のテープの書き込みを読む("1"を"01", "0"を"00", "-"を"10")
にに１１r　＃一番目のデータを通り越す
にぬーーr　＃二番目のデータを通り越す
ぬぬ１１r
ぬねーーr　＃三番目のデータを通り越す
ねね１１r
ねのーーr　＃四番目のデータを通り越す
のの００r
のの１１r

のはーーr　＃五番目のデータ。次のテープが書き込まれている。
はひ００r　＃一文字目が０（"０"or"１"）
ひふ１１r　＃”１”
ひへ００r　＃”０”
はほ１１r　＃一文字目が１”ー”
＃ふが１、へが０、ほがー

色々な場合があるのでテストケースを今回は載せませんでしたが、↑ここまでやると「ふ」、「へ」、「ほ」の状態になると思います！

####4. をやる
テープの書き換えです！

4. テープの書き換えを行う！
＃＃書き換えにいく
＃１にするとき
ふふ００r　＃ただ右にいく
ふふ１１r
ふまーーr　＃ーが一つだった時
まふ００r
まふ１１r
まみーーr　＃ーがふたつあった時
みふ００r
みふ１１r
みめーーr　＃ーが三つあった時
めもーーr　＃ー4つ目を通り越す

もや００r　＃テープのフラグが０だった時
やも００r
やも１１r
やもーーr

もゆ１１r　＃テープのフラグが１だった時
ゆよ０１l　＃Xを１に書き換え
ゆよ１１l　＃Xを１に書き換え
ゆよー１l　＃Xを１に書き換え

＃０にする時
へへ００r　＃ただ右に行く
へへ１１r
へらーーr　＃ーが一つだった時
らへ００r
らへ１１r
らりーーr　＃ーがふたつだった時
りへ００r
りへ１１r
りるーーr　＃ーが三つあった時
るれーーr　＃ー４っつ目を通り越す

れろ００r　＃テープのフラグが０だった時
ろれ００r
ろれ１１r
ろれーーr

れわ１１r　＃テープのフラグが１だった時
わよ００l　＃Xを０に書き換え
わよ１０l　＃Xを０に書き換え
わよー０l　＃Xを０に書き換え

＃ーにする時
ほほ００r　＃ただ右に行く
ほほ１１r
ほをーーr　＃ーが一つだった時
をほ００r
をほ１１r
をんーーr　＃ーがふたつだった時
んほ００r
んほ１１r
んアーーr　＃ーが三つあった時
アイーーr　＃ーが4つ目を通り越す

イウ００r　＃テープのフラグが０だった時
ウイ００r
ウイ１１r
ウイーーr

イエ１１r　＃テープのフラグが１だった時
エよ０ーl　＃Xをーに書き換え
エよ１ーl　＃Xをーに書き換え
エよーーl　＃Xをーに書き換え

####5. をやる！
ヘッドの移動です！これが一番大変です。「その場に停止」と「右に行く」というのはとても簡単なのですが、「左に行く」というのがとても大変です。「左に行く」にも二つの場合があり、一つはヘッドがテープの左端にない場合です。その場合はただ左にヘッドを移せばいいので簡単です。

が、しかし、ヘッドが左端にある場合、つまり"-"を4つ隔てた左には状態遷移図がある場合、そこから左に移すのが大変です。そこでどうするかというと、テープを全て右にうつします。それが厄介なのでがんばりましょう😭

5. ヘッドの移動！　＃11---11-11-1-00-01-00--11-11-1-01-10-00--11-1-1-10-10-00----1-01010-01
＃テープの書き換えが終わったので、今度はヘッドの移動
よよ００l　＃ただ左に行く
よよ１１l
よオーーl　＃ーが一個
オよ００l
オよ１１l
オカーーl　＃ーがにこ
カカーーl　＃次から状態遷移図に入る

カキ００l　＃６個目の状態遷移中の情報
カキ１１l
キキ００l
キキ１１l
キクーーl　＃５個目の状態遷移中の情報
クク００l
クク１１l
クケーーl　＃４個目の状態遷移中の情報
ケケ００l
ケケ１１l
ケコーーl　＃状態遷移のフラグを読む


コサ００l　＃状態遷移のフラグが０
サシーーl　＃２つ目の状態遷移中の情報
シシ００l
シシ１１l
シスーーl　＃１つ目の状態遷移中の情報
スス００l
スス１１l
スセーーl　＃ーがふたつ
セセーーl
セキ００l
セキ１１l

コソ１１r　＃状態遷移のフラグが１
ソターーr　＃４コメ
タタ００r
タタ１１r
タチーーr　＃５コメ
チチ００r
チチ１１r
チツーーr ＃６コメ、移動方向
ツテ１１r　＃１Xなのでその場に停止
ツト００r　＃０Xなのでまだわからない
トナ００r　＃００なので左
トニ１１r　＃０１なので右
＃テがその場に、ナが左、ニが右
＃テは何もすることがないから放置

＃右に行く
ニニ００r　＃右に行く
ニニ１１r
ニヌーーr　＃ーが１つ
ヌニ００r
ヌニ１１r
ヌネーーr　＃ーが２つ
ネニ００r
ネニ１１r
ネノーーr　＃ーが３つ
ノハーーr　＃ーが４つ

ハヒ００r　＃ヘッドの位置じゃないので右に
ヒハ００r
ヒハ１１r
ヒハーーr

ハフ１０r　＃ヘッドの位置なのでヘッドを移動
フホ００r
フホ１１r
フホーーr
ホマ０１l

＃左に行く
ナナ００r　＃右に行く
ナナ１１r
ナミーーr　＃ーが１つ
ミナ００r
ミナ１１r
ミメーーr　＃ーが２つ
メナ００r
メナ１１r
メモーーr　＃ーが３つ
モヤーーr　＃ーが４つ

ヤユ００r　＃ヘッドの位置じゃないので右に
ユヤ００r
ユヤ１１r
ユヤーーr

＃ヘッドの場所がテープの左端かどうかを判断する
ヤヨ１０l　＃ヘッドの位置
ヨラ００l
ヨラ１１l
ヨラーーl
ラリ０１l ＃左端ではなかった時、テープのフラグを０から１にする

ラルーーr　＃左端だったので、テープを二回右にずらす
ルレ００r　＃テープの左端までいく
ルレ１１r　＃テープの左端までいく
ルレーーr　＃テープの左端までいく

レロ００r　＃テープのフラグがあるのでまだテープの右端ではないとき
ロレ００r
ロレ１１r
ロレーーr

レワーーl　＃右端についた。全て右に一個づつずらしていく！

＃移すのは、テープに書き込まれているものとテープのフラグを別にして考える
＃テープに書き込まれているものを移す
ワヲ０ーr　＃０を右に移す
ヲンーーr
ンガー０l

ワギ１ーr　＃１を右に移す
ギグーーr
グガー１l

ワゼーーr　＃ーを右に移す
ゼゾーーr
ゾガーーl

＃テープには全て元々ーが書き込まれているので、わざわざーを移す状態遷移を書かなくてもいい（書いたほうが丁寧ではある）

ガゲーーl　＃テープのフラグ移動する
ゲゴーーl

ゴザ０ーr　＃テープのフラグは全て０のはずなのでこれだけでいい！
ザジーーr
ジズー０l

ズダーーl　＃テープに書き込まれているものを移す作業に戻る
ダワーーl

ゴヂーーr　＃全て移し終わったのでテープのフラグを移動
ヂヅーーr
ヅリー１l


ママ００l　＃ヘッドの位置を揃えて終わらせる
ママ１１l
マデーーl
デマ００l
デマ１１l
デリーーl
リリーーl
リテ００l
リテ１１l

とゆー感じでした！大変！

####6. をやる！
最後に状態を書き換えて、それが1だったら停止、そうでなければまた最初の状態("A")に戻っていきます！状態遷移の二番目のデータを順次０にしていき、その分書き加えていく感じです（状態を読む時の逆？のやり方）

こんな感じ↓

6. それでは状態を変更していきます！　#11---11-11-1-00-01-01--11-11-1-01-10-01--11-1111-1-10-10-01----1-01010-01
テテ００l　＃状態遷移の一文字目が０なのを探しに行く（3. で印をつけたので）
テテ１１l
テドーーl　＃ーが一つ
ドテ００l
ドテ１１l
ドバーーl　＃ーが二つ
バテ００l
バテ１１l
バァーーl　＃ーが三つあったので、左から状態遷移図を読んでいくが、その前に一個０をつけておく
ァビー０r　＃ー四文字目のところのーを０にして印をつけとく
ビビーーr　＃状態遷移図のところまで移動

ビブ１１r　＃一文字目が１なので違う
ビボ００r　＃一文字目が０だった

＃一文字目が１の時
ブブ００r　＃ただ右に行く
ブブ１１r
ブベーーr　＃ーがいっこ
ベブ００r
ベブ１１r
ベビーーr　＃ーがにこ

＃一文字目が０の時
ボボ００r
ボボ１１r
ボィーーr
ィィ００r
ィゥ１０l ＃次の状態　の１を０にしていく
ィヮーーl ＃全て０だったので終了！

＃状態の書き換え
ゥゥ００l　＃ただ左に行く
ゥゥ１１l
ゥェーーl　＃ーが一つの時
ェゥ００l
ェゥ１１l
ェォーーl　＃ーが二つの時
ォゥ００l
ォゥ１１l
ォョーーl　＃ーが三つあった時！
ョビ０１r　＃０だったら１にして
ョャ１１l　＃ーがあるまで１を左に行く
ャャ１１l
ャュー１r　＃ーがあったので１にして状態遷移図に戻りに行く
ュュ１１r
ュビーーr

＃＃ヮになった時、つまり状態の書き換えが全て終わった時の処理
＃状態遷移のフラグは後で処理するとして、今いる状態遷移の０を１にすべきところをする
ヮヮ０１l　＃状態遷移の二番目のデータが全て０なので、１にする
ヮがーーl　＃状態遷移の一番目のデータの場所へ
がぎ１１l　＃状態遷移の一番目のデータへ着いた。１を飛ばして０のところへ行く
ぎぐ０１l　＃０を１にした。先頭へむかう！

ぐぐ００l
ぐぐ１１l
ぐげーーl　＃ーが一個
げぐ００l
げぐ１１l
げごーーl　＃ーが二個
ごぐ００l
ごぐ１１l
ござーーr　＃ーが三個！

＃状態遷移のフラグの０を全て１にしていく！状態遷移の中で０が一文字だけあるのは状態遷移のフラグだけなので意外と簡単！
ざぶーーr　＃状態遷移図に入った
ぶじーーr
じじ１１r　＃状態遷移の一個目のデータを通り越す
じずーーr
ずず１１r　＃状態遷移の二個目のデータを通り越す
ずぜーーr
ぜぞ０１r　＃状態遷移のフラグが０だったら１にする
ぜぞ１１r　＃状態遷移のフラグが１だったらそのまま
ぞぞ００r　＃次の状態遷移に行くのでただ右に
ぞぞ１１r
ぞだーーr　＃ーが一個
だぞ００r
だぞ１１r
だぢーーr　＃ーが二個
ぢじ１１r　＃ーが二個だった
ぢづーーl　＃ーが三個あったから終了！最初に戻ります！

づづ００l　＃ただ左に行って最初に戻る
づづ１１l
づでーーl　＃ーが一個
でづ００l
でづ１１l
でどーーl　＃ーが二個
どづ００l
どづ１１l
どばーーl　＃ーが三個
ばび１１l
びHーーs　＃１が一個だったら停止！
びべ１１l　＃端まで行く
べべ１１l
べAーーr　＃端にたどり着いたらAにして最初っから！

大変すぎます😭

####完成を祝う
ここまで書いて、ちゃんと動いてるかな〜といいうことでテストケースを示しておきます！

testcase

11---11-11-1-00-01-01--11-11-1-01-01-01--11-1-1-10-01-10----1101000-00

読めばわかると思いますが（わからない方はもう一回読み直してください）

これをわかりやすく書くとすると、まず状態で
1 = H
11 = A
とした時、このテープは以下のような感じです

A --- AA01R AA11R AH-1S ---- 110-0
                             ^
                            状態

とすると、実行後はこうなるはずですね↓

H --- AA01R AA11R AH01S ---- 11110
                                ^
                               状態

つまり、こうなれば言い訳です↓

11---11-11-1-00-01-01--11-11-1-01-01-01--11-1-1-10-01-10----0101011100

どうなったでしょうか！

わーい！！成功です！

ここのを全部コピペしてみたけど動かなかった；；という方はこちら↓

UniversalTuringMachineStatesList.txtに全て入っています！（GitHubよくわからないので心配ですが...）

#トラブルシューティング
Q. No applicable line foundなんとかが出るんですが！？
A. 読むべき状態遷移がなかった時に出るエラーです

Q. Duplicated line has detected:なんとかが出るんですが！？
A. 読むべき状態遷移が複数あった時のエラーです

Q. 万能チューリングマシンを動かしているときにNo applicable云々が出るんですが！？
A. 私のコーディングの問題か、もしくはテープに書き込んだ状態遷移の問題です。どうしてもわからなければコメント欄に書いていただけると助かります。

Q. 万能チューリングマシンを動かしている時にDuplicated lineうんぬんが出るんですが！？
A. 私のコーディングの問題です

#ﾜﾀｸｼの無限への興味関心事
無限に伸びるテープというのは面白いもので、万能チューリングマシンを書いている時に私が考えた問題として、テープについて、無限に伸びるというのは「両端」に無限に伸びた方がいいのか？それとも「片方」に伸びた方がいいのか？というものがありました。

これについて万能チューリングマシンを構成する時の5. で、左端が足りなくなったら右に一個づつずらしたように、私は片方に伸びるのでも構わないと思っています。

しかし、これはとても奇妙なもので、「両端に伸びる無限」と「片方に伸びる無限」であったら、後者の方が圧倒的に短く、もっと言えば片方にだけ伸びる無限というのは、両端に伸びる無限の半分の長さなのではないかとすら錯覚してしまいます。しかし、実際はどちらも無限に伸びていますから、結局は同じ長さなのです。

#ﾜﾀｸｼの万能チューリングマシンへの興味関心事
今回作った万能チューリングマシンではおおよそ２００個ほどの状態を使いました。この万能チューリングマシンでは無限個の状態を扱うことができます。しかし、２００個という有限から無限を扱うことができるのは、これもまた奇妙なものです(というのは嘘で、２００個の状態を私たちの１０本の指と考え、無限個の状態を無限に並んでいるキーボードと考えてください。私たちはわずか１０本の指でどのキーボードだって押すことができます)。

もっと奇妙で興味深い問題は、この万能チューリングマシンは２００個の状態でできていますが、それは「２００個しか状態が使えないチューリングマシンも万能チューリングマシンだ(そのチューリングマシンの中で万能チューリングマシンを作れるから)」ということです。これはどんどん階層構造にすることが可能です。例えば２００個しか使えないチューリングマシンを作るのに１００個しか状態を使わないとします。それをどんどんやっていくと...↓みたいな感じ(数値は全て例です)

この図のように、最低？個の状態を使って、万能チューリングマシンの上で万能チューリングマシンを作っていけばいつか無限個に達することができます。
では、？個の？の数値はなんなのでしょうか。これが私にとっての最大の問題です。

が、実はこれは外国の方が解いてしまったそうです😢

#反省とおわりに
ここまで読んでくれた方がいるでしょうか。読んでいなくてもこのページを踏んでくれただけで嬉しいです。

今回が私にとって二度目の万能チューリングマシンの構成でしたが、作っている途中に「こここうしたらもっとよかったなあ」とか、「記事のためにも僕のためにも仕様書というのをもっと厳密に書くべきだったなあ」とか...思っていました。
前者に関してはしょうがないし、次作るときはもっと良い設計にしたいなと思っています。が、後者に関しては前回も同じことを思ったまま、結局やらなかったのでこの記事の質を下げてしまったし、今更引き下がることもできないので悲しく思います。

拙い日本語と粗雑な説明でしたが、やる気が出てきたら新しい記事を出すか、この記事を訂正するかで直していきたいと思います...

質問や意見はここのコメント欄やTwitterで教えてください！ありがとうございました！