Elixirでチューリングマシン －Elixir見習いの実習ー

はじめに

Elixirに慣れるために簡単なコードを書いています。チューリングマシンに取り組みました。

チューリングマシンとは

数学者アラン・チューリングが電子計算機の登場以前にその原理の元となったものを考案しました。チューリングマシンと呼ばれています。下記の新潟国際情報大学のyoutube動画がやさしく解説しています。https://www.youtube.com/watch?v=K5WnmOvXAMI&t=66s

新潟国際情報大学の動画より引用させていただきました。

Elixirでどうやる？

Elixirは関数型プログラミング言語です。破壊的代入がありません。ということはチューリングマシンのテープに破壊的代入により書き込むことができません。そこでテープの状態をキーワードリストのようにしました。動画の例ですと下記のようになります。

tape = [{0,:sp},{1,1},{2,:x},{3,:d},{4,1},{5,:y},{6,:z},{7,0},
        {8,:sp},{9,:x},{10,:d},{11,:y},{12,0},{13,:sp},{14,1}]

キーワードリストは各tupleの左側のキーが:aのようなアトムでないといけません。今回はテープの位置を表す整数にしたのでキーワードリストの使い方ができません。仕方がないのでassocという関数を作りました。Lispの連想リストと同じ仕組みです。

iex(25)> Turing.assoc(2,[{1,:a},{2,:x}])
:x 

テープは無限の長さを持ちます。スタート時を０とし右側は１，２，３・・・とし、左側は-1,-2,-3・・・ということにしました。

リストの左側に最新状態のテープ状態を追加します。assocは左から検索しますから、テープを上書きした場合には上書きされた方の値を返します。

これさえできれば後はElixirのパターンマッチングで記述できます。machine/4という関数を作ります。引数は

第１引数　内部状態
第２引数　テープヘッドが読み込んだテープの値
第３引数　テープの位置
第４引数　テープの状態を表すリスト

起動はrun/0です。　内部状態、スター地点のテープヘッドの値、スタート位置（０）、テープのリストをmachine/4に引き渡します。

実行結果

iex(26)> Turing.run
[0,sp,0][0,1,1][0,x,2][0,d,3][1,1,4][1,y,5][1,z,6][1,0,7][1,sp,8][1,x,9][1,d,10]halt
:ok

全コード

run/0 チューリングマシンを起動する。
machine/4　内部状態など４つの引数により状態を変化させる。:h（halt)で終了。　:dは＄　空白は:sp　で代用。その時の内部状態、ヘッドの値、ヘッドの位置をリストにして画面表示する。
assoc/2　第１引数をキーとして第２引数のリストから探してその連想値を返す。

defmodule Turing do

  def run() do
    tape = [{0,:sp},{1,1},{2,:x},{3,:d},{4,1},{5,:y},{6,:z},{7,0},
            {8,:sp},{9,:x},{10,:d},{11,:y},{12,0},{13,:sp},{14,1}]
    machine(0,:sp,0,tape)
  end

  def machine(:h,_,_,_) do IO.puts(:halt) end
  def machine(0,:d,pos,tape) do
    :io.write([0,:d,pos])
    tape1 = [{pos,:d}] ++ tape
    read = assoc(pos+1,tape)
    machine(1,read,pos+1,tape1)
  end
  def machine(0,read,pos,tape) do
    :io.write([0,read,pos])
    tape1 = [{pos,read}] ++ tape
    read = assoc(pos+1,tape)
    machine(0,read,pos+1,tape1)
  end
  def machine(1,:d,pos,tape) do
    :io.write([1,:d,pos])
    tape1 = [{pos,:d}] ++ tape
    read = assoc(pos+1,tape)
    machine(:h,read,pos+1,tape1)
  end
  def machine(1,read,pos,tape) do
    :io.write([1,read,pos])
    tape1 = [{pos,read}] ++ tape
    read = assoc(pos+1,tape)
    machine(1,read,pos+1,tape1)
  end

  def assoc(_,[]) do [] end
  def assoc(key,[{key,x}|_]) do x end
  def assoc(key,[{_,_}|ls]) do
    assoc(key,ls)
  end
end

空想

チューリングの時代はまだ真空管しかありませんでした。コンピューターを作るにしてもメモリはとても希少でした。破壊的代入によりメモリを節約するという意図もあったのかもしれません。現在はメモリは潤沢にあります。もしも、天才チューリングが生き返り、現代のリソースを基にしてコンピューターを設計したらどんなものになるのでしょうか？

終わりに

簡単なものを書きながらElixirの基本的な機能について習得をしています。そろそろPhoenixにもとりかかりたいです。