MOAL.automata_theory package¶
Subpackages¶
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.
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.
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”
-
class
MOAL.automata_theory.counter_machine.
SheperdsonSturgis
(program=None)[source]¶ Bases:
MOAL.automata_theory.counter_machine.CounterMachine
-
jnz
(c=2, z=0)¶
-
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
-
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.
-
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.
-
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.