The Halting Problem is based on an ill-formed question (specified using math symbols) 2012-04-30

[Peter Olcott]

An ill-formed question is defined as any question that lacks a correct answer from the set of possible answers.

The ill-formed question of the self-reference form of the Halting Problem:

M( String Input )
{
if ( H( Input, Input ) )
  Loop Forever;
else
  Exit;
}

<ForAll> H <ElementOfSet> Turing Machines
~<ThereExists> H(M, M) <ElementOfSet> {true, false}

http://www.dionysia.org/html/entities/symbols.html
Specified using standard HTML 4.0 Math Symbol Entities:

&forall H &isin Turing Machines
~&exist H(M, M) &isin {true, false}

H(M, M) // Return value of the invocation of H(M, M)
M is a template that H is lexically included within.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> An ill-formed question is defined as any question that lacks a correct answer
> from the set of possible answers.
>
> The ill-formed question of the self-reference form of the Halting Problem:
>
> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> <ForAll> H <ElementOfSet> Turing Machines
> ~<ThereExists> H(M, M) <ElementOfSet> {true, false}
>
> http://www.dionysia.org/html/entities/symbols.html
> Specified using standard HTML 4.0 Math Symbol Entities:
>
> &forall H &isin Turing Machines
> ~&exist H(M, M) &isin {true, false}

This is plainly wrong. There are lots of machines that return either
true or false when given (M, M) as input. A single counter example is
enough to refute a "forall":

T(a, b) = return true;

> H(M, M) // Return value of the invocation of H(M, M)
> M is a template that H is lexically included within.

You really should make this connection explicit. Most people would use
a subscript M_H to show that M is derived from H, but you
can also use functional notation M(H). The M derived from my T above is
then called M(T), and the TM computation that you think can't return a
value in {true, false} is T(M(T), M(T)) (and it returns true).

--
Ben.

[Peter Olcott]

On 5/1/2012 5:20 PM, Daryl McCullough wrote:
> On Tuesday, May 1, 2012 6:11:33 PM UTC-4, Peter Olcott wrote:
>
>> You have to read what I said before responding to it.
>> The response below does not even apply to the words above.
> Yes, it does. What you wrote is this:

>
>> An ill-formed question is defined as any question that lacks a correct answer> from the set of possible answers.
>> The ill-formed question of the self-reference form of the Halting Problem:
>> M( String Input )
>> {
>> if ( H( Input, Input ) )
>> Loop Forever;
>> else
>> Exit;
>> }
>>
>> <ForAll> H<ElementOfSet> Turing Machines
>> ~<ThereExists> H(M, M)<ElementOfSet> {true, false}

> I'm asking you to apply your definition for the
> specific case of the following H:
>
> H(x,y): if x> y, return true; otherwise, return false.
Good catch!

p--->q (logical implication)

The semantic meaning that tm would actually halt on input is specified by:
Halts(tm, input)

Here is the corrected version, thanks for the excellent counter-example.

<ForAll> H <ElementOfSet> Turing Machines

~<ThereExists> H(M, M) <ElementOfSet> {true, false}---->Halts(tm, input)

[Peter Olcott]

On 5/1/2012 5:52 PM, Daryl McCullough wrote:
> On Tuesday, May 1, 2012 6:34:14 PM UTC-4, Peter Olcott wrote:
>> On 5/1/2012 6:56 AM, Daryl McCullough wrote:
>>> On Monday, April 30, 2012 8:48:25 PM UTC-4, Peter Olcott wrote:
>>>
>>> Your use of mathematics symbols is not really helping.

>> <ForAll> H<ElementOfSet> Turing Machines
>> ~<ThereExists> H(M, M)<ElementOfSet> {true, false}
>>

>> The above forms the precise mathematical specification
>> of what most everyone here has adamantly claimed could
>> not possibly be true.
> That statement is nonsense. Here's a program H(x,y):
> H(x,y): if x> y, return true; otherwise return false.
>
> Obviously H(M,M) will return true or false for every
> input M.
>
>> You have stated that this idea is nonsense many times.
> Yes, it is complete and utter nonsense.
>
> Look, you keep getting irritated that people don't
> pay enough attention to what you have to say. As a
> matter of fact, hundreds of posts have been written
> in response to your ideas. That is much more attention
> than your ideas deserve, since they are, in fact,
> nonsense.
>
> There is only one way to disprove a theorem, and that
> is, to go through the theorem step by step and find
> a step that is invalid.

It is not that the conclusion is false, it is that the conclusion is
entirely based on very subtle error or reasoning.

When people glance at a few of my words before forming their refutation,
they don't have the focus required to discern these subtleties.

> You haven't done that. I
> gave you the actual theorem, and you completely
> ignored it. You think that you can disprove a
> theorem without actually going through the theorem?Here are the steps in the proof of the unsolvability
> of the halting problem:
>
> Definition: If H(x,y) is a computer program, we say that
> H is a "halt decider" if for every computer program M(x),
> and every input I, one of the following is the case:
> (1) H(#M,I) = true, and M(I) halts.
> (2) H(#M,I) = false, and M(I) does not halt.
>
> (Where #M means the code number of M).
>
> Claim: For all computer programs H(x,y) that return
> true or false, there exists a computer program M such
> that one of the following is the case:
>
> (1) M(#M) halts and H(#M,#M) = false.
> (2) M(#M) does not halt, and H(#M,#M) = true.
> (3) M(#M) does not halt, and neither doe H(#M,#M)
>
> Proof: Let M(x) be the program: if H(x,x) = false,
> then halt; otherwise loop.
>
> Theorem: There is no program H(x,y) that is a halt
> decider.
>
> Proof: Immediate, from the definition of halt decider
> and the above claim.
>
> Nothing in that theorem has anything to do with
> "questions", ill-formed or otherwise. You have
> a definition of "halt decider", and you have a
> proof that there is no such thing. If you think
> that there is a mistake in the theorem, then point
> to which step is mistaken.
Thanks for your excellent counter-example in the prior post, that was a
good catch!

The ill-formed question of the self-reference form of the Halting

Problem specified mathematically:

M( String Input )
{
if ( H( Input, Input ) )
Loop Forever;
else
Exit;
}

<ForAll> H <ElementOfSet> Turing Machines

~<ThereExists> H(M, M) <ElementOfSet> {true, false}---->Halts(tm, input)

Additional notational conventions:
p--->q (logical implication)
Halts(tm, input) // tm actually halts on input

[Ben Bacarisse]

This is either meaningless or false. The terms "tm" and "input" are not
bound by any of the quantifiers so in a formal sense it's meaningless.
Less formally, some people take unbound terms to be implicitly
universally quantified (i.e. there is an implicit <ForAll> tm, <ForAll>
input round the whole statement). Both Daryl's and my counter example
would then still apply, though to complete them, we'd have to specify a
"tm" and an "input" as well as an H. We'd just pick any single tm and
input such that Halts(tm, input) = true, and the implication you added
becomes redundant.

--
Ben.

[Peter Olcott]

Yes although too syntactically messy.

[Ben Bacarisse]

So you are saying you intended the meaning that makes your statement
false? OK. We agree on something at last.

BTW, it's not messy at all since it's common to just list the quantified
variables: ForAll H, tm, input ...

>> Both Daryl's and my counter example
>> would then still apply, though to complete them, we'd have to specify a
>> "tm" and an "input" as well as an H. We'd just pick any single tm and
>> input such that Halts(tm, input) = true, and the implication you added
>> becomes redundant.

--
Ben.