LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@pictomo_m(m pictomo)

Quineを改造してTuringMachineを作った

Posted at

Click here for an English explanation.

概要

Quineとは、自分自身を出力するプログラミングコードのこと。
"Quineは自分自身を出力する、ということは、自分自身をちょっとだけ変えたものも出力できるのでは?"ということで、Quineを応用し、チューリングマシン含む色々なものを作ってみたという記録になります。
記事を読むよりも実際に実行してみた方がきっとわかりやすいです。
実際のコードはこちらのリポジトリに保存してあるので、ぜひご活用ください。

Quineとは?

百聞は一見に如かずということで、まずはこちらのpythonスクリプトを実行してみてください。

python
_='_=%r;print(_%%_)';print(_%_)

するとシェルに以下のような文字列が出力されたと思います。

shell
_='_=%r;print(_%%_)';print(_%_)

おや、これは実行したPythonスクリプトそれ自体と全く同じですね。
という感じで、Quineとは、自分自身を出力するプログラムコードのことをいいます。

こちらが、私がQuineを知った時に試したリポジトリです。
また、こちらの動画(プログラマの知的遊戯！自身を出力するプログラムQuineの作り方【東工大院生の日常会話切り抜き】#3 - YouTube)では、Quineが非常に興味をそそる形で紹介されています。
Quineを使って、こんな感じ(【HTML】お手軽にQuineアートを作る #JavaScript - Qiita)でアートを作ることもできます。

Transformer

Quineで遊んでいるうちに、"Quineは自分自身を出力する、ということは、当然自分自身をちょっとだけ変更したものも出力できるのでは?"と思ったわけです。
そしてそれを標準出力ではなく自分自身の書き換えに使えば、実行する度に自分自身が変化するスクリプトとなります。
そこでまず私が作ったのが、Transformer(｀・ω・´)ｼｬｷｰﾝ
ちなみにTransformerという命名は、AIやNLPでいうところのTransformerとは全く関係ありません。
車がロボットに変形する方のトランスフォーマーです。

transformer Robot Mode
#!/usr/bin/env python3

# Robot Mode

import sys

path = sys.argv[0]

vehicle_content = """#!/usr/bin/env python3

# Vehicle Mode

import sys

path = sys.argv[0]

vehicle_content = {0}{1}{0}
robot_content = {0}{2}{0}

triple_quotes = chr(34) + chr(34) + chr(34)
with open(path, "w") as file:
    file.write(robot_content.format(triple_quotes, vehicle_content, robot_content))
"""
robot_content = """#!/usr/bin/env python3

# Robot Mode

import sys

path = sys.argv[0]

vehicle_content = {0}{1}{0}
robot_content = {0}{2}{0}

triple_quotes = chr(34) + chr(34) + chr(34)
with open(path, "w") as file:
    file.write(vehicle_content.format(triple_quotes, vehicle_content, robot_content))
"""

triple_quotes = chr(34) + chr(34) + chr(34)
with open(path, "w") as file:
    file.write(vehicle_content.format(triple_quotes, vehicle_content, robot_content))

これを実行すると...

transformer Vehicle Mode
#!/usr/bin/env python3

- # Robot Mode
+ # Vehicle Mode

import sys

path = sys.argv[0]

vehicle_content = """#!/usr/bin/env python3

# Vehicle Mode

import sys

path = sys.argv[0]

vehicle_content = {0}{1}{0}
robot_content = {0}{2}{0}

triple_quotes = chr(34) + chr(34) + chr(34)
with open(path, "w") as file:
    file.write(robot_content.format(triple_quotes, vehicle_content, robot_content))
"""
robot_content = """#!/usr/bin/env python3

# Robot Mode

import sys

path = sys.argv[0]

vehicle_content = {0}{1}{0}
robot_content = {0}{2}{0}

triple_quotes = chr(34) + chr(34) + chr(34)
with open(path, "w") as file:
    file.write(vehicle_content.format(triple_quotes, vehicle_content, robot_content))
"""

triple_quotes = chr(34) + chr(34) + chr(34)
with open(path, "w") as file:
    file.write(vehicle_content.format(triple_quotes, vehicle_content, robot_content))

わかりにくいですが、コードがロボットモードから車モードに変化しています。
もう一度実行すると元に戻ります。
面白いでしょう?

他にも色々とバリエーションを作っているので、ぜひご自身で実行してみてください。
mini-transformerは上記のTransformerをよりコンパクトに実装してみたものです。
self-reconstructorはもっとシンプルで、ただ自分自身を書き換えるだけの変化しないQuineとなります。
ultraman-tigaは3状態を行き来するものです。ウルトラマンティガみたいに( o|o)/ == ｼﾞｭﾜｯ
counterは、実行回数を自身に格納します。実行するたびにexecution_countが+1されます。

Turing Quine

さて本題です。
counterは実行する度に、動的に次の状態を算出し出力しています。
ということは、これを応用すれば、チューリング完全な何かになるのでは?と考えました。
こうして、試行錯誤して出来上がったのがこちら。

turing-quine
#!/usr/bin/env python3

# states
execution_count = 0
state = 0
tape = ["0"]
head = 0

# machine
delta = {
	0: {' ': (1, '.', 1), '.': (0, '#', -1), '#': (0, '.', -1)},
	1: {' ': (0, '#', -1), '.': (1, '#', 1), '#': (0, ' ', 1)}
}
initial_state = 0
goal_states = []

# tape
alphabet = [' ', '.', '#']
default_symbol = "0"
initial_tape = ['0']
initial_head = 0

import sys

path = sys.argv[0]
content = """#!/usr/bin/env python3

# states
execution_count = {5}
state = {6}
tape = {7}
head = {8}

# machine
delta = {9}
initial_state = {10}
goal_states = {11}

# tape
alphabet = {12}
default_symbol = "{13}"
initial_tape = {14}
initial_head = {15}

import sys

path = sys.argv[0]
content = {1}{0}{1}

def tape_str(tape, head):
    s = "".join(tape)
    return s[:head] + "{2}033[1m" + s[head] + "{2}033[0m" + s[head+1:]

if execution_count == 0:
    print(str(execution_count).zfill(3), "Accepted" if state in goal_states else "Rejected", state, tape_str(tape, head))

next = delta.get(state, {3}{4}).get(tape[head], False)
if next:
    state = next[0]
    tape[head] = next[1]
    head += next[2]
    if head == len(tape):
        tape.append(default_symbol)
    elif head == -1:
        tape.insert(0, default_symbol)
        head = 0
    execution_count += 1
    print(str(execution_count).zfill(3), "Accepted" if state in goal_states else "Rejected", state, tape_str(tape, head))
else:
    print("No transition found.")
    sys.exit(1)

with open(path, "w") as file:
    file.write(
        content.format(content, chr(34) * 3, chr(92), chr(123), chr(125), execution_count, state, tape, head, delta, initial_state, goal_states, alphabet, default_symbol, initial_tape, initial_head)
    )
"""

def tape_str(tape, head):
    s = "".join(tape)
    return s[:head] + "\033[1m" + s[head] + "\033[0m" + s[head+1:]

if execution_count == 0:
    print(str(execution_count).zfill(3), "Accepted" if state in goal_states else "Rejected", state, tape_str(tape, head))

next = delta.get(state, {}).get(tape[head], False)
if next:
    state = next[0]
    tape[head] = next[1]
    head += next[2]
    if head == len(tape):
        tape.append(default_symbol)
    elif head == -1:
        tape.insert(0, default_symbol)
        head = 0
    execution_count += 1
    print(str(execution_count).zfill(3), "Accepted" if state in goal_states else "Rejected", state, tape_str(tape, head))
else:
    print("No transition found.")
    sys.exit(1)

with open(path, "w") as file:
    file.write(
        content.format(content, chr(34) * 3, chr(92), chr(123), chr(125), execution_count, state, tape, head, delta, initial_state, goal_states, alphabet, default_symbol, initial_tape, initial_head)
    )

スクリプトの上部に、チューリングマシンとその状態が定義されています。
ちなみにここで定義しているのは、Wolframeの2状態3記号チューリングマシンというやつです。
万能チューリングマシンであることが証明されています。
スクリプトを実行する度に、# states以下が変化していくことがわかるでしょう。

このスクリプトは、チューリングマシンとして動作していることがよりわかりやすいように、実行時に状態を標準出力するようにしてあります。
また、同じディレクトリにリピーターを置いてそちらを実行すると、自動で繰り返し実行してくれます。

実際に実行してみたときの出力が以下。
Wolframeの2状態3記号チューリングマシンに特有の往復模様が確認できますね。

shell
...
1101 Rejected 0 ..########........###...##.#.#.##.##.##.##.#
1102 Rejected 0 ..#######.........###...##.#.#.##.##.##.##.#
1103 Rejected 0 ..######..........###...##.#.#.##.##.##.##.#
1104 Rejected 0 ..#####...........###...##.#.#.##.##.##.##.#
1105 Rejected 0 ..####............###...##.#.#.##.##.##.##.#
1106 Rejected 0 ..###.............###...##.#.#.##.##.##.##.#
1107 Rejected 0 ..##..............###...##.#.#.##.##.##.##.#
1108 Rejected 0 ..#...............###...##.#.#.##.##.##.##.#
1109 Rejected 0 ..................###...##.#.#.##.##.##.##.#
1110 Rejected 0 .#................###...##.#.#.##.##.##.##.#
1111 Rejected 0  ##................###...##.#.#.##.##.##.##.#
1112 Rejected 1 .##................###...##.#.#.##.##.##.##.#
1113 Rejected 0 . #................###...##.#.#.##.##.##.##.#
1114 Rejected 0 . .................###...##.#.#.##.##.##.##.#
1115 Rejected 1 ...................###...##.#.#.##.##.##.##.#
1116 Rejected 1 ..#................###...##.#.#.##.##.##.##.#
1117 Rejected 1 ..##...............###...##.#.#.##.##.##.##.#
1118 Rejected 1 ..###..............###...##.#.#.##.##.##.##.#
1119 Rejected 1 ..####.............###...##.#.#.##.##.##.##.#
1120 Rejected 1 ..#####............###...##.#.#.##.##.##.##.#
1121 Rejected 1 ..######...........###...##.#.#.##.##.##.##.#
1122 Rejected 1 ..#######..........###...##.#.#.##.##.##.##.#
1123 Rejected 1 ..########.........###...##.#.#.##.##.##.##.#
1124 Rejected 1 ..#########........###...##.#.#.##.##.##.##.#
1125 Rejected 1 ..##########.......###...##.#.#.##.##.##.##.#
1126 Rejected 1 ..###########......###...##.#.#.##.##.##.##.#
1127 Rejected 1 ..############.....###...##.#.#.##.##.##.##.#
1128 Rejected 1 ..#############....###...##.#.#.##.##.##.##.#
1129 Rejected 1 ..##############...###...##.#.#.##.##.##.##.#
1130 Rejected 1 ..###############..###...##.#.#.##.##.##.##.#
1131 Rejected 1 ..################.###...##.#.#.##.##.##.##.#
1132 Rejected 1 ..####################...##.#.#.##.##.##.##.#
1133 Rejected 0 ..################# ##...##.#.#.##.##.##.##.#
1134 Rejected 0 ..################# .#...##.#.#.##.##.##.##.#
1135 Rejected 1 ..#################..#...##.#.#.##.##.##.##.#
1136 Rejected 1 ..#################.##...##.#.#.##.##.##.##.#
1137 Rejected 0 ..#################.# ...##.#.#.##.##.##.##.#
1138 Rejected 0 ..#################.# #..##.#.#.##.##.##.##.#
1139 Rejected 1 ..#################.#.#..##.#.#.##.##.##.##.#
1140 Rejected 0 ..#################.#. ..##.#.#.##.##.##.##.#
1141 Rejected 0 ..#################.#. #.##.#.#.##.##.##.##.#
1142 Rejected 1 ..#################.#..#.##.#.#.##.##.##.##.#
1143 Rejected 0 ..#################.#.. .##.#.#.##.##.##.##.#
1144 Rejected 0 ..#################.#.. ###.#.#.##.##.##.##.#
1145 Rejected 1 ..#################.#...###.#.#.##.##.##.##.#
1146 Rejected 0 ..#################.#... ##.#.#.##.##.##.##.#
1147 Rejected 0 ..#################.#... .#.#.#.##.##.##.##.#
1148 Rejected 1 ..#################.#.....#.#.#.##.##.##.##.#
1149 Rejected 1 ..#################.#....##.#.#.##.##.##.##.#
1150 Rejected 0 ..#################.#....# .#.#.##.##.##.##.#
...

まとめ

というわけで、Quineがチューリング完全であることが証明できた...かはわかりませんが、Quineを応用した新しい遊びを実演してみました。
Quineにちょっとだけ手を加え、自分自身を書き換えるようにするだけで、実行する度に自分自身が変化していくおもしろスクリプトができちゃいます。
実際に動いているところを見るともっと面白いので、まだの方はこちらのリポジトリをクローンしてぜひ試してみてください。
また、これを応用して出来る新しいものを思いついたら、ぜひ実装して、私に教えてください。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?