Primitive Rec, Ackerman’s Function, Decidable

 bet 6/18 Sana 13.07.2022 Hajmi 77,62 Kb. #786839
Bog'liq
dec

Example 2.3 Let g(x, y) = x + y. Let
f (x) = µy[g(x + y) = 100].
f (0) = 100, f (1) = 99, . . ., f (99) = 1, f (100) = 0, and f is undefined on all other values.

Def 2.4 A function f (x1, . . . , xn) is general recursive if either

1. f is primitive recursive

2. f is defined by unbounded minimization on a (previously defined) gen- eral recursive function g(x1, . . . , xn, y), i.e. there is a general recursive function g and

f (x1, . . . , xn) = µy[g(x1, . . . , xn, y) = 0].

Def 2.5 The general recursive functions are also called the partial com- putable functions. The subset of the partial computable functions that are total are called the total computable functions, or just the computable func- tions. The term “general recursive” will not be used again in this course, but is included for historical purposes.
We will later see that general recursive functions are very powerful.
1. Turing Machines

We will now take a different approach to pinning down what is meant by “computable.” This definition is motivated by actual computers and resem- bles a machine. The definition is similar to that of a Deterministic Finite Automaton, or Push Down Automaton, but it can do much much more. Keep in mind that our final goal is to show that this model can compute a lot of functions.
We first give the formal definition, and then explain it intuitively.