Re: Yet another Attempt at Disproving the Halting Problem

[Peter Olcott]

Peter Olcott wrote:

Since it is not a Theorem, you can't invoke it to prove your case.
Worse, if you do invoke it, then any halt analyzer you make has a TM
equivalent which, when restricted to TMs, is known to be impossible. I
don't recall where you stand right now on the standard case.


You have to initialize the arry, not just read from it.

So then you are claiming that it is impossible to initialize an array?
I think that this attempt at refutation is dead.

 

[Peter Olcott]

The problem is: LoopIfHalts *is* the UTM that is running Halt.
Secondly: if Halt outputs "it halts", then LoopIfHalts will see that and
not halt.

That goes against my defined solution.
My solution requires that this not be the case.
You can not show that it must always be the case.

 

[Peter Olcott]

In sci.logic, Peter Olcott
<[email protected]>
wrote


The problem with embedding a TM in another TM is that the embedded
TM loses its boundaries, and one just gets one big TM.

That is why my method of determining if it is executed
within the context of another TM would work. There is
one of these many states that represents the Halt analyzer's
final state. If there is any state transition out of this state,
then it knows that it was mixed in with another TM.

The
halt analyzer is just another TM, and can't call the UTM (TM's
don't "call" things, they execute state transitions; the callstack
is a relatively recent innovation although I'd have to find
examples of pre-recursive code such as very old Fortran comples).

And of course LoopIfHalts embeds an arbitrary TM in itself, then
functions in a certain manner. That manner is later used to
prove that the original TM couldn't possibly solve the halting
problem correctly -- and the TM can't do a thing about it because
it can't know it's executing a (possibly transmogrified) copy of itself,

Back with that example that continues to prove that you don't
understand the burden of proof of proving a negative again.
Why don't you consult some expert and find out what it really
takes to prove a negative.

 

[Simon G Best]

I'm Back!!!

That goes against my defined solution.
My solution requires that this not be the case.
You can not show that it must always be the case.

Hint: The fatal flaw in your strategy is that you've concentrated on
having your halt analyzer check with your special UTM to make sure that
it's not being run as part of something else. You've left your special
UTM itself 'under-defended'.

Your special UTM /itself/ could be part of something else - how will it
know? Is it turtles all the way down?

Your special UTM could even be running on another, ordinary UTM (as in
my last refutation). How would it know? How *could* it know? It
couldn't! *It* *wouldn't*.

It's *always* possible to simulate a TM - *any* TM, *all* TMs, *any*
*possible* TM that might *ever* possibly exist - on an ordinary UTM -
*always*. *That's* *why* *they're* *called* *UNIVERSAL* *Turing*
*Machines*.

And that includes running /your/ 'special' UTM on a UTM

:-D

In the end, there will be a /real/ TM, on which can run any finite
number of UTMs as programs. A /real/ TM (including a UTM) at the
bottom; a simulated UTM on that; a simulated UTM on the simulated UTM;
and another simulated UTM on that; and another; and another; and
another. Almost at the top of this pile of virtual UTMs would be your
special UTM, and right at the top of this glorious pile of refutation
would be your supposed halt analyzer.

The /real/ TM, right at the bottom, can be /more/ than just a UTM. The
UTM part of it is just embedded inside - shock-horror - LoopIfHalts!!!
Oh, no!!!!1!!

Is it beginning to sink in, yet?

heh heh heh...

Simon

 

[Owen Jacobson]

I wasn't talking about an augmented UTM. I wasn't even talking about a
UTM.

And, further, an "augmented UTM" that can correctly evaluate this for
all Turing machines is necessarily a more powerful computing model than a
UTM, and there will exist a program for the augmented UTM that cannot be
analyzed by the augmented UTM (but can by an augmented augmented UTM,
which in turn...)

It'd be interesting to see a proof that a TM with less than 4 states
cannot determine (or can determine) that a TM with the same number of
states or fewer halts... It seems to me that the fact that a TM can
determine if a TM with a limited number of states halts is simply an
application of the above in the other direction.

 

[Will Twentyman]

That goes against my defined solution.
My solution requires that this not be the case.
You can not show that it must always be the case.

Your defined solution appears to not be a halt analyzer. You can't have
a halt analyzer *not* give back either "halts" or "does not halt" in
whatever coding. If there is a third option, such as "I'm not telling",
then it's not a halt analyzer.