Chapter 4: Definitions Flashcards Preview

Logic > Chapter 4: Definitions > Flashcards

Flashcards in Chapter 4: Definitions Deck (5)
Loading flashcards...
1

Definition 4.1.
register machine

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.

2

Definition 4.2.
computable register machine

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.

3

Definition 4.3.
partial function

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

4

Definition 4.4.
computable partial function

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.

5

Definition 4.8.
set of recursive partial functions

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.