Re: Yet another Attempt at Disproving the Halting Problem

[Daryl McCullough]

Peter Olcott says...

And the conclusion from this was...

Whatever. Do you agree that Turing proved that 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 of one argument that
halts on input y, and *always* returns 0 otherwise?

 

[David Bernier]

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)

Why don't you use your Halt Analyzer to determine which TMs halt and
which don't, among those listed in Marxen & Buntrock's paper:
``Attacking the Busy Beaver 5" ?

You can find two TMs listed as "unsolved" in
"TABLE 1. Transition Tables of Some Interesting Turing Machines"
at: http://www.drb.insel.de/~heiner/BB/mabu90.html#Results .

(They are TM #4 and TM #6, each with a question mark in the
column showing the number of ones printed by the machine
once [if] it halts.)

David Bernier

P.S.: If you solve Busy Beaver with 5 states, you can publish your
results and become "famous".

 

[>parr\(*>]

| 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...
|
| Whatever. Do you agree that Turing proved that 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 of one argument that
| halts on input y, and *always* returns 0 otherwise?

Daryl, why not let the troll starve?

He's nowhere where ready to understand Turing's paper. He hasn't a
clue what Un(m) means, and particularly the significance of the 'n'
in that expression.

And nor have you. If you did, you'd know that in his paper, Turing
also proved that for certain, limited, machines, the halting problem
could be solved.

 

[David C. Ullrich]

All the Halt analyzer needs to do is to ask the UTM if there are
any transitions out of its own final states.

that's all it needs to do? hard to imagine why nobody thought of
this til now, guffaw.

** If the UTM returns that
there are transitions out of the halt analyzer's final states the Halt
analyzer simply halts.

without returning a 0 or 1? then it's not doing what it's supposed to
do.

If there are no transitions out of its final states
then the Halt Analyzer definitively determines whether or not the
subject TM halts

how???????

the stupidity here is just breathtaking:

'i can write a halt analyzer'
'how?'
'easy. all it has to do is determine whether a tm halts!'

probably perfectly clear to you, but we lesser minds find
a few details that need to be filled in [like all of them...]

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

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

David C. Ullrich

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

 

[David C. Ullrich]

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

the otherwise has been proved here already, many times.

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...

 

[Daryl McCullough]

parr\(*> says...

| Whatever. Do you agree that Turing proved that 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 of one argument that
| halts on input y, and *always* returns 0 otherwise?

He's nowhere where ready to understand Turing's paper. He hasn't a
clue what Un(m) means, and particularly the significance of the 'n'
in that expression.

And nor have you. If you did, you'd know that in his paper, Turing
also proved that for certain, limited, machines, the halting problem
could be solved.

Yes, if you have a limited class of functions that are not
Turing-complete, then sometimes the halting problem can solved
for programs in that class. So? The interesting issue is whether
it is solvable for a Turing-complete set of programs.

Also, I don't personally think that there is anything special
about Turing machines. It was the first example of a Turing-complete
set of programs, and they are an especially simple type of machine,
but the issues involved in the halting problem arise in almost
the same way no matter what model of machine you are using, as
long as it's Turing-complete.

Actually, diagonalization is more general than the halting problem.
As you say, the halting problem is solvable for some classes of
machines. On the other hand, *no* class of machines can compute
its own diagonal:

diag(x) : If x is the code for a program of one argument that
halts on input x, and the result of that computation
is 0, then return 1. Otherwise, return 0.

No matter what class of programs you are talking about (as long
as you can make sense of the phrases "is a code for", "takes one
argument", "returns a result", "halts on input x"), diag(x) is a
well-defined mathematical function that cannot be computed by any
program in that class. For a Turing-complete class of programs,
the non-existence of a program (in that class) computing diag(x)
implies the nonexistence of a program (in that class) solving the
halting problem for that class.

 

[Peter Olcott]

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)

Why don't you use your Halt Analyzer to determine which TMs halt and
which don't, among those listed in Marxen & Buntrock's paper:
``Attacking the Busy Beaver 5" ?

You can find two TMs listed as "unsolved" in
"TABLE 1. Transition Tables of Some Interesting Turing Machines"
at: http://www.drb.insel.de/~heiner/BB/mabu90.html#Results .

(They are TM #4 and TM #6, each with a question mark in the
column showing the number of ones printed by the machine
once [if] it halts.)

David Bernier

P.S.: If you solve Busy Beaver with 5 states, you can publish your
results and become "famous".

I am only proving that the proof that solving the Halting Problem
is impossible is incorrect. I am not proving that solving the Halting
Problem is possible.

 

[Peter Olcott]

| Peter Olcott says...

Daryl, why not let the troll starve?

Why not at least try and form a valid refutation?
Any mindless idiot can provide mindless idiotic rhetoric.
Can't you strive to be more? How about a valid refutation?

I know why you did not critique the opening lines to my website.
Because they were flawless. There was no basis for critique. Is
it a crime in your country to threaten someone (as you did) over the internet?

 

[Peter Olcott]

No matter what class of programs you are talking about (as long
as you can make sense of the phrases "is a code for", "takes one
argument", "returns a result", "halts on input x"), diag(x) is a
well-defined mathematical function that cannot be computed by any
program in that class. For a Turing-complete class of programs,
the non-existence of a program (in that class) computing diag(x)
implies the nonexistence of a program (in that class) solving the
halting problem for that class.

Have you even looked at my latest material? Its only less than
a page. www.halting-problem.com
It is much simpler than any of the other versions and does not
require any form of special hardware.

 

[Peter Olcott]

On Fri, 13 Aug 2004 23:07:09 GMT, "Peter Olcott"


the otherwise has been proved here already, many times.

Now I finally have a concise refutation of all of these proofs.
None of them considered what exactly is required in the attempt
to prove that a thing can not possibly exist.
(the common terminology of this is "proving a negative")

To prove that a thing exists, requires only providing one instance
of this thing. To prove that a thing can not possibly exist requires
simultaneously covered each and every instance in the universal
set of all instances. To prove that my method does not work,
requires proving a negative.

 

[Will Twentyman]

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

Or SPACE for "no value returned"

The SPACE is the problem.

 

[Will Twentyman]

Now I finally have a concise refutation of all of these proofs.
None of them considered what exactly is required in the attempt
to prove that a thing can not possibly exist.
(the common terminology of this is "proving a negative")

To prove that a thing exists, requires only providing one instance
of this thing. To prove that a thing can not possibly exist requires
simultaneously covered each and every instance in the universal
set of all instances. To prove that my method does not work,
requires proving a negative.

Proving something does not exist is simple. You show that it's
existence will cause a contradiction. This has been done for the
Halting Problem.

 

[>parr\(*>]

| >parr\(*> says...
|
| >He's nowhere where ready to understand Turing's paper. He hasn't
a
| >clue what Un(m) means, and particularly the significance of the
'n'
| >in that expression.
|
| >And nor have you. If you did, you'd know that in his paper,
Turing
| >also proved that for certain, limited, machines, the halting
problem
| >could be solved.
|
| Yes, if you have a limited class of functions that are not
| Turing-complete, then sometimes the halting problem can solved
| for programs in that class. So?

The way I read it was that for certain types of machine (n<4) , he
halting problem was solvable. I may have interpreted it wrongly, in
which case I apologise.

| The interesting issue is whether
| it is solvable for a Turing-complete set of programs.

It was interesting before Turing proved it was not. Now it's just a
fact of life. (That was written with tongue firmly in cheek).

|
| Also, I don't personally think that there is anything special
| about Turing machines. It was the first example of a
Turing-complete
| set of programs, and they are an especially simple type of machine,
| but the issues involved in the halting problem arise in almost
| the same way no matter what model of machine you are using, as
| long as it's Turing-complete.

Out of interest, do you think any currently produced real computers
are Turing Complete? I don't think so because they can' have
infinite length 'tapes'. Again, I could have misunderstood.
|
| Actually, diagonalization is more general than the halting problem.
<...>

Too true. And powerfull with it. I remember the disbelief I had
when I was presented with proof that there are infinities larger than
the countable infinity. Totally counter-intuitive.

And that is where Peter has lost the plot, I fear.

Unless he's an overfed Troll.

 

[Daryl McCullough]

parr\(*> says...

Or may I call you "Laury"?

Out of interest, do you think any currently produced real computers
are Turing Complete? I don't think so because they can' have
infinite length 'tapes'. Again, I could have misunderstood.

Yes, that's right. In C, you can only refer to a limited number
of machine locations (although, really, really, huge).

However, an actual program together with floppy disks is Turing
complete: whenever the program runs out of space it just asks
the user to please enter the next floppy disk. (Or "please enter
the previous floppy disk"). If the user is kindly keeping track
of the order of the floppies, that makes an actual program into
a kind of Turing machine in which one "square of the tape" is
an entire floppy disk, and instead of just two symbols 1 and 0,
it has 10^10^10 symbols (however many possible floppy disk states
there are).

 

[>parr\(*>]

| >parr\(*> says...
|
| Or may I call you "Laury"?

You may call me what you like. 'parr' is temporary, even fish grow
up.
|
| >Out of interest, do you think any currently produced real
computers
| >are Turing Complete? I don't think so because they can' have
| >infinite length 'tapes'. Again, I could have misunderstood.
|
| Yes, that's right. In C, you can only refer to a limited number
| of machine locations (although, really, really, huge).
|
| However, an actual program together with floppy disks is Turing
| complete: whenever the program runs out of space it just asks
| the user to please enter the next floppy disk. (Or "please enter
| the previous floppy disk"). If the user is kindly keeping track
| of the order of the floppies, that makes an actual program into
| a kind of Turing machine in which one "square of the tape" is
| an entire floppy disk, and instead of just two symbols 1 and 0,
| it has 10^10^10 symbols (however many possible floppy disk states
| there are).

Theory vs practice. Always fun.

BTW, I'm surprise you're still trying to 'help' Peter. If he's not a
Troll, he's totally out of his depth an is unlikely ever to realise
how poor his analytic abilities are.

 

[Peter Olcott]

| >parr\(*> says...
|
| Or may I call you "Laury"?

You may call me what you like. 'parr' is temporary, even fish grow
up.
|
| >Out of interest, do you think any currently produced real
computers
| >are Turing Complete? I don't think so because they can' have
| >infinite length 'tapes'. Again, I could have misunderstood.
|
| Yes, that's right. In C, you can only refer to a limited number
| of machine locations (although, really, really, huge).
|
| However, an actual program together with floppy disks is Turing
| complete: whenever the program runs out of space it just asks
| the user to please enter the next floppy disk. (Or "please enter
| the previous floppy disk"). If the user is kindly keeping track
| of the order of the floppies, that makes an actual program into
| a kind of Turing machine in which one "square of the tape" is
| an entire floppy disk, and instead of just two symbols 1 and 0,
| it has 10^10^10 symbols (however many possible floppy disk states
| there are).

Theory vs practice. Always fun.

BTW, I'm surprise you're still trying to 'help' Peter. If he's not a
Troll, he's totally out of his depth an is unlikely ever to realise
how poor his analytic abilities are.

and you are stupid ass.

 

[Peter Olcott]

Proving something does not exist is simple. You show that it's
existence will cause a contradiction. This has been done for the
Halting Problem.

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.

 

[Peter Olcott]

Or SPACE for "no value returned"

The SPACE is the problem.

Now the halt analyzer merely asks the UTM to determine whether
or not it was invoked as a part of the execution of another TM.

If it was then the halt analyzer simply halts. If it was not then it
analyzes the TM and conclusively determines whether or not it
halts, and writes a ONE or a ZERO to a specific location of
its own tape, correspondingly. (1=HALTS 0=DOES_NOT_HALT)

If the halt function encounters anything at all like the LoopIfHalts
function, it simply returns ONE, knowing that it must halt.

 

[>parr\(*>]

| > | > | However, an actual program together with floppy disks is Turing
| > | complete: whenever the program runs out of space it just asks
| > | the user to please enter the next floppy disk. (Or "please
enter
| > | the previous floppy disk"). If the user is kindly keeping track
| > | of the order of the floppies, that makes an actual program into
| > | a kind of Turing machine in which one "square of the tape" is
| > | an entire floppy disk, and instead of just two symbols 1 and 0,
| > | it has 10^10^10 symbols (however many possible floppy disk
states
| > | there are).
| >
| > Theory vs practice. Always fun.
| >
| > BTW, I'm surprise you're still trying to 'help' Peter. If he's
not a
| > Troll, he's totally out of his depth an is unlikely ever to
realise
| > how poor his analytic abilities are.
|
| and you are stupid ass.

Call me stupid if you like, but ass? Juvenile salmon would be more
appropriate. Or perhaps you were mimicking Lord Charles and meant
'stupid arse'.

Actually calling me a stupid kettle of fish might be the most
appropriate rebuke given your own level of ability in your chosen
subject.

Have you wondered why a juvenile salmon was attracted to your
inanities? It's quite simple really. If you go atrolling, you catch
fish. The trouble is that some fish have big teeth such as enchodus
the saber-toothed salmon:
http://www.paleodirect.com/mv5.htm

And now back to your own silliness in:
http://www.halting-problem.com/

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?

If you can, it's high time you started to use the correct terminology
for your chosen field.

If you can't, then you are welcome to be the stupid pot to my stupid
kettle.

If neither, you are a Troll.

 

[Will Twentyman]

Now the halt analyzer merely asks the UTM to determine whether
or not it was invoked as a part of the execution of another TM.

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

If it was then the halt analyzer simply halts. If it was not then it
analyzes the TM and conclusively determines whether or not it
halts, and writes a ONE or a ZERO to a specific location of
its own tape, correspondingly. (1=HALTS 0=DOES_NOT_HALT)

If it halts without a return value, it is not a halt analyzer. Also,
you *claim* it conclusively determinew whether or not it halts. You
have not proven it.

If the halt function encounters anything at all like the LoopIfHalts
function, it simply returns ONE, knowing that it must halt.

But then LoopIfHalts will not halt, which means the halt analyzer was
wrong, which means it's not a halt analyzer.