チューリングを読む p.129

gistfile1.fs

// .01000000...

type Symbol =
  | None
  | Str of string
  | Num of int
 
type Op =
  | P of Symbol
  | R
 
type state =
  | B
  | C
  | D
  | E
  | F

let P0 = P(Num 0)
let P1 = P(Num 1)

let states = 
  Map.ofList [
    (B, None), ([P0; R], C)
    (C, None), ([R], D)
    (D, None), ([P1; R], E)
    (E, None), ([R], F)
    (F, None), ([P0; R], E)]

let tapeSize = 20
let tape = Array.create tapeSize None
let mutable pos = 0

let showTape() =
  tape
  |> Array.map (function
    | None -> "_"
    | Str x -> x
    | Num x -> string x)
  |> Array.iter (printf "%s")
  printfn ""

let readSymbol() =
  if pos < 0 || pos >= tape.Length then
    pos |> string |> failwith
  tape.[pos]

let writeSymbol symbol =
  if pos < 0 || pos >= tape.Length then
    pos |> string |> failwith
  tape.[pos] <- symbol

let rec run state = 
  if pos < tape.Length then
    let symbol = readSymbol()
    match Map.tryFind (state, symbol) states with
    | Some(opList, newState) ->
      for op in opList do
        match op with 
        | P symbol -> writeSymbol symbol
        | R -> pos <- pos + 1
        showTape()
      run newState
    | _ -> 
      failwith (string state)

run B