Refutation of the DisProof of the Halting Problem

[Bryan Olson]

Moreover, a language that admits a program that decides the halting problem
cannot be powerful enough to program its own interpreter.

There are arguable vacuous cases where that doesn't hold.
Suppose I define a computational language such that for any
program and any input, it outputs 'true'. Now if I define an
encoding of pairs-of-strings to stings, to represent (Machine,
Input), I can claim *any* program is an interpreter, because for
any P, P(Machine, Input) produces the same result as
Machine(Input). What's more, it solves it's halting problem,
since 'true' describes the machine's halting-behavior for any
input.

 

[Andrew Koenig]

There are arguable vacuous cases where that doesn't hold.
Suppose I define a computational language such that for any
program and any input, it outputs 'true'. Now if I define an
encoding of pairs-of-strings to stings, to represent (Machine,
Input), I can claim *any* program is an interpreter, because for
any P, P(Machine, Input) produces the same result as
Machine(Input). What's more, it solves it's halting problem,
since 'true' describes the machine's halting-behavior for any
input.

One might argue that in such a language, it is meaningless to talk about
determining whether a program halts, because every program in that language
halts. Hence, no determination is possible.

 

[Peter Olcott]

Moreover, a language that admits a program that decides the halting problem
cannot be powerful enough to program its own interpreter.

That is simply not true. My C++ void function did indeed solve
any halting problem that allows void functions.

 

[Bryan Olson]

That is simply not true. My C++ void function did indeed solve
any halting problem that allows void functions.

False. Not only was the function never shown, when Peter said
what it determines in a case I asked about, it got the answer
wrong. See:


http://www.google.com/groups&[email protected]

 

[Peter Olcott]

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

The Halting Problem can not be solved within the degree of
expressability of a TM. My solution only worked because of
its more limited degree of expressability.

There is no such thing as a void function in a TM, thus there is
no way to make constructing the counter-example program
impossible for a TM.

Well, the following TM:

StartState: S
HaltState: H
Alphabet: [A-Za-z0-9_]
TransitionFunction:

From: S
With: *
To: H
Moving: Sit

I don't get this last part: Moving Sit?

 

[The Ghost In The Machine]

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

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

The Halting Problem can not be solved within the degree of
expressability of a TM. My solution only worked because of
its more limited degree of expressability.

There is no such thing as a void function in a TM, thus there is
no way to make constructing the counter-example program
impossible for a TM.

Well, the following TM:

StartState: S
HaltState: H
Alphabet: [A-Za-z0-9_]
TransitionFunction:

From: S
With: *
To: H
Moving: Sit

I don't get this last part: Moving Sit?

Turing machines can do three things with their head per cycle:

Left
Right
Sit

The Left and Right should be obvious, and now hopefully Sit is, too.

If you have a better suggestion for the notion, by
all means speak up. IMO, "StayPut" is a bit clumsy.
"SameCell" is equally clumsy but might work. "None"
is a bit too generic.

As you well know, the transition function has domain
State x Alphabet and range State x Alphabet x {Left, Right, Sit}.
This means I erred slightly in the specification, which can
be handwaved-around a bit by a syntax such as

'Write: Same'

or

'Write: No'

(as opposed to 'Write: A' or 'Write: Blank')

But hopefully the idea's clear, regardless;
this machine transitions once and then halts.

 

[Peter Olcott]

In sci.logic, Peter Olcott

Well, the following TM:

StartState: S
HaltState: H
Alphabet: [A-Za-z0-9_]
TransitionFunction:

From: S
With: *
To: H
Moving: Sit

I don't get this last part: Moving Sit?

Turing machines can do three things with their head per cycle:

Left
Right
Sit

The Left and Right should be obvious, and now hopefully Sit is, too.

If you have a better suggestion for the notion, by
all means speak up. IMO, "StayPut" is a bit clumsy.
"SameCell" is equally clumsy but might work. "None"
is a bit too generic.

At each step of every state transition only specify those actions
actually taken. If the head is not moved then simply don't mention
the head.

 

[Jim Burns]

[...]
Turing machines can do three things with their head per cycle:

Left
Right
Sit

The Left and Right should be obvious, and now hopefully Sit is, too.

If you have a better suggestion for the notion, by
all means speak up. IMO, "StayPut" is a bit clumsy.
"SameCell" is equally clumsy but might work. "None"
is a bit too generic.

How about { Left, Right, Here }? It looks more parallel to me
(in the writer's sense, not the mathematician's).

You could also say { MoveLeft, MoveRight, StayHere }, but it's
longer, even redundant, given the category name is Moving.

Jim Burns

 

[The Ghost In The Machine]

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

In sci.logic, Peter Olcott

Well, the following TM:

StartState: S
HaltState: H
Alphabet: [A-Za-z0-9_]
TransitionFunction:

From: S
With: *
To: H
Moving: Sit

I don't get this last part: Moving Sit?

Turing machines can do three things with their head per cycle:

Left
Right
Sit

The Left and Right should be obvious, and now hopefully Sit is, too.

If you have a better suggestion for the notion, by
all means speak up. IMO, "StayPut" is a bit clumsy.
"SameCell" is equally clumsy but might work. "None"
is a bit too generic.

At each step of every state transition only specify those actions
actually taken. If the head is not moved then simply don't mention
the head.

AFAIK, the range is State x Alphabet x Movement, in the standard text.
One could of course use as the range of the transition function:

State union (State x Alphabet) union (State x Alphabet x {Left, Right})

if one wishes, but that's a bit harder to prove stuff with.
The domain, as always, is State x Alphabet.

Not that it matters; you're caught at the moment in an
irrelevancy. This will not help your proof that denying
WillHalt()'s information to LoopIfHalts() will somehow
invalidate Turing's Halting Impossibility Proof.

 

[The Ghost In The Machine]

In sci.logic, Jim Burns
<[email protected]>
wrote

[...]
Turing machines can do three things with their head per cycle:

Left
Right
Sit

The Left and Right should be obvious, and now hopefully Sit is, too.

If you have a better suggestion for the notion, by
all means speak up. IMO, "StayPut" is a bit clumsy.
"SameCell" is equally clumsy but might work. "None"
is a bit too generic.

How about { Left, Right, Here }? It looks more parallel to me
(in the writer's sense, not the mathematician's).

You could also say { MoveLeft, MoveRight, StayHere }, but it's
longer, even redundant, given the category name is Moving.

Jim Burns

An interesting suggestion, though I'm not sure "Here" makes as
much sense as "Sit". I was merely constructing a machine
which was the Turing Machine equivalent of a no-op.

 

[Jim Burns]

[...]

An interesting suggestion, though I'm not sure "Here" makes as
much sense as "Sit". I was merely constructing a machine
which was the Turing Machine equivalent of a no-op.

There is a discussion of obscurity of math expressions currently
in sci.math. Keeping that in mind, I would like to offer these:
instead of ( Right, Left, Sit ) , how about ( Gee, Haw, Whoa )?

Actually, decrement, increment, and no-operation (Dec, Inc, Nop)
seem like it's almost as good a choice. (There may be a problem
with it not being obscure enough.)

Jim Burns

 

[The Ghost In The Machine]

In sci.logic, Jim Burns
<[email protected]>
wrote

[...]

An interesting suggestion, though I'm not sure "Here" makes as
much sense as "Sit". I was merely constructing a machine
which was the Turing Machine equivalent of a no-op.

There is a discussion of obscurity of math expressions currently
in sci.math. Keeping that in mind, I would like to offer these:
instead of ( Right, Left, Sit ) , how about ( Gee, Haw, Whoa )?

Actually, decrement, increment, and no-operation (Dec, Inc, Nop)
seem like it's almost as good a choice. (There may be a problem
with it not being obscure enough.)

Jim Burns

DEC = Digital Equipment Corporation
INC = Incorporated
NOP = Not Our Problem.



Unfortunately for you, I've read _White Fang_, so am at least
somewhat aware of Gee, Haw, MUSH. (Woah is a logical
extension, and anyone who's read cowboy novels -- or for that
matter seen Sylvester Sam trying to stop a camel or "stupid
dragon" -- knows the meaning thereof.)

But if one wants obscure, try -1, 0, +1. Then again, that's
probably way too clear to mathematicians...