# ex_tm
[![hex.pm version](https://img.shields.io/hexpm/v/ex_tm.svg)](https://hex.pm/packages/ex_tm)
[![travis-ci status](https://travis-ci.org/SekiT/ex_tm.svg?branch=master)](https://travis-ci.org/SekiT/ex_tm)
[![Coverage Status](https://coveralls.io/repos/github/SekiT/ex_tm/badge.svg)](https://coveralls.io/github/SekiT/ex_tm)
Just proving Elixir is turing complete.
## Installation
If [available in Hex](https://hex.pm/docs/publish), the package can be installed as:
```elixir
def deps do
[{:ex_tm, "~> 1.0.1"}]
end
```
## Example
```elixir
machine = %TuringMachine{
initial_tape: fn _pos -> "_" end,
position: 0,
state: 0,
accept_states: [3],
}
program = [
{0, "_", "Hello,", :right, 1},
{1, "_", " " , :right, 2},
{2, "_", "world!", :right, 3},
]
result = TuringMachine.run(machine, program)
TuringMachine.slice_tape(result, 0, 2)
# => ["Hello,", " ", "world!"]
```
## Struct `TuringMachine`
- `initial_tape`: Function from integer to any value, which represents the value of the tape of given position.
- `tape_hash`: Once evaluated tape values are stored in this map. Avoid touching this.
- `position`: Integer which indicates the position of the head.
- `state`: The state of the machine, which can be any type of value.
- `accept_states`: A list of accept states. The machine stops when its state becomes one of them.
## Program
A program is a list of 5-tuple commands.
The command below means: "when the state is `0` and the value of the tape at now position is `"a"`, then turn it into `"b"`, and go `:right`, and make the state `1`".
`{0, "a", "b", :right, 1}`
The direction is one of `:right`, `:left`, `:stay`, `1`, `-1`, `0`.
## Program by code
You can also make program from string:
```elixir
program = TuringMachine.Program.from_string """
# Make 10100100010000...
0, 0, 1, R, 1
1, 0, 1, R, 2
2, 0, 1, R, 3
3, 0, 1, L, 4
4, 0, 0, L, 4
4, 1, 1, L, 5
5, 0, 0, L, 5
5, 1, 0, L, 6
6, 0, 1, R, 7
7, 0, 0, R, 7
7, 1, 1, R, 8
8, 0, 0, R, 8
8, 1, 0, R, 9
9, 0, 1, L, 4
6 , 1, 1, R, 10
10, 0, 0, R, 10
10, 1, 1, R, 11
11, 0, 0, R, 11
11, 1, 0, R, 1
"""
machine = %TuringMachine{
initial_tape: fn _pos -> "0" end,
state: "0",
accept_states: ["A"],
}
TuringMachine.step_times(machine, program, 30)
|> TuringMachine.slice_tape(0, 6)
# => ["1", "0", "1", "0", "0", "1", "0"]
```
Each line is considered as a command.
`0, 0, 1, R, 1` is interpreted into `{"0", "0", "1", :right, "1"}`.
Note that each value for state or tape is treated as a string.
You can specify direction by `R`, `L`, `S`, or `right`, `left`, `stay`, `1`, `-1`, `0`.
Characters after `#` in a line are ignored, so you can put comments.
Lines that cannot be interpreted as a command are just ignored.
You can also use `TuringMachine.Program.from_file/1` to read code from file.