[re and Recursive sets] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


re and Recursive sets

(Click here to view the original thread with full colors/images)


Posted by: Alexis

two cuestions:

1) S = Ig (S is the image of g) where g is a partial computable and monotonic funcition.

g is monotonic if x>y and g defined for both implies g(x)>=g(y).
S is recursive? Why?

2)Let f be a total computable function.

S = { x | fx = f} (i.e the xth turing machine and f compute the same function)
S is recursively enumerable? is recursive? Why?


Posted by: Matthew Szudzik

Alexis,

Here are answers to your questions:

(1) The set S is not recursive, although it is recursively enumerable.
Let g[x] perform the xth computation in some enumeration of all possible
computations, and then output x if the computation halts. Of course, g[x]
is undefined if the xth computation does not halt. Note that g is
monotonic, and in this case S is just the set of all halting computations.
The set of all halting computations is not recursive (by the recursive
unsolvability of the halting problem).

(2) The set S is not recursive, and not even recursively enumerable in
this case. If S were recursively enumerable, then you could solve the halting problem.

Suppose that S were recursively enumerable, and that you wanted to know whether or not a particular computation z halts. Let f be the totally computable function for which f[n] is 1 if z halts within n many steps, and for which f[n] is 0 otherwise. Letting x be any computable function that always outputs 0, you can now determine whether or not z halts by running z in parallel with a search of the elements of S. If you encounter x as one of the elements of S, then you know that z does not halt. Otherwise, z will eventually halt.


Matthew Szudzik


Posted by: Alexis

Ok thanks!
But in question 1) what do you exactly means when you say "computation"? It is a computable function or it is godel number? In the latter case, S is S={x | fx is total}?
Can you explain that formally?

Regards.
Alexis


Posted by: Matthew Szudzik

A computation is a partially computable function of zero arguments.




Forum Sponsored by Wolfram Research

© 2004-2013 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings