Is the Halting Problem merely an ill-formed question?

An ill-formed question is any question that requires an answer from a solution
set where no correct answer exists within this solution set. One example of an
ill-formed question is the following: "How tall are you green or blue?".

Another type of ill-formed question is requiring an answer to be in form
impossible for the respondent to correctly provide. One example of this would be
requiring a mute person to answer a question only in the form of verbal spoken
communication.

void LoopIfHalts(string SourceCode) {
if ( WillHalt(SourceCode, SourceCode) == TRUE )
while (TRUE) // loop forever
;
else
return;
}

int WillHalt(string SourceCode, string InputData) {
if (MalignantSelfReference(SourceCode, InputData))
return MALIGNANT_SELF_REFERENCE;
if ( TheProgramWillHalt(SourceCode, InputData) )
return TRUE;
else
return FALSE;
}

LoopIfHalts(LoopIfHalts);

I propose this assertion, every variation of the above example that attempts to
prove the conclusion of the Halting Problem forms at least one of the two
specified types of ill-formed questions. It is not my burden of proof to show
that the Halting Problem is solvable, I am only at most attempting to show the
prior proofs concluding that it is unsolvable may be incorrect.

Because of this, I am not required to show that the function
MalignantSelfReference(SourceCode, InputData) is computable. This function will
continue to be assumed to be computable, unless and until anyone provides a
specific example showing that it is not computable in a specific instance.

In comp.theory Peter Olcott <NoSpam{}seescreen.com> wrote:

> An ill-formed question is any question that requires an answer from
> a solution set where no correct answer exists within this solution
> set. One example of an ill-formed question is the following: "How
> tall are you green or blue?".

Correct, and has been pointed out to you many times, that isn't a
problem at all here. For the halting problem, given an algorithm and
an input, the required solution set is:

A) The algorithm halts on this input in a finite amount of time
B) Not A.

Clearly the answer is always one of those two.

> Another type of ill-formed question is requiring an answer to be in
> form impossible for the respondent to correctly provide. One example
> of this would be requiring a mute person to answer a question only
> in the form of verbal spoken communication.

This isn't an ill-formed question. Maybe an "unfair" question for
whoever or whatever you're asking, but it certainly does not make it
ill-formed (how about "ill-advised"?). Requiring a mute person to
give a verbal answer is quite a different thing than asking a computer
to give a yes/no answer. Are you saying that there is no way for a
computer to express "yes" or "no"? Funny, I though bits 0 and 1
worked quite well for that...

--

Steve Stringer
sillybanter{}

In sci.logic, Peter Olcott
<NoSpam{}SeeScreen.com>
wrote
on Sun, 22 Oct 2006 09:09:18 -0500
<iYK_g.31745$eZ4.3585{}dukeread06>:
> An ill-formed question is any question that requires an answer from a solution
> set where no correct answer exists within this solution set. One example of an
> ill-formed question is the following: "How tall are you green or blue?".
>
> Another type of ill-formed question is requiring an answer to be in form
> impossible for the respondent to correctly provide. One example of this would be
> requiring a mute person to answer a question only in the form of verbal spoken
> communication.
>
> void LoopIfHalts(string SourceCode) {
> if ( WillHalt(SourceCode, SourceCode) == TRUE )
> while (TRUE) // loop forever
> ;
> else
> return;
> }
>
> int WillHalt(string SourceCode, string InputData) {
> if (MalignantSelfReference(SourceCode, InputData))
> return MALIGNANT_SELF_REFERENCE;
> if ( TheProgramWillHalt(SourceCode, InputData) )
> return TRUE;
> else
> return FALSE;
> }
>
> LoopIfHalts(LoopIfHalts);
>
> I propose this assertion, every variation of the above example that attempts to
> prove the conclusion of the Halting Problem forms at least one of the two
> specified types of ill-formed questions. It is not my burden of proof to show
> that the Halting Problem is solvable, I am only at most attempting to show the
> prior proofs concluding that it is unsolvable may be incorrect.
>
> Because of this, I am not required to show that the function
> MalignantSelfReference(SourceCode, InputData) is computable. This function will
> continue to be assumed to be computable, unless and until anyone provides a
> specific example showing that it is not computable in a specific instance.
>

The function MalignantSelfReference() is not well-defined, let alone
computable; however, one can implement it easily and show that it
might work:

function MalignantSelfReference(String sourceCode, String inputData)
{
return true;
}

This is of course overly paranoid but is a proof-of-concept. Therefore,
this part of the Modified Halting Problem can be solved, even if it is a
trivial solution.

It's a bit like factoring
x^6 - 3*x^5 - 42*x^4 + 28*x^3 - 97*x^2 + 12*x - 32; clearly one of the
factors is (x-8); the other one is an irreducible quintic.

How would you implement MalignantSelfReference()?

--
#191, ewill3{}earthlink.net
Useless C++ Programming Idea #12995733:
bool f(bool g, bool h) { if(g) h = true; else h = false; return h;}

--
Posted via a free Usenet account from http://www.teranews.com

<sillybanter{}> wrote in message news:v2O_g.10504$A27.6378{}trnddc08...
> In comp.theory Peter Olcott <NoSpam{}seescreen.com> wrote:
>
>> An ill-formed question is any question that requires an answer from
>> a solution set where no correct answer exists within this solution
>> set. One example of an ill-formed question is the following: "How
>> tall are you green or blue?".
>
> Correct, and has been pointed out to you many times, that isn't a
> problem at all here. For the halting problem, given an algorithm and
> an input, the required solution set is:
>
> A) The algorithm halts on this input in a finite amount of time
> B) Not A.
>
> Clearly the answer is always one of those two.

Although common sense would tell you this, this conclusion might not be correct.
The example of "How tall are you Red or Not(Red)." is ill-formed because neither
Red nor Not(Red) form numerical quantities of height.

The missing third piece in the above is that the question: "Does the algorithm
halt on this input in a finite amount of time?" is ill-formed for one reason or
another.

>
>> Another type of ill-formed question is requiring an answer to be in
>> form impossible for the respondent to correctly provide. One example
>> of this would be requiring a mute person to answer a question only
>> in the form of verbal spoken communication.
>
> This isn't an ill-formed question. Maybe an "unfair" question for
> whoever or whatever you're asking, but it certainly does not make it
> ill-formed (how about "ill-advised"?). Requiring a mute person to
> give a verbal answer is quite a different thing than asking a computer
> to give a yes/no answer. Are you saying that there is no way for a
> computer to express "yes" or "no"? Funny, I though bits 0 and 1
> worked quite well for that...

Requiring that the answer be in the form of a Boolean, is equivalent.
A) The program halts TRUE
B) The program does not halt FALSE
C) Due to Malignant Self Reference, the halting status of the program derives a
question with no possible correct answer.

>
> --
>
> Steve Stringer
> sillybanter{}
>

"The Ghost In The Machine" <ewill{}sirius.tg00suus7038.net> wrote in message
news:r9ns04-t4t.ln1{}sirius.tg00suus7038.net...
> In sci.logic, Peter Olcott
> <NoSpam{}SeeScreen.com>
> wrote
> on Sun, 22 Oct 2006 09:09:18 -0500
> <iYK_g.31745$eZ4.3585{}dukeread06>:
>> An ill-formed question is any question that requires an answer from a
>> solution
>> set where no correct answer exists within this solution set. One example of
>> an
>> ill-formed question is the following: "How tall are you green or blue?".
>>
>> Another type of ill-formed question is requiring an answer to be in form
>> impossible for the respondent to correctly provide. One example of this would
>> be
>> requiring a mute person to answer a question only in the form of verbal
>> spoken
>> communication.
>>
>> void LoopIfHalts(string SourceCode) {
>> if ( WillHalt(SourceCode, SourceCode) == TRUE )
>> while (TRUE) // loop forever
>> ;
>> else
>> return;
>> }
>>
>> int WillHalt(string SourceCode, string InputData) {
>> if (MalignantSelfReference(SourceCode, InputData))
>> return MALIGNANT_SELF_REFERENCE;
>> if ( TheProgramWillHalt(SourceCode, InputData) )
>> return TRUE;
>> else
>> return FALSE;
>> }
>>
>> LoopIfHalts(LoopIfHalts);
>>
>> I propose this assertion, every variation of the above example that attempts
>> to
>> prove the conclusion of the Halting Problem forms at least one of the two
>> specified types of ill-formed questions. It is not my burden of proof to show
>> that the Halting Problem is solvable, I am only at most attempting to show
>> the
>> prior proofs concluding that it is unsolvable may be incorrect.
>>
>> Because of this, I am not required to show that the function
>> MalignantSelfReference(SourceCode, InputData) is computable. This function
>> will
>> continue to be assumed to be computable, unless and until anyone provides a
>> specific example showing that it is not computable in a specific instance.
>>
>
> The function MalignantSelfReference() is not well-defined, let alone
> computable; however, one can implement it easily and show that it
> might work:
>
> function MalignantSelfReference(String sourceCode, String inputData)
> {
> return true;
> }
>
> This is of course overly paranoid but is a proof-of-concept. Therefore,
> this part of the Modified Halting Problem can be solved, even if it is a
> trivial solution.
>
> It's a bit like factoring
> x^6 - 3*x^5 - 42*x^4 + 28*x^3 - 97*x^2 + 12*x - 32; clearly one of the
> factors is (x-8); the other one is an irreducible quintic.
>
> How would you implement MalignantSelfReference()?

That is not the point. The point is whether or not it can be shown that
MalignantSelfReference() can not be implemented. If it can not be shown that
MSR() can not be implemented, then the proofs that show the HP is not solvable
may fail. This is not at all the same thing as proving that the HP is solvable.

>
> --
> #191, ewill3{}earthlink.net
> Useless C++ Programming Idea #12995733:
> bool f(bool g, bool h) { if(g) h = true; else h = false; return h;}
>
> --
> Posted via a free Usenet account from http://www.teranews.com
>

Peter Olcott wrote:
> That is not the point. The point is whether or not it can be shown that
> MalignantSelfReference() can not be implemented. If it can not be shown that
> MSR() can not be implemented, then the proofs that show the HP is not solvable
> may fail. This is not at all the same thing as proving that the HP is solvable.
If you define the set of all programs which have the MSR property, one
could look at it and either prove or disprove that it is decidable. I
don't want to see a definition of MalignantSelfReference() (I've asked
many times for that...), but a definition in the form MSR = {p | p has
some property} would suffice.

In sci.logic, Peter Olcott
<NoSpam{}SeeScreen.com>
wrote
on Sun, 22 Oct 2006 13:32:10 -0500
<JOO_g.31754$eZ4.8495{}dukeread06>:
>
> "The Ghost In The Machine" <ewill{}sirius.tg00suus7038.net> wrote in message
> news:r9ns04-t4t.ln1{}sirius.tg00suus7038.net...
>> In sci.logic, Peter Olcott
>> <NoSpam{}SeeScreen.com>
>> wrote
>> on Sun, 22 Oct 2006 09:09:18 -0500
>> <iYK_g.31745$eZ4.3585{}dukeread06>:
>>> An ill-formed question is any question that requires an answer from a
>>> solution
>>> set where no correct answer exists within this solution set. One example of
>>> an
>>> ill-formed question is the following: "How tall are you green or blue?".
>>>
>>> Another type of ill-formed question is requiring an answer to be in form
>>> impossible for the respondent to correctly provide. One example of this would
>>> be
>>> requiring a mute person to answer a question only in the form of verbal
>>> spoken
>>> communication.
>>>
>>> void LoopIfHalts(string SourceCode) {
>>> if ( WillHalt(SourceCode, SourceCode) == TRUE )
>>> while (TRUE) // loop forever
>>> ;
>>> else
>>> return;
>>> }
>>>
>>> int WillHalt(string SourceCode, string InputData) {
>>> if (MalignantSelfReference(SourceCode, InputData))
>>> return MALIGNANT_SELF_REFERENCE;
>>> if ( TheProgramWillHalt(SourceCode, InputData) )
>>> return TRUE;
>>> else
>>> return FALSE;
>>> }
>>>
>>> LoopIfHalts(LoopIfHalts);
>>>
>>> I propose this assertion, every variation of the above example that attempts
>>> to
>>> prove the conclusion of the Halting Problem forms at least one of the two
>>> specified types of ill-formed questions. It is not my burden of proof to show
>>> that the Halting Problem is solvable, I am only at most attempting to show
>>> the
>>> prior proofs concluding that it is unsolvable may be incorrect.
>>>
>>> Because of this, I am not required to show that the function
>>> MalignantSelfReference(SourceCode, InputData) is computable. This function
>>> will
>>> continue to be assumed to be computable, unless and until anyone provides a
>>> specific example showing that it is not computable in a specific instance.
>>>
>>
>> The function MalignantSelfReference() is not well-defined, let alone
>> computable; however, one can implement it easily and show that it
>> might work:
>>
>> function MalignantSelfReference(String sourceCode, String inputData)
>> {
>> return true;
>> }
>>
>> This is of course overly paranoid but is a proof-of-concept. Therefore,
>> this part of the Modified Halting Problem can be solved, even if it is a
>> trivial solution.
>>
>> It's a bit like factoring
>> x^6 - 3*x^5 - 42*x^4 + 28*x^3 - 97*x^2 + 12*x - 32; clearly one of the
>> factors is (x-8); the other one is an irreducible quintic.
>>
>> How would you implement MalignantSelfReference()?
>
> That is not the point. The point is whether or not it can be shown that
> MalignantSelfReference() can not be implemented. If it can not be shown that
> MSR() can not be implemented, then the proofs that show the HP is not solvable
> may fail. This is not at all the same thing as proving that the HP is solvable.

No one can show that. MalignantSelfReference() can be implemented, and
the entire framework works. The main problem is that the result is
useless.

An alternate implementation of MalignantSelfReference() would allow for
the testing of known algorithms. To wit:

boolean MalignantSelfReference(String sourceCode, String inputData)
{
if(sourceCode == "Return 1;") return false;
if(sourceCode == "Return 2;") return false;
if(sourceCode == "Return 3;") return false;
...
if(sourceCode == "if(param0) then return 1; else return 2;")
return false;
if(sourceCode == "if(param0) then return 1; else return 3;")
return false;
...

// nope; we don't know the answer.

return true;
}

Not that this is all that useful either; this is merely a codification
of what is already known.

>
>>
>> --
>> #191, ewill3{}earthlink.net
>> Useless C++ Programming Idea #12995733:
>> bool f(bool g, bool h) { if(g) h = true; else h = false; return h;}
>>
>> --
>> Posted via a free Usenet account from http://www.teranews.com
>>
>
>


--
#191, ewill3{}earthlink.net
Useless C++ Programming Idea #8830129:
std::set<...> v; for(..:iterator i = v.begin(); i != v.end(); i++)
if(*i == thing) {...}

--
Posted via a free Usenet account from http://www.teranews.com

In sci.logic, Jens Auer
<jens.auer-news{}betaversion.net>
wrote
on Sun, 22 Oct 2006 21:07:17 +0200
<453bc167{}news.ish.de>:
> Peter Olcott wrote:
>> That is not the point. The point is whether or not it can be shown that
>> MalignantSelfReference() can not be implemented. If it can not be shown that
>> MSR() can not be implemented, then the proofs that show the HP is not solvable
>> may fail. This is not at all the same thing as proving that the HP is solvable.
> If you define the set of all programs which have the MSR property, one
> could look at it and either prove or disprove that it is decidable. I
> don't want to see a definition of MalignantSelfReference() (I've asked
> many times for that...), but a definition in the form MSR = {p | p has
> some property} would suffice.

To do that properly would require some work.

If we assume a machine with an infinite number of registers, each
capable of holding an indefinitely long integer, one might set up
an equivalence partitioning of programs, by trying to equate registers.
For example:

R1 = 10000;
R2 = 1;
while(R1 > 0)
{
R2 *= R3;
R1--;
}

and

R3321 = 10000;
R99128 = 1;
while(R3321 > 0)
{
R99128 *= R1023995;
R3321--;
}

might be termed equivalent.

Once this equivalency is established, one can then attempt to search
for substrings in program A which are equivalent to program B.
If program B is WillHalt, the result becomes obvious.

boolean MalignantSelfReference(String program, String input)
{
return (ProgramContainsEquivalentSubstring(program, WillHalt));
}

There are of course issues with block sequencing and such,
if one wants to implement substring search, but that is a detail.

Unfortunately, this implementation obviously won't work for a far
more fundamental reason. The algorithm

R3321 = 10000;
R99128 = 1;
while(R3321 > 0)
{
R99128 *= R1023995;
R3321++;
R3321--;
R3321--;
}

clearly generates the same output as the two programs
above but is not in the same partition, since there are
two extra instructions.

Or one can implement

R3321 = 10000;
R99128 = 1;
while(R3321 > 0)
{
R99128 *= R1023995;
R3321--;
doSomethingElse();
}

where doSomethingElse() chews on a set of registers which are
completely irrelevant to the calling algorithm.

Or one can just insert the code directly:

R3321 = 10000;
R99128 = 1;
while(R3321 > 0)
{
R99128 *= R1023995;
R3321--;
<any code not involving R3321, R99128, or R1032995>
}

Hhppy code-hunting, WillHalt()! :-)

If one doesn't like registers one might contemplate a pure stack-based
machine; this machine's code might be easier to search for substrings.

--
#191, ewill3{}earthlink.net
Windows Vista. Because it's time to refresh your hardware. Trust us.

--
Posted via a free Usenet account from http://www.teranews.com

"Peter Olcott" <NoSpam{}SeeScreen.com> writes:

> An ill-formed question is any question that requires an answer from
> a solution set where no correct answer exists within this solution
> set. One example of an ill-formed question is the following: "How
> tall are you green or blue?".

You give a general definition of ill-formed here but I am wary of
applying it in case I miss something subtle, Help me out by commenting
on this self-test of my understanding:

A programmer might choose one of three common methods if he/she needs
to specify a set of string (to check for valid input maybe). In a
simple case one could just give the set of strings (a list maybe).
For a more complex cases one might use a regular expression which
matches only valid inputs (email addresses for example). For move
complex inputs one might need a context-free grammar (if the input
was, say an equation to evaluate). Which of the following questions are
well- (or ill-) formed (my opinion also given for you to asses my
understanding of your definition above):

1. Give two (finite) sets of strings, do they describe the same set if
inputs? (I think is a well-formed question.)

What is your opinion?

2. Given two (finite) regular expressions, do they describe the same
set of inputs? (Well-formed as well, I think.)

What is your opinion?

3. Given two (finite) CFGs, do they describe the same set or inputs?
(Again, well-formed, in my opinion.)

Again, what do you say? Am I applying your definition correctly?

I presume that if I suggested a fourth case: 4. Given two Turing
Machines, M1 and M2, asking if they describe the same set of strings
(that is the sets of inputs that make M1 and M2 enter an accepting
state are one and the same) you would say this is ill-defined. Yes?
I say it is well-defined and I can not see what in your definitions
changes anywhere along the line from 1 to 2 to 3 to 4. Can you add
some more?

--
Ben.

The Ghost In The Machine wrote:
>>>> Because of this, I am not required to show that the function
>>>> MalignantSelfReference(SourceCode, InputData) is computable. This function
>>>> will
>>>> continue to be assumed to be computable, unless and until anyone provides a
>>>> specific example showing that it is not computable in a specific instance.
>>>>
>>> The function MalignantSelfReference() is not well-defined, let alone
>>> computable; however, one can implement it easily and show that it
>>> might work:
In another thread, Peter tried to give a real definition of MSR:
int MalignantSelfReference(SourceCode, InputData) {
if ( IsSourceCode(InputData) )
if ( MatchSelfReferencePattern(SourceCode, InputData) )
if ( DetectedSelfReferenceTogglesTheReturnValue(SourceC ode,
InputData) )
return TRUE;
return FALSE;
}

There are two problems connected to the computability of this function:
1) MatchSelfReferencePattern has to find expressions equivalent to
WillHalt(s,s) == TRUE
2) DetectedSelfReferenceTogglesTheReturnValue(SourceC ode,
InputData) has to check if the expression following the condition with
the self-reference computes the opposite of WillHalt(s,s) == TRUE. In
other words, it has to evaluate the epxression WillHalt("while (TRUE);")
in the given example, which is solving the halting problem itself.

Looks like WillHalt and MatchSelfReferencePattern are circular
definitions and hence not valid or useful.