MOAL.automata_theory package

Submodules

MOAL.automata_theory.counter_machine module

class MOAL.automata_theory.counter_machine.Abacus(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

inc(c=2, z=0)
class MOAL.automata_theory.counter_machine.CounterMachine(program=None)[source]

Bases: object

MAX_STEPS = 20
__init__(program=None)

Setup initial conditions

Register #2 contains “2”, (initially) Registers #0, #1 and #3 are empty (contain “0”). Register #0 remains unchanged throughout calculations

because it is used for the unconditional jump.

Register #1 is a scratch pad.

4 registers, plus ‘scratch pad register’”

z = [z]ero aka, jump register (0) s = [s]cratch register (1) c = [c]urrent register (2) d = [d]estination register (3)

1 2 3 4 5 6 7 8 9 10 <- Instruction (address) JZ DEC INC INC JZ JZ DEC INC JZ H <- Instruction 2 2 3 1 0 1 1 2 0 <- Register 6 1 10 6 <- Jump-to instruction

__str__()
_generate_program(instructions=10, registers=4)
clr(c=2)
cpy(c=2, d=3)
dec(c=2)
halt()
inc(c=2)
j(z=0)
je(r_j, r_k, z=0)
jnz(c=2, z=0)
jz(c=2, z=0)
jzdec(c=2)
run()
run_instruction(instruction)
class MOAL.automata_theory.counter_machine.ElgotRobinsonRASP(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

class MOAL.automata_theory.counter_machine.Lambek(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

class MOAL.automata_theory.counter_machine.Minsky(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

inc(c=2, z=0)
jzdec(c=2)
class MOAL.automata_theory.counter_machine.Program(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

class MOAL.automata_theory.counter_machine.RandomAccessMachine(*args, **kwargs)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

From Wikipedia: “A random-access machine (RAM) is an abstract computational-machine model identical to a multiple-register counter machine with the addition of indirect addressing. At the discretion of an instruction from its finite state machine’s TABLE, the machine derives a “target” register’s address either (i) directly from the instruction itself, or (ii) indirectly from the contents (e.g. number, label) of the “pointer” register specified in the instruction.

By definition: A register is a location with both an address (a unique, distinguishable designation/locator equivalent to a natural number) and a content - a single natural number.

For precision we will use the quasi-formal symbolism from Boolos-Burgess-Jeffrey (2002) to specify a register, its contents, and an operation on a register”

__init__(*args, **kwargs)[source]
cpy(reg, val)[source]

Unlike the cpy in the counter machine above, the random access machine allows for directly accessing an arbitrary register, instead of only being able to use the preset register, for copy/updates.

reg(reg)[source]
class MOAL.automata_theory.counter_machine.SheperdsonSturgis(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

jnz(c=2, z=0)
class MOAL.automata_theory.counter_machine.Successor(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

class MOAL.automata_theory.counter_machine.SuccessorRAM(program=None)[source]

Bases: MOAL.automata_theory.counter_machine.CounterMachine

MOAL.automata_theory.pointer_machine module

MOAL.automata_theory.turing_machine module

class MOAL.automata_theory.turing_machine.Decider(program=None, max_states=10)[source]

Bases: MOAL.automata_theory.turing_machine.TuringMachine

See wikipedia.org/wiki/Machine_that_always_halts

transition()[source]
class MOAL.automata_theory.turing_machine.DummyProgramGenerator[source]

A helper to generate programs for use in the Turing Machine – useful for testing a Universal Turing Machine.

static _transition(next, symbols=[0, 1])[source]

Create a single transition pair with a random 0, 1 write symbol (or provided symbol set.

static make(max_states=10)[source]

Make a program to run in the machine.

Transitions are made up of key/value pairs, so it’s important to shuffle the value beforehand.

class MOAL.automata_theory.turing_machine.TuringMachine(program=None, max_states=10)[source]

Bases: object

__init__(program=None, max_states=10)
_get_tape_visualization()
_run()
_setup(program)
_show_program()
activate()
halt()

Whether or not this machine actually does halt, this method must be called to prevent stack overflow (for infinite examples).

run()
transition()

MOAL.automata_theory.universal_turing_machine module

class MOAL.automata_theory.universal_turing_machine.UniversalTuringMachine(*args, **kwargs)[source]

Bases: MOAL.automata_theory.turing_machine.TuringMachine

wikipedia.org/wiki/Universal_Turing_machine
#Example_of_universal-machine_coding

” TS = Tape symbol TM = Tape-motion MC = M-configuration (instruction, state) P = Print-op

q1 blank P0 R q2 q2 blank E R q3 q3 blank P1 R q4 q4 blank E R q1

DA D DC R DAA DADDCRDAA DAA D D R DAAA DAADDRDAAA DAAA D DCC R DAAAA DAAADDCCRDAAAA DAAAA D D R DA DAAAADDRDA

Finally, the codes for all four 5-tuples are strung together into a code started by ”;” and separated by ”;” i.e.: ;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA “

...for our experiment, we’ll just encode one string directly, and skip the table mapping, since they both represent the same thing, albeit with different string values.

__init__(*args, **kwargs)[source]
add_program(*args)[source]
decode()[source]

Re-assemble the string sequence into a real data structure – not part of the typical UTM behavior, but signifies the need to decode the values into something usable.

encode()[source]

Not really necessary, but to emulate the behavior we translate our generated program into a single long string of values that can be decoded.

run(name)[source]
exception MOAL.automata_theory.universal_turing_machine.UnknownProgram[source]

Bases: exceptions.Exception