4. domača naloga

4. domača naloga#

Pri tej nalogi boste napisali svoj simulator Turingovih strojev. Zaradi preprostosti bomo za abecedo vzeli kar znake tipa char, za prazni znak bomo izbrali presledek ' ', stanja pa bomo predstavili z nizi. Za možne premike zafiksiramo tip direction:

type direction = Left | Right
type state = string

Implementacija trakov#

Napišite modul Tape, ki implementira spodnjo signaturo, kjer je:

t tip v obe smeri neomejenih trakov in glavo na danem mestu;
make, ki naredi nov trak z znaki iz niza ter glavo na prvem znaku;
read, ki vrne znak pod glavo;
write, ki pod glavo zapiše dani znak;
move, ki glavo premakne v dano smer;
print, ki izpiše vsebino traku ter pod njim z ^ označi mesto glave.

Zadnji dve funkciji naj vrneta nov trak, obstoječega pa naj pustita nespremenjenega.

Ker je tip t abstrakten, si lahko privoščite poljubno implementacijo, zato poskrbite tako za učinkovitost kot za preglednost kode.

module type TAPE = sig
  type t

  val make : string -> t
  val move : direction -> t -> t
  val read : t -> char
  val write : char -> t -> t
  val print : t -> unit
end

Tape.(
  make "ABCDE"
  |> move Right
  |> move Right
  |> write '!'
  |> move Left
  |> print
)

Implementacija Turingovih strojev#

Napišite modul Machine, ki implementira spodnjo signaturo, kjer je:

t tip Turingovih strojev;
make, ki naredi nov stroj z danim začetnim stanjem in seznamom preostalih stanj ter prazno prehodno funkcijo;
initial, ki vrne začetno stanje stroja;
add_transition, ki prehodno funkcijo razširi s prehodom \((q, a) \mapsto (q', a', d)\);
step, ki za dano stanje in trak izvede en korak stroja, če je to mogoče.

Zadnji dve funkciji naj vrneta spremenjene vrednosti, obstoječe argumente pa naj pustita nespremenjene. Prav tako pri zadnjih dveh funkcijah lahko predpostavite, da ju bomo klicali le na poprej podanih stanjih.

Tudi tu je tip t abstrakten, zato poskrbite za učinkovitost in preglednost kode.

module type MACHINE = sig
  type t
  val make : state -> state list -> t
  val initial : t -> state
  val add_transition : state -> char -> state -> char -> direction -> t -> t
  val step : t -> state -> Tape.t -> (state * Tape.t) option
end

Primer stroja “Binary Increment” na http://turingmachine.io lahko implementiramo kot:

let binary_increment =
  Machine.(
    make "right" [ "carry"; "done" ]
    |> add_transition "right" '1' "right" '1' Right
    |> add_transition "right" '0' "right" '0' Right
    |> add_transition "right" ' ' "carry" ' ' Left
    |> add_transition "carry" '1' "carry" '0' Left
    |> add_transition "carry" '0' "done" '1' Left
    |> add_transition "carry" ' ' "done" '1' Left
  )

Zapišite funkciji slow_run in speed_run tipa Machine.t -> str -> unit, ki simulirata Turingov stroj na traku, na katerem je na začetku zapisan dani niz. Prva naj izpiše trakove in stanja pri vseh vmesnih korakih, druga pa naj izpiše le končni trak. Slednjo bomo uporabljali tudi pri meritvi učinkovitosti izvajanja.

let _ =
  slow_run binary_increment "1011"

let _ =
  speed_run binary_increment "1011"

Krajši zapis#

Ko definiramo Turingov stroj, prehode običajno združujemo najprej po stanjih, nato pa še po znakih. Prav tako pri dosti prehodih samo premikamo glavo, trak in stanje pa pustimo pri miru. Zapišite funkcije:

for_state
for_character
for_characters
move
switch_and_move
write_and_move
write_switch_and_move

s katerimi bi lahko zgornji primer na krajše zapisali kot spodaj. Implementacijo in tipe ugotovite sami.

let binary_increment' =
  Machine.make "right" ["carry"; "done"]
  |> for_state "right" [
    for_characters "01" @@ move Right;
    for_character ' ' @@ switch_and_move "carry" Left
  ]
  |> for_state "carry" [
    for_character '1' @@ switch_and_move "carry" Left;
    for_characters "0 " @@ write_switch_and_move "done" '1' Left
  ]  

Primeri Turingovih strojev#

Obračanje niza#

Sestavite Turingov stroj, ki začetni niz obrne na glavo. Pri tem lahko predpostavite, da v začetnem nizu ni nobenega presledka.

Eniški zapis#

Sestavite Turingov stroj, ki na začetku na traku sprejme število \(n\), zapisano v dvojiškem zapisu, na koncu pa naj bo na traku zapisanih natanko \(n\) enic.

Dvojiški zapis#

Sestavite ravno obratni Turingov stroj, torej tak, ki na začetku na traku sprejme število \(n\) enic, na koncu pa naj bo na traku zapisano število \(n\) v dvojiškem zapisu.