Deduction∆ , 46 n-state entry, 27

Diff, 27, 31 score, 27

Div, 33, 52

Element, 33, 52 cell

Entry, 38 blank, 7

Equal, 33 marked, 7

Exp, 31 scanned, 8

Fact, 31 characteristic function, 26

Formulas, 46 Church™s Thesis, 2

Formula, 46 code, 20

Inference, 46 sequence of tape positions, 37

81

82 INDEX

(First) Incompleteness Theorem, 53

tape position, 37

Second Incompleteness Theorem, 54

Turing machine, 38

complete, 2

halt, 11

set of sentences, 44

Halting Problem, 17, 22

completeness, 44

Completeness Theorem, 1

identity function, 26

composition, 29

image of a function, 25

computable

Incompleteness Theorem, 43

function, 26

G¨del™s First, 53

o

set of formulas, 46

G¨del™s Second, 54

o

computation, 11

initial function, 29

partial, 11

input tape, 11

constant function, 30

k-place

decision problem, 1

function, 25

de¬nable

relation, 25

function, 55

relation, 55 language

domain of a function, 25 ¬rst-order number theory, 43

Entscheidungsproblem, 1, 43 machine, 9

Turing, 7, 9

¬rst-order language

marked cell, 7

for number theory, 43

minimalization

Fixed-Point Lemma, 53

bounded, 36

function

unbounded, 35

bounded minimalization of, 36

composition of, 29

natural numbers, 25

computable, 26

n-state

constant, 30

entry in busy beaver competition,

de¬nable in N, 55

27

domain of, 25

Turing machine, 9

identity, 26

number theory

initial, 29

¬rst-order language for, 43

k-place, 25

partial, 25 output tape, 11

primitive recursion of, 30

partial

primitive recursive, 31

computation, 11

projection, 29

function, 25

recursive, 36

pig, yellow, 19

regular, 35

position

successor, 29

tape, 8

Turing computable, 26

primitive recursion, 30

unbounded minimalization of, 35

primitive recursive

zero, 29

function, 31

G¨del code

o relation, 32

sequences, 45 projection function, 29

symbols of LN , 45

G¨del Incompleteness Theorem, 43

o r.e., 39

INDEX 83

recursion Turing computable

function, 26

primitive, 30

relation, 36

recursive

Turing machine, 7, 9

function, 36

code of, 38

relation, 36

n-state, 9

set of formulas, 46

representation of, 18

recursively enumerable, 39

table, 10

set of formulas, 46

universal, 17, 22, 38

regular function, 35

two-way in¬nite tape, 13, 14

relation

characteristic function, 26

unary notation, 26

de¬nable in N, 55

unbounded minimalization, 35

k-place, 25

Unde¬nability Theorem

primitive recursive, 32

Tarski™s, 55

recursive, 36

universal Turing machine, 17, 22, 38

Turing computable, 36

UTM, 17

representable

function, 50 zero function, 29

relation, 50

representation

of a tape position, 19

of a Turing machine, 18

scanned cell, 8

scanner, 13

score

busy beaver competition, 27

state, 8, 9

successor

function, 29

tape position, 11

table

Turing machine, 10

tape, 7, 13

blank, 7

input, 11

output, 11

two-way in¬nite, 13, 14

tape position, 8

code of, 37

code of a sequence of, 37

representation of, 19

successor, 11

Tarski™s Unde¬nability Theorem, 55

theory

of N, 54

of a set of sentences, 44

TM, 9