Haskellによる計算機モデルの実装(チューリングマシン)

Haskell

Haskellは、純粋関数型言語という部類の言語で、従来の手続き型プログラミング言語とは違うパラダイムの言語です。
今回は、Haskellを用いてチューリングマシンを実装しました。

チューリングマシンの概要

チューリングマシンを構成するパーツは3つです。

• テープ
• ヘッド
• 内部状態

テープは、文字が書いてある配列のようなものだと思ってください。マシンは、任意のテープの箇所の1文字を読み取ります。
内部状態は、マシンが持つ任意の状態です。
ヘッドは、このテープの文字を一文字ずつ読み取り、内部状態と文字の組み合わせによって、

• 内部状態を変え、
• テープの読み取り位置をずらす
  というアクションを起こします。

たとえば、

0 1 0 1 1 0 1 0 0 1 1 0 1 0 1

というテープがあったとします。
そしてマシンの内部状態は

{0, 1, 2}

の中のどれかだとします。
下記に示したものが状態遷移規則です。
左辺は、テープの文字と内部状態のペア
右辺は、テープの遷移先と、内部状態の遷移先です。

        (0, 0) \rightarrow (-1, 2) \\
        (0, 1) \rightarrow (1, 1)\\
        (0, 2) \rightarrow (1, 2)\\
        (1, 0) \rightarrow (-1, 0)\\
        (1, 1) \rightarrow (-1, 1)\\
        (1, 2) \rightarrow (-1, 2)\\

上記に示したテープと遷移規則を元に、具体例を考えてみましょう。
マシンが左から2つめの文字(1)を読み取っているとします。そして、マシンの内部状態が0であったとします。
すると、状態遷移規則において、(1,0)であるので、テープの読み取り箇所を-1、マシンの内部状態を０に更新します。
テープの読み取り箇所は、最初2つめの文字であったものが、-1されるので、1つめのも文字になります。
そこで同じように文字を読み取り、内部状態を元に更新していくというフローです。これが永遠に繰り返されます。

Stateモナドと内部状態

チューリングマシンの概要を理解したところで、今回はこのマシンを実装してみましょう。
今回は、内部状態を管理するために、Stateモナドを使い、内部状態を受け渡しながら、実際にテープの読み取りと内部状態の更新を行います。
Stateモナドに関しては、良記事があるのでそれらを参考にしてください。

参考文献
Stateモナドで遊んでみよう
Haskell 状態系モナド 超入門

実装

まず、TeapIndexとInternalStateという型を定義します。そして、これらをタプルでペアにしたMachineStateを定義します。これが、Stateモナドによって管理されます。

turing_machine.hs

type TeapIndex = Int
type InternalState = Int
type MachineState = (TeapIndex, InternalState)

次に読み取りの関数です。

turing_machine.hs

readTeap :: State MachineState InternalState
readTeap = do
    (currentTeapIndex, currentInternalState) <- get
    let (moveTeapDirection, nextInternalState) = runRule currentTeapIndex currentInternalState
    put (currentTeapIndex + moveTeapDirection, nextInternalState)
    return nextInternalState

Stateモナドで、MachineStateを持ち回り、evalStateをするとマシンの内部状態であるInternalStateを返します。runRule関数に、テープのインデックスと内部状態を与えると、どこに移動するかと新しい内部状態を返します。

次に状態遷移規則です。runRule関数の中に、case-of構文を使って実装します。

turing_machine.hs

runRule :: Int -> Int -> (Int, Int)
runRule teapIndex internalState = do
    let currentTeapString = teap !! teapIndex
    case (currentTeapString, internalState) of
        (0, 0) -> (-1, 2) 
        (0, 1) -> (1, 1)
        (0, 2) -> (1, 2)
        (1, 0) -> (-1, 0)
        (1, 1) -> (-1, 1)
        (1, 2) -> (-1, 2)

最後に、テープを実際に読み込む関数を実装します。

turing_machine.hs

readTeap3times = do
    state <- readTeap
    state <- readTeap
    return state

main = do
    print $ execState readTeap3times startState

Stateモナドを使っているため、同じ関数を呼び出しても違う値が返されます。

あとは、初期条件を与えて、実行します。

turing_machine.hs

teap = [1, 0, 1, 0, 0, 1, 0, 1, 1, 0]
startState = (5, 1)

main = do
    print $ execState readTeap3times startState

以上で実装は終了です。状態遷移規則とかを変えると、実際にマシンがうまく動いてることがわかります。
コードはこちらにおいてありますので、ぜひ参考にしてください。

まとめ

今回は、チューリングマシンをHaskellのStateモナドを使って実装しました。
Stateモナドの使い方を学習する上で非常に良いトレーニングになったので、ぜひ実装してみてください！！