Chapter 4: Definitions

Question 1

Definition 4.1.

register machine

Answer 1

A register machine consists of the following:

· A sequence of registers R1, R2, · · · , each capable of being assigned a non-negative integer.
· A program, which consists of a specified finite number of states S0, S1, · · · , Sn such that:
· Each of the states S1, · · · , Sn is associated to an instruction, to be performed in that
state.
· S1 is the initial state: its instruction is to be performed first.
· S0 is the terminal state: on reaching it, the program ends.

Question 2

Definition 4.2.

computable register machine

Answer 2

A function f : Nk 0 → N0 is a computable function if there exists a register machine that, started with n1 in R1, · · · , nk in Rk, and zero values in all remaining registers, ends (i.e. reaches state S0) with f(n1, · · · , nk) in R1.

Question 3

Definition 4.3.

partial function

Answer 3

A partial function f : Nk 0 → N0 is a map whose restriction to some subset, A say, of its domain, Nk 0, is a function, i.e. f : Nk 0 → N0 is a partial function if f|A : A → N0 is a function, for some A ⊂ Nk 0

Question 4

Definition 4.4.

computable partial function

Answer 4

A partial function f : Nk 0 → N0 is a computable partial function if there exists a register machine that, started with n1 in R1, · · · , nk in Rk, and zero values in all remaining registers, ends (i.e. reaches state S0) with f(n1, · · · , nk) in R1 if f(n1, · · · , nk) is defined, and does not terminate if f(n1, · · · , nk) is undefined.

Question 5

Definition 4.8.

set of recursive partial functions

Answer 5

The set of recursive partial functions is defined, inductively, as follows:

1) The (zero) function f : Nk 0 → N0 , f(n1, · · · , nk) = 0 is recursive.
2) The (successor) function f : N0 → N0 , f(n) = n + 1 is recursive.
3) The (projection) function f : Nk 0 → N0 , f(n1, · · · , nk) = ni for some 1 ≤ i ≤ k, is recursive.
4) The composition of recursive (partial) functions leads to a recursive (partial) function.
5) Applying primitive recursion to recursive (partial) functions leads to a recursive (partial) function.
6) Applying minimalisation to a recursive (partial) function leads to a recursive (possibly partial) function.