Recursive (Total) and Partial Recursive Functions

Question 1

How does the boundedness between Floop and BlooP programs differ?

Answer 1

‘Free loops’

Question 2

Will Floop programs always terminate?

Answer 2

No …

Question 3

Bounded minimization for FlooP?

Answer 3

For BlooP: h is a primitive recursive function then f is obtained from h by bounded minimization if “the least y > n, such that the projection of h(x, n) = 0 there is one; n otherwise”

Therefore, f yields the minimal value for y (up to bound n( for which h holds.

For FlooP: REMOVE the upper bound:

Problem: Some cases get undefined = partial function

Question 4

What is the least-searched operator?

Answer 4

Question 5

How to impliment the u-operator using a TM:

Answer 5

Question 6

Recursive Definition

Define Partial Recursive Functions:

Answer 6

The partial recursive function are the smallest class containing:

1. The zero,
2. successor,
3. projection functions,

And closed under
4. Composition
5. Primitive recursion, and
6. the u-operator

Note: “smallest class” satisfying certain conditions = smallest case corresponds to the final clause

Question 7

What are (total) recursive functions?

Answer 7

Partial recursive functions need not be undefined, because u might always yield a value

Question 8

What is the halting problem for partial recursive functions?

Answer 8

Let φ1, φ2, φ3 be an enumeration of all partial recursive functions

Question: Maybe there is a way of constructing a recursive fucntion that determines whether φx(x) is undefined and then returns some value

Answer: There is no recursive function which can tell us wether φx(x) s defined for all x