Register Machine

Given a set of states we define -instructions: For a natural number and (usually )

Instruction	Interpretation
	Add letter to the content of register and go to state
	Check whether the last letter in register is - If so go to state - Otherwise, go to state
	Check whether register is empty - If so go to state - Otherwise, go to state
	Check whether register is empty - If so go to state - Otherwise, remove the final letter of its content and go to state

Definition

A pair is called a register machine if is a non-empty finite set of states with two special elements (start and halt states), and is a function with domain and codomain the -instructions (so each is a -instruction). The function is called the program of the register machine. For a fixed , we refer to as the program line.

As is finite, we can find the largest which appears in instructions and we call this number the upper register index. (Note that this machine uses at most registers because we start from ) Computation Sequence Strong Equivalence of Register Machines Partial Function Question

Standard operations

Subroutine Lemma Case Distinction Lemma Repeat Lemma

Computability

Computable Computably Enumerable

Operations on natural numbers

Encoding Numbers in Binary Words Truncation of Register Machine Gödel’s primitive recursive functions Partial Recursive Functions Splitting and Merging Words

Coding Langauges

Encoding Alphabets in Binary Words Encoding Register Machines The Software Principle The s-m-n Theorem Kleene’s Recursion Theorem

Misc

Computability Hierarchy Reduction Function Turing Joint Complete Language Index Set