ComputabilityTheory.jl Documentation

π(m::Integer..., algebraic::Bool = true)

The depairing function. Takes in an integer and find its unique pair of integers such that those integers paired is exactly the function input:

\[\pi(m) \mapsto \left\langle m_0, m_1\right\rangle\\ \mathbb{N} \to \mathbb{N}^2\]

Setting boolean algebraic flag to false calls a brute force search method which is extremely slow for large $n$ (see the n parameter below) but exists for completeness. That is,

\[\pi(m) := \left(\mu x\leq m\right)\left(\exists y\leq m\right)m=\left\langle x,y\right\rangle\\ \pi_0\left(\left\langle x_0,x_1\right\rangle\right) = x_0\\ \pi_1\left(\left\langle x_0,x_1\right\rangle\right) = x_1\]

This function also takes in a parameter $n$:

\[\pi(m, n) \mapsto \left\langle m_1, \ldots, m_n\right\rangle\\ \mathbb{N} \to \mathbb{N}^n\]

This function may also take in a third parameter $k$ so that

\[\pi(m, n, k) \equiv \pi_k^n \mapsto \left\langle m_1, \ldots, m_n\right\rangle \mapsto m_k\quad\text{where }1\leq k\leq n\]

Examples

julia> π(83, algebraic = false) # code a natural number into a 2-tuple
(5, 7)

julia> π(83, 2, algebraic = true) # use algebraic method of depairing rather than search (much faster)
(5, 7)

julia> π(83, 2, 1, algebraic = false) # code a natural number into a 2-tuple and get the the number in the tuple indexed by 1 (index starting from zero)
7

struct GoToProgramme <: Programme

This struct has fields:

• P::Integer
• programme_length::Integer
• instructions::Vector{<:Tuple}
• max_line::Integer

GoToProgramme(P::Integer)
GoToProgramme(S::Sequence)

A goto programme can be coded by a single number! This number in the struct is P.

For any $d \in \mathbb{N}$, the sequence code of a sequence $(a_0,a_1,\ldots,a_{d-1}) \in \mathbb{N}^d$, denoted by $[a_0,a_1,\ldots,a_{d-1}]$, is

\[\left\langle d, \left\langle a a_0,a_1,\ldots,a_{d-1}\right\rangle\right\rangle\]

Then, P is $[a_0,a_1,\ldots,a_{d-1}]$. So, given $P$, π(P, 2, 0) is the number of lines of the programme, d; and π(P, 2, 1) is the programme itself. Depairing that $d$ times, we get a tuple of integers: the instructions of the programme (one integer codes one line in the programme). We define each line of the programme as being coded as follows:

• The code for "$Rn := Rn + 1$" is $\left\langle 0, n\right\rangle$;
• The code for "$Rn := Rn - 1$" is $\left\langle 1, n\right\rangle$;
• The code for "$\texttt{goto } k$" is $\left\langle 2, k\right\rangle$;
• The code for "$\texttt{if } Rn = 0 \texttt{ goto } k$" is $\left\langle 3, \left\langle n, k\right\rangle\right\rangle$; and
• The code for "$\texttt{halt}$" is $\left\langle 4, 0\right\rangle$.

It should also be noted that the sequence code for some base cases is defined as follows:

• if $d = 0$, the sequence code $[]$ for the empty sequence is the number 0; and
• if $d = 1$, for $a \in \mathbb{N}$, the sequence code $[a]$ for the sequence $(a)$ of length 1, is $\left\langle 1, a\right\rangle$.

The constructor function for this struct will ensure that the given integer P is a valid goto programme.

Examples

julia> GoToProgramme(121).length
1

julia> GoToProgramme(121).instructions
1-element Array{Tuple{BigInt,BigInt},1}:
 (4, 0)

struct Instruction <: ProgrammeCompoment

An instruction is a command spanning a single line in a goto programme.

This struct has the fields:

• I::Integer
• first::Integer
• second::Integer
• third::Union{Integer, Nothing}
• instruction::Tuple

Instruction(I::Integer)

Given an integer, this constructor function decodes the instruction. An instruction can be one of five things, defined as follows:

• The code for "$Rn := Rn + 1$" is $\left\langle 0, n\right\rangle$;
• The code for "$Rn := Rn - 1$" is $\left\langle 1, n\right\rangle$;
• The code for "$\texttt{goto } k$" is $\left\langle 2, k\right\rangle$;
• The code for "$\texttt{if } Rn = 0 \texttt{ goto } k$" is $\left\langle 3, \left\langle n, k\right\rangle\right\rangle$; and
• The code for "$\texttt{halt}$" is $\left\langle 4, 0\right\rangle$.

Instruction(instruction::Tuple)
Instruction(i::Integer, j::Integer...) = Instruction((i, j...))

Given a tuple or a list of values, the value of the instruction is the pair of all inputs.

Examples

julia> Instruction((3, (1, 2))).I
58

mutable struct MachineState <: MachineComponent

A snapshot of a state of a Turing machine.

Fields:

• state::String: The name of the state of the Turing machine at the current machine state.
• tape::Dict{Int, String}: The current state of the tape of the machine. The head will be atIntvalue, and the contents atString` value.
• headpos::Int: The position of the head at the current state of the Turing Machine.

@enum Move Left=1 Stay Right

An enumerated type Move.

mutable struct RegisterMachine <: Machine

A register machine. That is, a machine with finitely many registers, whose registers contain a natural number n ∈ ℕ ∪ {0}.

Fields:

• contents::AbastractArray: The contents of the registers.

RegisterMachine(contents::AbstractArray)

A constructor function for the struct RegisterMachine. Ensures the contents of the machine are indeed all natural numbers

RegisterMachine(T::Union{Tuple, UnitRange})
RegisterMachine(a::Integer, b::Integer...)

Constructor functions for the struct RegisterMachine. Your contents are allowed to be tuples, ranges, or a series of integers.

struct Rule <: MachineComponent

Fields:

• instate::String: The state name (String) where the rule starts.
• outstate::String: The state name (String) where the rule ends.
• s1::String: What the Turing machine will read.
• s2::String: What the Turing machine will write.
• move::String: How the Turing machine will move (see Move).

Note: instate and outstate are connected nodes in the Turing Machine.

struct Sequence <: ProgrammeCompoment

For any $d \in \mathbb{N}$, the sequence code of a sequence $(a_0,a_1,\ldots,a_{d-1}) \in \mathbb{N}^d$, denoted by $[a_0,a_1,\ldots,a_{d-1}]$, is

\[q = \left\langle d, \left\langle a a_0,a_1,\ldots,a_{d-1}\right\rangle\right\rangle\]

The struct has the following fields:

• q::Integer
• seq_length::Integer
• instructions::Tuple

Sequence(q::Integer) # instructions_coded
Sequence(t::Tuple) # (seq_length, instructions_coded)
Sequence(seq_length::Integer, j::Tuple)
Sequence(i::Integer, j::Integer...)
Sequence(i::Instruction...)

The constructor methods for this struct decode the given value(s) into the sequence.

Examples

julia> Sequence(972292871301644916468488152875266508938968846389326007980307063346008398713128885682044504108288931767348821063618087715644933567266540511345568504718733339523678538338052787779884557674350959673597803113281693069940562881722205193604550737455583875504348606989700013337656597740101535).instructions
(328, 4, 531, 4, 5, 0, 14)

struct TMProgramme <: TuringMachine

Fields:

• title::String: A descriptive name for your programme.
• initial::String: The state name where the Turing machine begins.
• final::String: The state name where the Turing machine halts.
• blank::String: The symbol used to denote a blank cell.
• Rules::Vector{Rule}`: A list of rules of the programme.

rand(::Type{GoToProgramme}, d::Integer; upper_bound::Integer = 200)

Finds a random go-to programme.

rand takes in the type, GoToProgramme, a number of lines of the programme, d, and an upper bound for the main instructions (coded; not including the halt instruction) which defaults to 200. (Recall how we code instructions, using pair_tuple, so numbers between 1 and 200 will produce reasonably small codes)

Examples

julia> show_programme(rand(GoToProgramme, 3, upper_bound = 200)) # a reasonably small random programme with 3 lines
0    R3 := R3 + 1
1    if R0 = 0 goto 1
2    halt

Base.show(io::IO, mstate::MachineState)

Prints the current state of a Turing machine.

Truncated negation: an operator that acts like subtraction without going to negatives.

This can be written in the REPL as \dotminus<tab>.

Examples:

julia> 6 ∸ 3
3

julia> 3 ∸ 1
2

julia> 10 ∸ 12
0

julia> 1 ∸ 2
0

cℤ(z::Integer)
cℤ(z::Integer, w::Integer...)

This function uniquely maps an integer to a natural number. The output is a BigInt. This function can be written in the REPL by c\bbZ<tab>.

\[z \mapsto c\mathbb{Z}(z)\\ z, w, \ldots \mapsto c\mathbb{Z}(z), c\mathbb{Z}(w), \ldots\\ \mathbb{Z} \to \mathbb{N}\]

cℤ(zs::AbstractArray{<:Integer})

Given an array of integers, cℤ will convert every element of the array into natrual numbers.

cℤ(r::NTuple{N, Integer})

Given a tuple, cℤ will convert ever element of the tuple into natural numbers, and pair the result:

\[\left(z, w\right) \mapsto c\mathbb{Z}\left(\left\langle z, w\right\rangle\right)\\ \mathbb{Z}^2 \to \mathbb{N}\]

\[\left(z_1, \ldots, z_n\right) \mapsto c\mathbb{Z}\left(\left\langle z_1\right\rangle\right), \ldots, c\mathbb{Z}\left(\left\langle z_n\right\rangle\right)\\ \mathbb{Z}^n \to \mathbb{N}\]

Examples

julia> cℤ(-10) # code integer as a natural number
19

julia> cℤ((-1,2)) # cℤ pairs the code of each
16

cℤ⁻¹(n::Integer)

The inverse of cℤ⁻¹. Uniquely maps natural numbers to integers. This function can be written in the REPL by c\bbZ<tab>\^1<tab>.

cℤ⁻¹(zs::AbstractArray{<:Integer})

Given an array of integers, cℤ⁻¹ will convert every element of the array into integers.

Examples

julia> cℤ⁻¹(19)
-10

decrement(n::Integer)

Constructs an Instruction object for decrementing the $n\textsuperscript{th}$ register.

The code for "$Rn := Rn - 1$" is $\left\langle 1, n\right\rangle$.

goto(n::Integer)

Constructs an Instruction object for going to line $k$.

The code for "$\texttt{goto } k$" is $\left\langle 2, k\right\rangle$.

halt()

Constructs an Instruction object for the final line of all goto programmes: halt.

The code for "$\texttt{halt}$" is $\left\langle 4, 0\right\rangle$.

ifzero_goto(t::NTuple{2, Integer})
ifzero_goto(n::Integer, k::Integer)

Constructs an Instruction object for going to line $k$ if and only if the $n\textsuperscript{th}$ register is zero.

The code for "$\texttt{if } Rn = 0 \texttt{ goto } k$" is $\left\langle 3, \left\langle n, k\right\rangle\right\rangle$.

increment(n::Integer)

Constructs an Instruction object for incrementing the $n\textsuperscript{th}$ register.

The code for "$Rn := Rn + 1$" is $\left\langle 0, n\right\rangle$.

pair_tuple(x::Integer, y::Integer)
pair_tuple(x::Integer, y::Integer, z::Integer...)
pair_tuple(t::Tuple)

The pairing function is a function that uniquely maps any number of integer inputs to a single integer:

\[\left(k_1,k_2\right) \mapsto \frac{1}{2}\left(k_1+k_2\right)\left(k_1+k_2+1\right)+k_1\\ \mathbb{N}^2 \to \mathbb{N}\]

This concept can also be generalised to take integers $x_0$ to $x_{n-1}$ so that

\[(x_0, x_1, \ldots, x_{n - 1}) \mapsto \left\langle\left\langle x_0, \ldots, x_{n - 2}\right\rangle, x_{n - 1}\right\rangle\\ \mathbb{N}^n \to \mathbb{N}\]

and returns their "pair".

As this maps every combination of integers to a single output, this number gets massive very fast. As such, pair_tuple will return a BigInt.

To depair the tuple, see $\pi$.

For more information, see https://en.m.wikipedia.org/wiki/Pairing_function.

Examples

julia> pair_tuple(5,7) # code pair of natural numbers as a natural number
83

rand_unsafe(::Type{GoToProgramme}, d::Integer; upper_bound::Integer = 200)

Finds a random go-to programme.

rand_unsafe takes in the type, GoToProgramme, a number of lines of the programme, d, and an upper bound for the main instructions (coded; not including the halt instruction) which defaults to 200. (Recall how we code instructions, using pair_tuple, so numbers between 1 and 200 will produce reasonably small codes)

Examples

julia> show_programme(ComputabilityTheory.rand_unsafe(GoToProgramme, 3, upper_bound = 200)) # a reasonably small random programme with 3 lines
0    R3 := R3 + 1
1    if R0 = 0 goto 1
2    halt

run_goto_programme(P::GoToProgramme, R::RegisterMachine) -> RegisterMachine.contents
run_goto_programme(P::GoToProgramme, T::Tuple) -> RegisterMachine.contents
run_goto_programme(P::Integer, T::Tuple) -> RegisterMachine.contents
run_goto_programme(P::Integer, R::RegisterMachine) -> RegisterMachine.contents

Takes in a coded programme P (for coding a programme, see notes), and runs the programme using register machine R. It a tuple is given, will convert to a register machine whose contents is the tuple. If an integer is given, will convert to a goto programme.

Notes: There are five possible instructions for a GoTo programme:

• Increment Rᵢ ⟵ pair_tuple(0, i)
• Decrement Rᵢ ⟵ pair_tuple(1, i)
• Goto line k ⟵ pair_tuple(2, k)
• If Rᵢ is zero, goto line k ⟵ pair_tuple(3, (i, k))
• Halt ⟵ pair_tuple(4, 0)

Then, the programme P, consisting of instructions I₁, I₂, ..., Iᵢ, is coded by

pair_tuple(i, pair_tuple(I₁, I₂, ..., Iᵢ))

For utilities regarding these instructions, see pair_tuple, Sequence, Instruction, increment, decrement, goto, ifzero_goto, halt, and GoToProgramme.

Examples

julia> run_goto_programme(363183787614755732766753446033240)
(1, 0)

julia> run_goto_programme(363183787614755732766753446033240, Register(0, 0, 0 ,0))
(1, 0, 0, 0)

run_turing_machine(TMProgramme, tape, verbose)

Run a specified Turing programme on a specified tape. verbose is a boolean.

show_programme(io::IO, P::GoToProgramme)
show_programme(P::GoToProgramme)
show_programme(P::Integer)

Given a goto programme, this function will decode it into its constituent components. It will default to stdout.

Examples

julia> show_programme(121)
0    halt