Re: Yet another Attempt at Disproving the Halting Problem

[Will Twentyman]

You other statement was correct. This one seems to not be
correct. There can be many contradictions that do not result
in logical impossibilities It depends upon exactly how the terms
are defined..

The one case that I have in mind was that one of the proofs thought
it to be a logical impossibility to create a TM that provides incorrect
results. Its answers were contradictory. In this case it resulted in
merely a TM with wrong answers, and not a TM that is impossible to
exist.

If part of the specification is that the TM always give correct answers,
and the conclusion is that sometimes it gives incorrect answers, it must
not exist as a TM that always gives correct answers. For example, it
may be possible to make a halt guesser that is *usually* right. But we
want a halt analyzer that is *always* right.

 

[Peter Olcott]

I am not British in this country you are an ass.
If you want to be an arse in your own country
you are welcome to it. The only thing that I can
figure is that the people that tend towards mean
nastiness must have something fundamentally wrong
with their lives.

 

[Peter Olcott]

Then it is not running on a UTM. Perhaps you should call it an Olcott
Machine.

It is a trivial augmentation to the basic definition of a UTM.
If this augmentation was written in C++ it would only take
about ten lines, maybe not even that many.

If it halts without a return value, it is not a halt analyzer.

It is not prohibited from working correctly on every possible input.
Every other attempt WAS prohibited from working correctly on every
possible input. This was the whole basis for the claim that it was
impossible. This basis no longer exists. No program is ever required
to work under every possible condition, they only have to work
correctly for every possible input, that is sufficient. Some real-time
systems have additional response time requirements.

 

[Kai-Uwe Bux]

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?)

Hi,


if I understand you correctly, you propose to write a halt analyzer that
refuses to return its result to a caller and instead prints it (say on the
screen). In order to prevent that it is misused as an ordinary halt
analyzer, it will check its calling context. Thereby, as you point out,
your halt analyzer cannot be used to construct the programm that it will
misclassify.

So, your routine has essentially the following form:

void halt_analyzer ( std::string input_programm ) {
// step one: check for calling context
if ( check_if_called_in_compromised_setting() ) {
exit;
}

// step two: analyze the input_programm
bool result;
/*
now, here goes the code that actually analyzed the input_programm
and sets result.
*/

// step three: print, but do not return the result:
if ( result ) {
std::cout << "programm will halt.\n";
else {
std::cout << "programm will not halt.\"
}

}


Let me first remark the following: The routine halt_analyzer itself cannot
be used to construct the Turing counterexample to its correctness. You are
correct on this account.


Now, please consider the following routine:

bool my_devious_copyright_violation ( std::string input_programm ) {
// step two: analyze the input_programm
bool result;
/*
now, here goes the code that actually analyzed the input_programm
and sets result.
*/
return( result );
}

I construct this one from your halt_analyzer by copying step two. I omit
the protection in step one and I replace the printing of step three with a
return of the result. As you know, Turing's argument shows that the routine

my_devious_copyright_violation

cannot analyze all programms correctly. That is, there is a programm P such
that

my_devious_copyright_violation(P) returns true iff P does not halt.

Here is my question: What will halt_analyzer(P) print?


Best

Kai-Uwe Bux

 

[>parr\(*>]

| > <...>
| > Your first problem is in
| > the very first sentence:
| >
| > "Alan Turing conclusively
| > proved is that it is
| > impossible to construct a
| > halt analyzer that always
| > returns a correct result
| > back to the program being
| > analyzed."
| >
| > He did not. He did not use
| > 'returns a correct result'
| > in his proof.
| > He did not talk about
| > programs (nor programmes as
| > would have been the
| > term used in Britain about
| > 15 years later). And he
| > most certainly and
| > definitely did not have
| > anything like 'returning a
| > result back to the program
| > being analysed'.
| >
| > Read again what you wrote.
| > I'll paraphrase. You
| > assert that in his proof,
| > the program being analysed
| > calls the halt analyser.
| >
| > Let me now repeat what he
| > actually wrote:
| > At the top of page 231:
| >
| > "In particular, it is
| > shown (§11) that the
| > Hilbertian
| > Entscheidungsproblem can
| > have no solution."
| >
| > Can you see any difference
| > between what Turing wrote,
| > and what you wrote?
| > <...>
|
| I am not British in this country you are an
| ass. If you want to be an arse in your own
| country you are welcome to it. The only
| thing that I can figure is that the people
| that tend towards mean nastiness must have
| something fundamentally wrong with their
| lives.

I do. And you are no better than I when it comes to being mean and
nasty towards people with problems.

But all the same, you ignored the technical critique, repeated above,
of your web page content.

I would ask, "what say you to that?", but I know you have absolutely
no answer; that you know inside that you do not know how to turn your
intuitive belief into a formal, and acceptable proof.

Of course, it didn't help your case that you came cruising in on the
wake of |-|erc's maunderings.

Is it any surprise that you are dismissed as a Kook, a Troll?

 

[Will Twentyman]

It is a trivial augmentation to the basic definition of a UTM.
If this augmentation was written in C++ it would only take
about ten lines, maybe not even that many.

I won't argue that point. What I'm trying to get you to see is that you
are using a term that already has a different definition. You can call
the Olcott Machines, Augmented Turing Machines, Swiss Cheese Machines,
or whatever you want. However, when we are discussing a problem that
involves Turing Machines, and you are using some other type of machine
to attempt to solve the problem and refer to it as a Turing Machine as
well, confusion is bound to come.

What I'm trying to convince you to do is use a distinct, different
terminology for your modified TMs to avoid confusion.

It is not prohibited from working correctly on every possible input.
Every other attempt WAS prohibited from working correctly on every
possible input. This was the whole basis for the claim that it was
impossible. This basis no longer exists. No program is ever required
to work under every possible condition, they only have to work
correctly for every possible input, that is sufficient. Some real-time
systems have additional response time requirements.

Since your website is down, I can't check that. I thought I saw
something about halting without a returned value.

 

[Peter Olcott]

Peter Olcott wrote:

If part of the specification is that the TM always give correct answers,
and the conclusion is that sometimes it gives incorrect answers, it must
not exist as a TM that always gives correct answers. For example, it
may be possible to make a halt guesser that is *usually* right. But we
want a halt analyzer that is *always* right.
Yup.

 

[Will Twentyman]

Yup.

However, the contradiction shows that any halt analyzer on a
conventional TM *must* give an incorrect answer for a particular type of
TM. Therefor, each potential halt analyzer will fail when dealing with
conventional TMs. Why? Because it cannot *always* give the correct answer.

 

[Peter Olcott]

I won't argue that point. What I'm trying to get you to see is that you
are using a term that already has a different definition. You can call
the Olcott Machines, Augmented Turing Machines, Swiss Cheese Machines,
or whatever you want. However, when we are discussing a problem that
involves Turing Machines, and you are using some other type of machine
to attempt to solve the problem and refer to it as a Turing Machine as
well, confusion is bound to come.

At what point does one stop calling it a Turing Machine?
If it has more than one tape?
If it has ASCII as its alphabet?
If it implements a C++ compiler?

What I'm trying to convince you to do is use a distinct, different
terminology for your modified TMs to avoid confusion.

Slightly Augmented Universal Turing Machine sounds okay to me.

Since your website is down, I can't check that. I thought I saw
something about halting without a returned value.

It should never be down.
Perhaps the link that I posted had a typo.

www.halting-problem.com

Always a dash inbetween to give it higher search engine
priority on the keywords halting problem.

 

[Peter Olcott]

However, the contradiction shows that any halt analyzer on a
conventional TM *must* give an incorrect answer for a particular type of
TM. Therefor, each potential halt analyzer will fail when dealing with
conventional TMs. Why? Because it cannot *always* give the correct answer.

You slipped and slided you meanings a little there, and ended up
concluding something that is not true. An augmented UTM is in
no way prohibited from correctly processing the halt analysis of
each and every element of the universal set of Turing Machines.

 

[Will Twentyman]

At what point does one stop calling it a Turing Machine?
If it has more than one tape?
If it has ASCII as its alphabet?
If it implements a C++ compiler?

When it's output depends on something other than what's on the tape when
it starts running.

Slightly Augmented Universal Turing Machine sounds okay to me.

SAUTMs. I'll suggest that they emulate SATMs and TMs. Now, what is the
information that a SATM can request from a SAUTM? The next transition,
the entire transition table, or something else?

It should never be down.
Perhaps the link that I posted had a typo.

The link was ok. I've been typing it in manually. It looks like the
internet hiccupped.

 

[Will Twentyman]

You slipped and slided you meanings a little there, and ended up
concluding something that is not true. An augmented UTM is in
no way prohibited from correctly processing the halt analysis of
each and every element of the universal set of Turing Machines.

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

 

[The Ghost In The Machine]

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

It is a trivial augmentation to the basic definition of a UTM.

An interesting requirement, but how does a UTM know that a given
TM implements the Halting Problem? And how does a TM call up to
the UTM to ask whether its thread of execution is looping?

Standard TM machines don't *have* function calls, although they can
emulate them easily enough by writing something on the tape. The
requirement then gets translated into writing a special something
twice -- when the special something look like just another number.

(Hackers do this sort of thing all the time; there's nothing
really distinguishing a pointer from any other largish integer,
after all, on modern machines. [Older machines might reject
odd integers, or integers not a multiple of 4.])

If this augmentation was written in C++ it would only take
about ten lines, maybe not even that many.

A halt analyzer can do a number of things to return its value
back to the ultimate consumer (which may not be LoopIfHalts).
The ones I can think of are:

[1] cout << "Hi, I'm on tape."
[2] light(myLife)
[3] distinguished halting states.

All of these are convertable to a return value through a transmogrification
step that doesn't look at the entire program, but only small pieces
of it.

If you can think of additional side effects, please let us know.

It is not prohibited from working correctly on every possible input.

It is, however, transmogrifiable through a 1-1 non-onto method
into something that *is* prohibited from working correctly
(by the existence of LoopIfHalts).

Every other attempt WAS prohibited from working correctly on every
possible input. This was the whole basis for the claim that it was
impossible. This basis no longer exists. No program is ever required
to work under every possible condition, they only have to work
correctly for every possible input, that is sufficient. Some real-time
systems have additional response time requirements.

Is LoopIfHalts(TransmogrifiedWillHalt) a possible input?

 

[Peter Olcott]

Peter Olcott wrote:

When it's output depends on something other than what's on the tape when
it starts running.

I don't know about that. If the definition of a Turing Machine
machine was as specific as that then:

Any computation that can be carried out by mechanical
means can be performed by some Turing Machine.

was probably trivially refuted before it was even written down.
If you take the above Church Turing thesis literally, then you
have been completely refuted before you said your first word
on this point.

 

[Will Twentyman]

I don't know about that. If the definition of a Turing Machine
machine was as specific as that then:

Any computation that can be carried out by mechanical
means can be performed by some Turing Machine.

was probably trivially refuted before it was even written down.
If you take the above Church Turing thesis literally, then you
have been completely refuted before you said your first word
on this point.

How do you figure? A TM is *defined* to operate based solely on its
states and the input on the tape. Any additional inputs you might
desire can be encoded as part of the input on the tape.

As for the Church-Turing thesis: just because I think something *might*
be carried out by mechanical means doesn't mean it *can* be. I'm not
particularly interested in the Church-Turing thesis at this point. You
asked when something stops *being* a Turing Machine, not when it stops
being *equivalent* to a Turing Machine.

 

[Peter Olcott]

In sci.logic, Peter Olcott

An interesting requirement, but how does a UTM know that a given
TM implements the Halting Problem? And how does a TM call up to
the UTM to ask whether its thread of execution is looping?

Standard TM machines don't *have* function calls, although they can
emulate them easily enough by writing something on the tape. The
requirement then gets translated into writing a special something
twice -- when the special something look like just another number.

Apparently you don't have the basic idea correctly.
All the halt analyzer asks the UTM is if there are any other
TM's running on it. Only if the answer is NO does it even
begin to do its halt analysis.

This means that whenever Halt() sees anything like LoopIfHalts,
it can safely say that it simply halts.

 

[Peter Olcott]

Peter Olcott wrote:

How do you figure? A TM is *defined* to operate based solely on its
states and the input on the tape.

And the Church Turing thesis essentially "defines" each
and every computation to be TM equivalent.

Any additional inputs you might
desire can be encoded as part of the input on the tape.

As for the Church-Turing thesis: just because I think something *might*
be carried out by mechanical means doesn't mean it *can* be. I'm not

Your are getting entirely off-track here unless you are claiming
that looking up a simple value in a two-dimensional array can't
be accomplished by anything less than an oracle.

 

[Will Twentyman]

And the Church Turing thesis essentially "defines" each
and every computation to be TM equivalent.

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.

Your are getting entirely off-track here unless you are claiming
that looking up a simple value in a two-dimensional array can't
be accomplished by anything less than an oracle.

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

 

[Will Twentyman]

Apparently you don't have the basic idea correctly.
All the halt analyzer asks the UTM is if there are any other
TM's running on it. Only if the answer is NO does it even
begin to do its halt analysis.

This means that whenever Halt() sees anything like LoopIfHalts,
it can safely say that it simply halts.

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.

 

[The Ghost In The Machine]

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

Apparently you don't have the basic idea correctly.
All the halt analyzer asks the UTM is if there are any other
TM's running on it. Only if the answer is NO does it even
begin to do its halt analysis.

This means that whenever Halt() sees anything like LoopIfHalts,
it can safely say that it simply halts.

The problem with embedding a TM in another TM is that the embedded
TM loses its boundaries, and one just gets one big 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,
or a variant of itself that alleges to solve the Halting Problem.

This doesn't mean halting analyzers can't exist; the
simplest method is to occasionally return "I can't analyze
this TM", and to use various heuristics (two obvious ones:
for(; ; and while(1) to determine whether an algorithm
halts or not.