ComputabilityTheory.jl Documentation

Adding ComputabilityTheory.jl

julia> using Pkg
julia> Pkg.add("ComputabilityTheory") Updating registry at `~/.julia/registries/General.toml` Resolving package versions... Installed ComputabilityTheory ─ v0.1.1 Updating `~/work/ComputabilityTheory.jl/ComputabilityTheory.jl/docs/Project.toml` [1aac4ff9] ~ ComputabilityTheory v0.1.2 `~/work/ComputabilityTheory.jl/ComputabilityTheory.jl` ⇒ v0.1.1 Updating `~/work/ComputabilityTheory.jl/ComputabilityTheory.jl/docs/Manifest.toml` [1aac4ff9] ~ ComputabilityTheory v0.1.2 `~/work/ComputabilityTheory.jl/ComputabilityTheory.jl` ⇒ v0.1.1 Precompiling project... ComputabilityTheory 1 dependency successfully precompiled in 1 seconds (6 already precompiled)

Documentation

Base.MathConstants.πMethod
π(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\]

Note

See the note from documentation on pair_tuple. This function may not do exactly what you expect.


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
source
Main.ComputabilityTheory.GoToProgrammeType
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)
source
Main.ComputabilityTheory.InstructionType
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
source
Main.ComputabilityTheory.MachineStateType
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.
source
Main.ComputabilityTheory.RegisterMachineType
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.

source
Main.ComputabilityTheory.RuleType
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.

source
Main.ComputabilityTheory.SequenceType
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)
source
Main.ComputabilityTheory.TMProgrammeType
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.
source
Base.randMethod
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)

Note

This may be slow. Depending on how large your upper bound is, it may take a while to find a valid code.


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
source
Base.showMethod
Base.show(io::IO, mstate::MachineState)

Prints the current state of a Turing machine.

source
Main.ComputabilityTheory.:∸Method

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
source
Main.ComputabilityTheory.cℤMethod
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
source
Main.ComputabilityTheory.cℤ⁻¹Method
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
source
Main.ComputabilityTheory.decrementMethod
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$.

source
Main.ComputabilityTheory.gotoMethod
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$.

source
Main.ComputabilityTheory.haltMethod
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$.

source
Main.ComputabilityTheory.ifzero_gotoMethod
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$.

source
Main.ComputabilityTheory.incrementMethod
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$.

source
Main.ComputabilityTheory.pair_tupleMethod
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.

Note

There are two variations to this process which will change the output:

  • As per the visualisation in the link above, the first number given is found along the $x$ axis, and the second along the $y$ axis. In this implementation, it is the other way around. This can easily by modified, however, by adding $k_1$ at the end instead of $k_2$.
  • The other variation is which direction of nesting we decide on for more than 2 inputs. The alternative (which we do not use in this implementation) is

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


Examples

julia> pair_tuple(5,7) # code pair of natural numbers as a natural number
83
source
Main.ComputabilityTheory.rand_unsafeMethod
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)

Note

*This sometimes fails, as not every random number will deconstruct into a nice go-to programme. Programmatically, I have done as much as I can to try to avoid this failing. It is more likely to fail as you increase the upper bound. To avoid this, try using rand, though be warned it might be a little slower as it will keep trying till it finds something.


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
source
Main.ComputabilityTheory.run_goto_programmeMethod
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)
source
Main.ComputabilityTheory.show_programmeMethod
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
source

Index