System.Automata.TuringMachine Class Reference

A nondeterministic Turing machine More...

Inheritance diagram for System.Automata.TuringMachine:

Public Types
enum	Direction { Direction.L, Direction.R, Direction.S }
	The direction to move the tape More...

Public Member Functions
	TuringMachine (States q, Alphabet a, TapeAlphabet g, TuringTransitionFunction tf, State q0)
bool	Run (IEnumerable< char > x, out char[] o)
	Run the machine More...
bool	Run (IEnumerable< char > x)
bool	Run (string x, out char[] o)
bool	Run (string x)

Static Public Member Functions
static string	BinEncode (int x)
static string	BinEncode (char x)
static string	BinEncode (char[] x)
static string	BinEncode (string x)
static string	UnaryEncode (uint n)
static string	BinEncode (TuringMachine t, char[] x=null)
	Encode a turing machine More...
static string	BinEncode (TuringTransition t, States s)
	Encode a turing machine move More...

Static Public Attributes
static new readonly AcceptingStates	AcceptingStates = new AcceptingStates(State.Ha)

Protected Member Functions
int	MoveTapeHead (int i, Direction d)

Properties
TapeAlphabet	TapeAlphabet [get, protected set]
	The tape alphabet. More...
new TuringTransitionFunction	Transitions [get]
Properties inherited from System.Automata.Automaton
States	States [get, protected set]
	The set of states. More...
AcceptingStates	AcceptingStates [get, protected set]
	The set of accepting states. More...
Alphabet	Alphabet [get, protected set]
	The machine's alphabet. More...
State	InitialState [get, protected set]
	The initial state. More...
TransitionFunction	Transitions [get, protected set]
	The state transition mappings More...

Detailed Description

A nondeterministic Turing machine

Member Enumeration Documentation

Direction

enum System.Automata.TuringMachine.Direction

strong

The direction to move the tape

Enumerator
L	Move the tape head left one cell.
R	Move the tape head right one cell.
S	Do not move the tape head.

Member Function Documentation

BinEncode() [1/6]

static string System.Automata.TuringMachine.BinEncode ( int  x )

static

Parameters

x	The number to encode

Returns

The integer as a binary number

32-bits with two's complement for negatives, without leading 0s

BinEncode() [2/6]

static string System.Automata.TuringMachine.BinEncode ( char  x )

static

Parameters

x	The character to encode

Returns

The character as an ASCII binary number without leading 0s

BinEncode() [3/6]

static string System.Automata.TuringMachine.BinEncode ( char []  x )

static

Parameters

x	The string to encode

Returns

A string of the form e(x0)Δe(x1)Δ..Δe(xk)Δ where e(xk) is the binary encoding of a single character.

BinEncode() [4/6]

static string System.Automata.TuringMachine.BinEncode ( string  x )

static

Parameters

x	The string to encode

Returns

A string of the form e(x0)Δe(x1)Δ..Δe(xk)Δ where e(xk) is the binary encoding of a single character.

BinEncode() [5/6]

static string System.Automata.TuringMachine.BinEncode ( TuringMachine  t, char []  x = null  )

static

Encode a turing machine

Parameters

t	The turing machine to encode
x	The input to encode

Returns

A string ∈ {0, 1, Δ}* representing a turing machine in the form Δe(m0)Δe(m1)Δ..Δe(mk)Δe(x) Where mk is a transition and e is the binary encoding function.

See BinEncode(TuringTransition) and BinEncode(char[]) for specific encodings.

BinEncode() [6/6]

static string System.Automata.TuringMachine.BinEncode ( TuringTransition  t, States  s  )

static

Encode a turing machine move

Parameters

t	The transition
s	The set of states

Returns

A string ∈ {0, 1, Δ}* representing a turing transition 𝛿(p, σ) = (q, τ, D) where p,q ∈ S, σ,τ ∈ Σ in the form n(indexof(p))Δn(σ)Δn(indexof(q))Δn(τ)Δn(D)Δ where n(x) reperesents the binary integer or UTF representation of x. n(D) = { L->00, R->01, S->10, err->11 }

Exceptions

ArgumentException

If a state referenced is not contained in s

Run()

bool System.Automata.TuringMachine.Run	(	IEnumerable< char >	x,
		out char []	o
	)

Run the machine

Parameters

x	The input to run the machine on.
o	The completed tape contents

Returns

True if the machine halts in the accept state.

The first move the machine makes is to fill the tape with the blank symbol followed by the input.

UnaryEncode()

static string System.Automata.TuringMachine.UnaryEncode ( uint  n )

static

Parameters

n	The number to encode

Returns

The number n returned as the string 1^n

Property Documentation

TapeAlphabet

TapeAlphabet System.Automata.TuringMachine.TapeAlphabet

getprotected set

The tape alphabet.

---

The documentation for this class was generated from the following file:

• System.Automata/TuringMachine.cs