<<

. 10
( 10 .)



Decode, 70 busy beaver competition, 27
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

<<

. 10
( 10 .)