[Recursive enumerable set] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Recursive enumerable set

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


Posted by: nico2005

S = { x | Dfx es finite }

Dfx = Domain of function computed by xth turing machine.

Is S recursive enumerable? Why?

Nicolas.-


Posted by: Matthew Szudzik

Nicolas,

Another way to describe your set S is to say that it is the set of all algorithms f that halt for only finitely many inputs. To claim that S is recursively enumerable is to claim that there is some algorithm s such that s[f] halts when the algorithm f is in the set S, and that loops (that is, does not halt) when f is not in the set S.

Now, for each possible computation z, consider the algorithm u[z] that is defined so that u[z][t] halts if the computation z halts within t many steps, and so that u[z][t] loops if the computation z does not halt within t many steps. Note that if z halts, then the algorithm u[z] is not in the set S. And note that if z loops, then u[z] is in the set S (because u[z] halts for zero inputs in that case, and zero is a finite number).

If your set S were recursively enumerable, then we could use s and u to solve the halting problem for any arbitrary computation z. To determine whether or not the computation z halts, just run the computation z in parallel with the computation s[u[z]]. Exactly one of the two computations will halt. If z halts, then you know that z halts. If s[u[z]] halts, then you know that z loops. But this contradicts the fact that there is no algorithm that can solve the halting problem, so we must conclude that your set S is not recursively enumerable. Q.E.D.

Matthew Szudzik


Posted by: nico2005

Thanks for your response Matthew.

However, when you say "if the computation z halts within t many steps", do you mean that z halts for every input x? or a fixed input k?

If z loops for every input x we can say u[z] is in S, but if z loops for a constant k we can´t conclude such thing. So I understand that when you say that z halts you mean that it halts for every x. In such case my guess is that the function u[z] is not computable.

What do you think?

Regards.

Nicolas.-


Posted by: Matthew Szudzik

Nicolas,

z is a "computation", meaning that it does not have any inputs (for example, z could be the computation Sin[1] or the computation 2+3). I suppose that you could also think of z as an algorithm that takes a fixed input k, although I would write z[k] in that case.

The important point is that z is a computation (i.e. it has no inputs), but u[z] is an algorithm that takes one input (note that the z in the formula "u[z]" is NOT the input to the algorithm u[z], it is a parameter upon which the algorithm depends). If the computation z loops, then u[z][t] loops for every input t, and so the algorithm u[z] is undefined for all inputs. That is, the domain of u[z] is of size 0, so we may conclude that u[z] is in the set S.

Matthew Szudzik




Forum Sponsored by Wolfram Research

© 2004-2008 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