THE BORE
General => The Superdeep Borehole => Topic started by: Tristam on November 03, 2008, 01:31:26 AM
-
...who understand the self-halting problem: Why does a register machine program that computes the self-halting function h (such that h(n) = 0 if fn(n) is defined and h(n) = 1 if fn(n) is defined) necessitate a companion program that computes the function g such that g(n) = 0 if fn(n) is undefined and g(n) = undefined if fn(n) is defined.
Plz halp, assignment is due soon. Unfortunately the Bore members who I *think* may be able to explain it to me probably have been out of school for a while.
-
actually computability theory isn't really my thing at all, despite my username, but if I understand your question correctly, why wouldn't it? if you can construct a program that doesn't halt, and your machine model allows conditional branching (directly or otherwise), isn't it straightforward to construct the second program from the first?
-
Constructing a program that calculates function g (and one that builds on the results of the program that calculates h) is indeed straightforward enough. My problem was in my thinking of more basic, classical logic.
In my assignment I noted:
Thus, it follows that function g is uncomputable. And when the self-halting problem’s components are shown as above, it’s easy to see how the classical argument form modus tollens summarizes the uncomputability of function h based on g’s uncomputability:
If function h is computable by some register machine, then function g is also computable by some register machine.
However, function g is NOT computable by some register machine.
Therefore, it must be the case that function h is NOT computable by some register machine.
I kept asking why g *necessarily* followed h; however, merely because it *can* follow is enough to construct a simple modus tollens argument to show that function h is not computable.
Does that sound correct to you?
Thanks for your help.
-
yeah, I don't really understand the distinction you're making between necessary and possible. from a predicate logic POV, I guess the inference in question is of the form (exists x: H(x)) -> (exists x: G(x)), where H(x) = "x is a program that fits the definition of h", and G(x) is similar. so if you have a function F on programs (i.e. the procedure I outlined for constructing g from h) such that (forall x: H(x) -> G(F(x))), you just need to use existential elimination and introduction (http://en.wikipedia.org/wiki/Existential_quantification). F does have to work on arbitrary programs that satisfy H though, not just on a particular h --- maybe that's what you meant by necessary?