Re: Yet another Attempt at Disproving the Halting Problem

[Kenneth Doyle]

Yup it is completely obvious to anyone whom has not thought it through
at all.

Oh look, he's using 'whom'. Pity he doesn't understand the difference
between the subject and predicate of a sentence, otherwise he would sound
really well educated.

 

[Peter Olcott]

What you have done is analogous to:

Question: Is it possible for a human beeing to survive a free fall in
any and all instances?
Answer: No
Proof: Nobody can survive a free fall from a height of 100 meters.
Olcott: But I refuse to jump from that height and thus I have proofen
that a human beeing can survive any and all free falls.

Halting Problem according to Alan Turing:
The problem of finding out whether a given number is the D.N of a
circle-free machine,

Translation: (The problem of finding out whether a given Turing Machine
Description specifies a Turing Machine that fails to Halt).

The above translation was based on pages 5, 12 and 18 of the following
http://www.abelard.org/turpap2/tp2-ie.asp

Turing's words continued:
and we have no general process for doing this in a finite number of steps.
In fact, by applying the diagonal process argument correctly, we can show
that there cannot be any such general solution.

What I have done is correctly refuted any possible proof of the conclusion
stated in the above paragraph.

 

[Peter Olcott]

Start by studying the definitions. Once you do that you will understand
that what you wrote above is nonsense. The definitions are not open to
discussion. In particular, how the halt analyzer returns its result is
not open to discussion.

Au Contraire

Halting Problem according to Alan Turing:
The problem of finding out whether a given number is the D.N of a circle-free
machine,

(The problem of finding out whether a given Turing Machine Description
specifies a Turing Machine that fails to Halt).

and we have no general process for doing this in a finite number of steps.
In fact, by applying the diagonal process argument correctly, we can show
that there cannot be any such general solution.

There is nothing at all that specifies the form of the result in the problem
definition.

 

[Daryl McCullough]

Peter Olcott says...

Halting Problem according to Alan Turing:
The problem of finding out whether a given number is the D.N of a
circle-free machine,

Translation: (The problem of finding out whether a given Turing Machine
Description specifies a Turing Machine that fails to Halt).

I have refuted any existing proof that the above is impossible.

What you have not refuted (because it is provably true) is this:
There is no program H(x,y) which for any pair of inputs x and y,
*always* returns 1 if x is the code for a computer program of one
argument which halts on input y, and *always* returns 0 otherwise.

That's what Turing proved, and you have said nothing that casts
doubt on that proof. So your 1000 posts on this subject have been
a waste of everyone's time.

 

[Daryl McCullough]

Peter Olcott says...

Yup it is completely obvious to anyone whom has not thought it through
at all.

You haven't thought through *anything* at all, Peter. You are spinning
your wheels trying to make a pink elephant by turning off the lights.
Turing's counterexample isn't what *caused* the alleged Halt function
to be incorrect; it is the *evidence* that it incorrect. Destroying
the evidence doesn't make it work any better.

Here's an argument for the impossibility of solving the halting problem
that doesn't in any way rely on one program calling another program.

Pick a programming language (say C). Then we define the following
*mathematical* function on strings (*not* a program---it's just a
function):

diag(x): If x is the code for a program of one string argument
that is functional (that is, it always behaves in the same way
for the same inputs), and x is a legal input to that program,
and that program halts on input x, and the result of running
that program on input x is nonzero, then diag(x) = 0.
Otherwise, diag(x) = 1.

Note: When I say "results" I don't care whether the result is a return
value, or something printed to the screen, or something written to a
file, or something said out loud using a voice synthesizer. However the
program gives its results, if the result of running program x on input
x is nonzero, then diag(x) = 0. Otherwise, diag(x) = 1.

Claim: There is no computer program Q such that for any input x
will produce the result diag(x).

Proof: Let Q(x) be any computer program that takes one string argument,
and let #Q be the code of Q. Then Q(#Q) cannot produce the result
diag(#Q). Either diag(#Q) is 0 (in which case Q(#Q) is something nonzero),
or diag(#Q) is 1 (in which case, Q(#Q) either doesn't halt, or produces
the result 0).

So the conclusion is that there exists a mathematical function that
is not computable by any computer program. Let me remind you that
diag is *not* a computer program. It doesn't actually *call* any
computer programs. It's just that diag(x) is defined in terms of
what *would* happen if you called program x on input x. So it doesn't
help to say that some programs behave differently depending on the
context in which they are called. That doesn't matter.

So the function diag(x) is not computable. Now here's a fact about
diag(x):

Claim: If there were were a program H(x,y) that solved the halting
problem, then diag(x) would be computable by a sufficiently patient
and careful human being.

Proof: To compute diag(x), just simulate (on paper) H(x,x). If
the result is 1, then you know that x is a code for a program
that halts on input x. In that case, you simulate the operation
of program x running on input x. If the result is 0, then you
know that diag(x) = 1, and if the result is nonzero, then you
know that diag(x) = 0.

If the result of simulating H(x,x) is 0, then you know that x
is not a code for a program that halts on input x. In that case,
you know that diag(x) = 1.

So a human being equipped with sufficient amounts of paper could
compute diag(x). By Church's thesis, any deterministic mechanical
algorithm that can be carried out by a human being using pencil
and paper is computable by a computer program. Therefore:

Lemma: If H(x,y) were computable, then diag(x) would be
computable.

Conclusion: Since diag(x) is not computable, then neither is H(x,y).

 

[r.e.s.]

Here's an argument for the impossibility of solving the halting problem
that doesn't in any way rely on one program calling another program.

^^^^^^^^^^

The way in which your argument relies on a program "calling itself"
is that in your proof, a program is assumed to exist (for reductio
ad absurdum) that does call itself, namely your Q(#Q). Is it fair
to say that there was really no such reliance, because, after all,
the conclusion is that Q doesn't exist?

(It's the same kind of situation as in the proof I described in
a different thread, using the noncomputability of Rado functions.)

(Sheesh, I feel like Chuang Tzu -- just woke up from a dream ...
.... wait a minute ... am I a man who merely dreamed he was a
butterfly -- or am I a butterfly who now dreams himself a man?
Or something like that.)

--r.e.s.

 

[Daryl McCullough]

r.e.s. says...

^^^^^^^^^^

The way in which your argument relies on a program "calling itself"
is that in your proof, a program is assumed to exist (for reductio
ad absurdum) that does call itself, namely your Q(#Q). Is it fair
to say that there was really no such reliance, because, after all,
the conclusion is that Q doesn't exist?

No, Q(#Q) is *not* a program calling itself. It is a program executing
on a particular string argument. And no, I didn't prove that Q doesn't
exist. And no, I wasn't doing a reductio ad absurdum to prove that Q
doesn't exist. Q is an absolutely arbitrary computer program that takes
one argument of type string. What I proved was that for *any* program
Q (taking a string argument), the result of the computation Q(#Q)
is something that is unequal to diag(#Q) (thus proving that Q does not
compute the function diag).

Let me give a particular example. Suppose Q(x) is the function
that takes a string a returns the number of characters in that
string. In some programming language, it might have this definition:

int Q(string x) { return x.length; }

In that case, #Q is the code for Q. So it's the string

"int Q(string x) { return x.length; }"

Running Q(#Q) produces an integer, namely 36 (if I counted correctly).
By the definition of diag, diag(#Q) = 0 (since Q(#Q) returns something
nonzero).

So Q(#Q) is not Q *calling* itself. It is Q running on a string that
happens to be the definition of Q. An instance of Q calling itself
would be something like this:

int Q(int x) { if (x==0) return 1; else return x * Q(x-1) }

Anyway, my point wasn't really about whether programs call themselves
or not. Some do and some don't. My point was that in my proof, no program
is calling a *halt* program. This was specifically to address Peter Olcott's
claim that a halt program might behave differently if it is called inside
another program than it would if it were run directly. That distinction
is irrelevant to my argument, since I never mentioned any program
calling the halting program.

 

[Karl Heinz Buchegger]

[...]

It's as if I claim that there are no pink elephants. You note that to
demonstrate that an elephant is not pink, I must turn on the
light. So your approach to producing a pink elephant is to build a dark
building with no lights, and to confiscate any candles or
flashlights that anyone takes into the building. That way, nobody
can prove that you don't have a pink elephant.

precisely. [and also precisely why i don't understand why people
debate whether the silly things he suggests are possible or legal -
it's so obvious that 'not returning the result' can't possibly
-help-...]

Yup it is completely obvious to anyone whom has not thought it through
at all.

Actually the opposite is true:
Anybody thinking that *not returning the result* and at the same time
is claiming that the machine *produces a result* has not thought
it through all to the end. At the moment the machine produces a
result, it *is* possible to return it to the caller and it is
this sheer possibility of this, which makes the paradox possible.

 

[r.e.s.]

r.e.s. says...

No, Q(#Q) is *not* a program calling itself. It is a program executing
on a particular string argument.

I took your "in *any* way" as applying also to "calling",
which can of course mean simply "referring to". In any
event, I meant only the self-referring aspect of Q(#Q).

Unfortunately, I skimmed way too quickly and totally
misread your proof as being reductio ad absurdum.

--r.e.s.

 

[Peter Olcott]

Peter Olcott wrote:

Actually the opposite is true:
Anybody thinking that *not returning the result* and at the same time
is claiming that the machine *produces a result* has not thought
it through all to the end. At the moment the machine produces a
result, it *is* possible to return it to the caller and it is
this sheer possibility of this, which makes the paradox possible.

It could determine is invocation context before beginning to
derive a result. If it was called within the context of another
TM it could simply halt. It does not even need to write a space
to a specific memory location. It could simply halt.
(See what I mean about thinking it through?)

 

[Karl Heinz Buchegger]

It could determine is invocation context before beginning to
derive a result. If it was called within the context of another
TM it could simply halt. It does not even need to write a space
to a specific memory location. It could simply halt.
(See what I mean about thinking it through?)

In which case you are no longer consistent with the requirement
that the Halting function has to produce a correct result
in the range of
Halt
or Does not Halt.

In other words: you no longer have a Halting Analyzer which fullfills
the requirements and thus by definiton have not solved the Halting
Problem. You solved something else, but not the Halting Problem.

 

[David C. Ullrich]

Au Contraire

Halting Problem according to Alan Turing:
The problem of finding out whether a given number is the D.N of a circle-free
machine,

(The problem of finding out whether a given Turing Machine Description
specifies a Turing Machine that fails to Halt).

and we have no general process for doing this in a finite number of steps.
In fact, by applying the diagonal process argument correctly, we can show
that there cannot be any such general solution.

There is nothing at all that specifies the form of the result in the problem
definition.

precisely. it's impossible to -determine- whether the tm halts -
silliness about not returning the result to the caller doesn't
help, the olcott machine is still doing something impossible.

some day you're going to quote something and then also show
that you understand the significance of what you quoted.
maybe not this year, but it's bound to happen eventually...


************************

David C. Ullrich

sorry about the inelegant formatting - typing
one-handed for a few weeks...

 

[David C. Ullrich]

[...]

It's as if I claim that there are no pink elephants. You note that to
demonstrate that an elephant is not pink, I must turn on the
light. So your approach to producing a pink elephant is to build a dark
building with no lights, and to confiscate any candles or
flashlights that anyone takes into the building. That way, nobody
can prove that you don't have a pink elephant.

precisely. [and also precisely why i don't understand why people
debate whether the silly things he suggests are possible or legal -
it's so obvious that 'not returning the result' can't possibly
-help-...]

Yup it is completely obvious to anyone whom has not thought it through
at all.

right. and nobody in the decades since turing managed to think it
through until you came along. guffaw.

btw you should really take a course in remedial english. when
people say 'who' where 'whom' is correct that's one thing -
people often do that intentionally so as not to sound pedantic,
after all 'whom' barely exists these days in informal english.
otoh using 'whom' where 'who' is correct [especially after
the difference has been explained a few times] makes you sound
stupid, like you really do think that the difference is just
that 'whom' is a formal version of 'who'.

although come to think of it if you didn't enjoy sounding
stupid you wouldn't be talking about things you don't
understand. never mind...

************************

David C. Ullrich

sorry about the inelegant formatting - typing
one-handed for a few weeks...

 

[Will Twentyman]

Au Contraire

Halting Problem according to Alan Turing:
The problem of finding out whether a given number is the D.N of a circle-free
machine,

(The problem of finding out whether a given Turing Machine Description
specifies a Turing Machine that fails to Halt).

and we have no general process for doing this in a finite number of steps.
In fact, by applying the diagonal process argument correctly, we can show
that there cannot be any such general solution.

There is nothing at all that specifies the form of the result in the problem
definition.

When you have a TM that claims to be Halt but does not necessarily
return a value equivalent to "halts" or "does not halt", however, it is
not possible to 1) determine that it knew whether the program halts or
2) use it for certain TMs and inputs that we may be interested in.

 

[>parr\(*>]

| On Fri, 13 Aug 2004 00:24:34 GMT, "Peter Olcott"
| >Yup it is completely obvious to anyone whom has not thought it
through
| >at all.

| <...>
| btw you should really take a course in remedial english. when
| people say 'who' where 'whom' is correct that's one thing -
| <...>

Oh dear David,

The well fed troll really suckered you there!.

Don't worry, you're not alone.

 

[Peter Olcott]

Peter Olcott wrote:

In which case you are no longer consistent with the requirement
that the Halting function has to produce a correct result
in the range of
Halt
or Does not Halt.

In other words: you no longer have a Halting Analyzer which fullfills
the requirements and thus by definiton have not solved the Halting
Problem. You solved something else, but not the Halting Problem.

It seems like it can only possibly be construed that YOUR requirements
entail that it must fail. If it does not fail, then it does not meet YOUR
requirements. Lucky I am that Turing's requirements were not so
stringent. It makes no difference that I can't meet your goofy specs.

 

[Peter Olcott]

When you have a TM that claims to be Halt but does not necessarily
return a value equivalent to "halts" or "does not halt", however, it is
not possible to 1) determine that it knew whether the program halts or
2) use it for certain TMs and inputs that we may be interested in.

The updated version now only returns two values ONE and ZERO
for HALTS DOES_NOT_HALT.

The original proof claimed that it showed that there was one TM
for which every halt analyzer must fail. It was wrong in this.

 

[Peter Olcott]

On Fri, 13 Aug 2004 00:24:34 GMT, "Peter Olcott"


right. and nobody in the decades since turing managed to think it
through until you came along. guffaw.

Either prove otherwise or implicitly acknowledge that you have
been defeated by your lack of proving otherwise.

btw you should really take a course in remedial english. when
people say 'who' where 'whom' is correct that's one thing -
people often do that intentionally so as not to sound pedantic,
after all 'whom' barely exists these days in informal english.
otoh using 'whom' where 'who' is correct [especially after
the difference has been explained a few times] makes you sound
stupid, like you really do think that the difference is just
that 'whom' is a formal version of 'who'.

although come to think of it if you didn't enjoy sounding
stupid you wouldn't be talking about things you don't
understand. never mind...

************************

David C. Ullrich

sorry about the inelegant formatting - typing
one-handed for a few weeks...

 

[Peter Olcott]

On Fri, 13 Aug 2004 01:14:21 GMT, "Peter Olcott"


precisely. it's impossible to -determine- whether the tm halts -
silliness about not returning the result to the caller doesn't
help, the olcott machine is still doing something impossible.

All the Halt analyzer needs to do is to ask the UTM if there are
any transitions out of its own final states. ** If the UTM returns that
there are transitions out of the halt analyzer's final states the Halt
analyzer simply halts. If there are no transitions out of its final states
then the Halt Analyzer definitively determines whether or not the
subject TM halts, and writes a ONE or a ZERO to a specific
position in its own tape. There is no other TM that will read this
value because the Halt Analyzer was informed by the UTM, that
the UTM will go into its own halt state, immediately after the
halt analyzer has completed processing.

** This requires an augmented UTM that has a feature not typically
found in either TMs or UTMs. It is a very simple feature to provide.
The UTM merely looks up the Halt Analyzer's final states (these
are provided to the UTM by the Halt Analyzer as parameters)
in its own state transition matrix table. One of the two subscripts
to this table is the state number that was provided as a parameter. As
long as there exists no state transition action anywhere in this row of
the table, the UTM reponds with 1, otherwise with 0.

int IsThereATransitionOutOfThisState(HaltAnalyzerFinalStateNumber)

 

[Peter Olcott]

Peter Olcott says...


What you have not refuted (because it is provably true) is this:
There is no program H(x,y) which for any pair of inputs x and y,
*always* returns 1 if x is the code for a computer program of one
argument which halts on input y, and *always* returns 0 otherwise.

And the conclusion from this was the no TM can possibly
ever conclusively determine whether or not each and every
element of the universal set of TMs will halt on a specific
input data set.

The Proof proved A, and then concluded B. I disproved B.

Alan Turing's statement: (Conclusion of the Halting Problem Proof)
The problem of finding out whether a given number is the D.N of a circle-free
machine, and we have no general process for doing this in a finite number of
steps. In fact, by applying the diagonal process argument correctly, we can
show that there cannot be any such general solution.

This is the conclusion of the proof.