Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: Proof that Decidability is Always Decidable
150 views
Skip to first unread message
Peter Olcott
Apr 18, 2012, 8:33:54 PM4/18/12
to
On 4/18/2012 7:26 PM, Joshua Cranmer wrote:
> On 4/18/2012 5:19 PM, Peter Olcott wrote:
>> On 4/18/2012 9:07 AM, Joshua Cranmer wrote:
>>> On 4/18/2012 5:15 AM, Peter Olcott wrote:
>>>> This is a partial function on the subset of the input that is
>>>> decidable
>>>> and does halt.
>>>
>>> You have not established that such a function would be computable. See
>>> my other response to your message.
>>>
>>
>> Try and show a valid counter-example where it is not computable.
>
> Note that your function is not sufficiently well-defined, as you are
> still incredibly vague on what "decidability" is, especially since you
> treat it as a global invariant property yet define it with respect to
> an unnamed Turing machine.
"Decidability" has been completely specified as of the first posting of
this thread, please look at this again.
> On 4/18/2012 5:19 PM, Peter Olcott wrote:
>> On 4/18/2012 9:07 AM, Joshua Cranmer wrote:
>>> On 4/18/2012 5:15 AM, Peter Olcott wrote:
>>>> This is a partial function on the subset of the input that is
>>>> decidable
>>>> and does halt.
>>>
>>> You have not established that such a function would be computable. See
>>> my other response to your message.
>>>
>>
>> Try and show a valid counter-example where it is not computable.
>
> Note that your function is not sufficiently well-defined, as you are
> still incredibly vague on what "decidability" is, especially since you
> treat it as a global invariant property yet define it with respect to
> an unnamed Turing machine.
"Decidability" has been completely specified as of the first posting of
this thread, please look at this again.
Joshua Cranmer
Apr 18, 2012, 8:46:48 PM4/18/12
to
On 4/18/2012 7:33 PM, Peter Olcott wrote:
> "Decidability" has been completely specified as of the first posting of
> this thread, please look at this again.
I see one of two possible definitions in the first post:
> "Decidability" has been completely specified as of the first posting of
> this thread, please look at this again.
1. Does not halt.
2. An input is decidable (i.e., a circular definition).
In the first sense, it is exactly equivalent to the Halting problem, and
so the property is known to be uncomputable. In the second sense, it has
a circular definition, so no conclusion can be reached.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
Peter Olcott
Apr 18, 2012, 9:15:03 PM4/18/12
to
On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
> On 4/18/2012 7:33 PM, Peter Olcott wrote:
>> "Decidability" has been completely specified as of the first posting of
>> this thread, please look at this again.
>
> I see one of two possible definitions in the first post:
> 1. Does not halt.
Yes this is it.
> On 4/18/2012 7:33 PM, Peter Olcott wrote:
>> "Decidability" has been completely specified as of the first posting of
>> this thread, please look at this again.
>
> I see one of two possible definitions in the first post:
> 1. Does not halt.
> 2. An input is decidable (i.e., a circular definition).
>
> In the first sense, it is exactly equivalent to the Halting problem,
> and so the property is known to be uncomputable.
No, not at all. Look at it again and see if you can see the difference.
>
> In the first sense, it is exactly equivalent to the Halting problem,
> and so the property is known to be uncomputable.
Peter Olcott
Apr 18, 2012, 10:09:16 PM4/18/12
to
On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
> On 4/18/2012 7:33 PM, Peter Olcott wrote:
>> "Decidability" has been completely specified as of the first posting of
>> this thread, please look at this again.
>
> I see one of two possible definitions in the first post:
> 1. Does not halt.
> 2. An input is decidable (i.e., a circular definition).
>
Actually both of these are incorrect.
>> "Decidability" has been completely specified as of the first posting of
>> this thread, please look at this again.
>
> I see one of two possible definitions in the first post:
> 1. Does not halt.
> 2. An input is decidable (i.e., a circular definition).
>
Leif Roar Moldskred
Apr 18, 2012, 10:19:34 PM4/18/12
to
In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:
>
>> *sigh* How do you propose to distinguish between cases (a) and (b) in
>> a way that is guaranteed to complete in finite time?
> Provide any simple example, I will show you how.
You have to be able to show that you can do it for _any_ TM. Showing
it for a simple example would prove nothing.
> As far as I can tell the only possible instance of an infinite time
> requirement is if the Halt decider simulates its input TM and the input
> TM does not halt. If it is given the the Halt decider does not simulate
> its input TM, then it can be concluded that the time to decide is finite.
In other words, you're just blowing smoke and assuming the existence
of what you're trying to prove. Not that this hasn't been apparent
long before now, of course, but honestly -- who do you think you're
fooling at this stage? Yourself?
--
Leif Roar Moldskred
>
>> *sigh* How do you propose to distinguish between cases (a) and (b) in
>> a way that is guaranteed to complete in finite time?
> Provide any simple example, I will show you how.
You have to be able to show that you can do it for _any_ TM. Showing
it for a simple example would prove nothing.
> As far as I can tell the only possible instance of an infinite time
> requirement is if the Halt decider simulates its input TM and the input
> TM does not halt. If it is given the the Halt decider does not simulate
> its input TM, then it can be concluded that the time to decide is finite.
In other words, you're just blowing smoke and assuming the existence
of what you're trying to prove. Not that this hasn't been apparent
long before now, of course, but honestly -- who do you think you're
fooling at this stage? Yourself?
--
Leif Roar Moldskred
Bryan
Apr 18, 2012, 11:51:49 PM4/18/12
to
Peter Olcott wrote:
> Bryan wrote:
> > Peter Olcott wrote:
> >> Boolean Halts(String tm, String input)
> >> {
> >> if tm halts on input
> > How, at this point, could you think that's decidable?
>
> There are only three possibilities:
> (a) Halting
> (b) Not Halting
> (c) Undecidable
(a) and (b) are mutually exclusive and jointly exhaustive.
An individual instance of the halting problem cannot be Turing-
undecidable. Any finite language is decidable. Peter, you said you
have, if I remember correctly, four textbooks on theory of
computation. How could you not know that?
> If it is not either (b) or (c) then it goes to here.
The given tm either halts on the given input, or does not halt on the
given input.
> This is rte partial function that Patricia wrote about yesterday.
Look at what you wrote: " if tm halts on input". Whatever you are
talking about now, I was talking about what you wrote.
> No this is false. Halts() always halts. It only examines the input TM's
> specification, it does not run it.
You did not show any TM, nor pseudo code, that does *either* examines
or runs it.
> > You've left undefined how you answer, "if tm halts on input". Until
> > you do so, there's not telling whether Decidable(M, M) returns or runs
> > forever.
>
> It is a partial function on the subset of the input that is decidable
> and does halt. In every other case it halts and returns false.
You've still left undefined how you answer, "if tm halts on input".
Until you do so, there's no telling what it does on that input.
--Bryan
> Bryan wrote:
> > Peter Olcott wrote:
> >> Boolean Halts(String tm, String input)
> >> {
> >> if tm halts on input
> > How, at this point, could you think that's decidable?
>
> There are only three possibilities:
> (a) Halting
> (b) Not Halting
> (c) Undecidable
(a) and (b) are mutually exclusive and jointly exhaustive.
An individual instance of the halting problem cannot be Turing-
undecidable. Any finite language is decidable. Peter, you said you
have, if I remember correctly, four textbooks on theory of
computation. How could you not know that?
> If it is not either (b) or (c) then it goes to here.
The given tm either halts on the given input, or does not halt on the
given input.
> This is rte partial function that Patricia wrote about yesterday.
Look at what you wrote: " if tm halts on input". Whatever you are
talking about now, I was talking about what you wrote.
> No this is false. Halts() always halts. It only examines the input TM's
> specification, it does not run it.
You did not show any TM, nor pseudo code, that does *either* examines
or runs it.
> > You've left undefined how you answer, "if tm halts on input". Until
> > you do so, there's not telling whether Decidable(M, M) returns or runs
> > forever.
>
> It is a partial function on the subset of the input that is decidable
> and does halt. In every other case it halts and returns false.
You've still left undefined how you answer, "if tm halts on input".
Until you do so, there's no telling what it does on that input.
--Bryan
Owen Jacobson
Apr 18, 2012, 11:59:42 PM4/18/12
to
Stylistic red pen time!
On 2012-04-17 23:44:14 +0000, Peter Olcott said:
> Boolean Halts(String tm, String input)
> {
> if tm halts on input
> // tm is a valid TM and halting is decidable
Inconsistent indentation (the 'if' is indented by three spaces; the
comment by a further two spaces).
> return true;
> else // anything else, such as not decidable,
> return false; // not a valid TM, not halting
Inconsistent indentation (now the second level of indentation is only
one space).
> }
>
> // DecidabilityDecider
Function comment reiterates the function name without adding any information.
> Boolean Decidable(String tm, String input)
> {
> if (Halts(tm, input))
> return true;
> else
> return false;
Inconsistent indentation again.
> }
Statement groups of the form 'if (x) return true; else return false;'
can be replaced with 'return x;' in every language with a boolean type.
The 'if' version is longer without adding clarity or meaning.
More generally, the 'Decidable' function is exactly the 'Halts'
function and could be removed entirely. If you really think 'Halts'
needs two names, use a simpler implementation that passes the
parameters and return value straight through to and from Halts, or use
whatever facility your language provides for aliasing (function
pointers, delegates, preprocessor shenanigans, or whatever).
> M( String Input )
M has no return type, inconsistent with other functions in your typed,
C-like pseudolanguage. This is done without explanation. If your
language has (typeless) procedures, that's unusual enough to deserve
mention.
Whitespace use here is inconsistent with the rest of your code.
M's parameters are capitalized, but every other function's parameters
are strictly lowercase.
> {
> if ( Decidable( Input, Input ) )
No leading indentation for the statements within this function, unlike
every other function.
Whitespace use here is inconsistent with the rest of your code.
> Loop Forever;
An unexplained lapse into natural language for a very simple element of
your program.
> else
> Exit;
Given the more obviously natural-language use of "Loop Forever" above,
is "Exit" meant to be a symbol in your language such as a call to a
procedure or a special statement, or is it meant to be a prose
description of that branch of the program's behaviour (which would be
odd, since you already used 'return' above to exit from functions)?
Clarify.
> }
>
> Decidable(M, M); // Correctly returns False.
Are whatever values that bare function names evaluate to in your C-like
pseudolanguage implicitly convertible to meaningful String values?
Shouldn't you spell that out more explicitly, given how badly it
violates the principle of least surprise? Alternately, this line is
missing some conversions.
This pseudocode is incredibly sloppy and it points to a lot of bad
habits. Those habits will lead to confusing, hard-to-follow code and
confusing, hard-to-reason-about systems. If you write real code like
this, please, take some pride in your work and clean it up, then keep
it clean as you revise it.
I'm not even going to go into the gaping logical problems in your
pseudocode or in your choice of names. George is already doing a great
job of yelling at you about that.
-o
(Do you even *have* a habitual coding style?)
On 2012-04-17 23:44:14 +0000, Peter Olcott said:
> Boolean Halts(String tm, String input)
> {
> if tm halts on input
Inconsistent indentation (the 'if' is indented by three spaces; the
comment by a further two spaces).
> return true;
> else // anything else, such as not decidable,
> return false; // not a valid TM, not halting
Inconsistent indentation (now the second level of indentation is only
one space).
> }
>
> // DecidabilityDecider
Function comment reiterates the function name without adding any information.
> Boolean Decidable(String tm, String input)
> {
> if (Halts(tm, input))
> return true;
> else
> return false;
Inconsistent indentation again.
> }
Statement groups of the form 'if (x) return true; else return false;'
can be replaced with 'return x;' in every language with a boolean type.
The 'if' version is longer without adding clarity or meaning.
More generally, the 'Decidable' function is exactly the 'Halts'
function and could be removed entirely. If you really think 'Halts'
needs two names, use a simpler implementation that passes the
parameters and return value straight through to and from Halts, or use
whatever facility your language provides for aliasing (function
pointers, delegates, preprocessor shenanigans, or whatever).
> M( String Input )
M has no return type, inconsistent with other functions in your typed,
C-like pseudolanguage. This is done without explanation. If your
language has (typeless) procedures, that's unusual enough to deserve
mention.
Whitespace use here is inconsistent with the rest of your code.
M's parameters are capitalized, but every other function's parameters
are strictly lowercase.
> {
> if ( Decidable( Input, Input ) )
No leading indentation for the statements within this function, unlike
every other function.
Whitespace use here is inconsistent with the rest of your code.
> Loop Forever;
An unexplained lapse into natural language for a very simple element of
your program.
> else
> Exit;
Given the more obviously natural-language use of "Loop Forever" above,
is "Exit" meant to be a symbol in your language such as a call to a
procedure or a special statement, or is it meant to be a prose
description of that branch of the program's behaviour (which would be
odd, since you already used 'return' above to exit from functions)?
Clarify.
> }
>
> Decidable(M, M); // Correctly returns False.
Are whatever values that bare function names evaluate to in your C-like
pseudolanguage implicitly convertible to meaningful String values?
Shouldn't you spell that out more explicitly, given how badly it
violates the principle of least surprise? Alternately, this line is
missing some conversions.
This pseudocode is incredibly sloppy and it points to a lot of bad
habits. Those habits will lead to confusing, hard-to-follow code and
confusing, hard-to-reason-about systems. If you write real code like
this, please, take some pride in your work and clean it up, then keep
it clean as you revise it.
I'm not even going to go into the gaping logical problems in your
pseudocode or in your choice of names. George is already doing a great
job of yelling at you about that.
-o
(Do you even *have* a habitual coding style?)
Joshua Cranmer
Apr 19, 2012, 1:08:21 AM4/19/12
to
On 4/18/2012 9:09 PM, Peter Olcott wrote:
> On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
>> On 4/18/2012 7:33 PM, Peter Olcott wrote:
>>> "Decidability" has been completely specified as of the first posting of
>>> this thread, please look at this again.
>>
>> I see one of two possible definitions in the first post:
>> 1. Does not halt.
>> 2. An input is decidable (i.e., a circular definition).
>>
> Actually both of these are incorrect.
Then your first post is wrong on more than one level...
> On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
>> On 4/18/2012 7:33 PM, Peter Olcott wrote:
>>> "Decidability" has been completely specified as of the first posting of
>>> this thread, please look at this again.
>>
>> I see one of two possible definitions in the first post:
>> 1. Does not halt.
>> 2. An input is decidable (i.e., a circular definition).
>>
> Actually both of these are incorrect.
Jussi Piitulainen
Apr 19, 2012, 2:14:42 AM4/19/12
to
Peter Olcott <NoS...@OCR4Screen.com> writes:
while 2 * n = p + q where p and q are primes do
n := n + 1;
end.
There clearly is a Turing machine that computes the above. Does it
halt? It doesn't use any input, but since you have such a problem with
the empty string, I further specify, completely arbitrarily, that the
machine represents the numbers 1, 2, 3, ..., 10, 11, ... as sequences
of decimal digits and the initial contents of the tape are 314159.
> As far as I can tell the only possible instance of an infinite time
> requirement is if the Halt decider simulates its input TM and the
> input TM does not halt. If it is given the the Halt decider does not
> simulate its input TM, then it can be concluded that the time to
> decide is finite.
What a remarkable leap of logic, from your own lack of imagination to
complete certainty. To even start to convince anybody else, you would
certainly have to say something positive of what any of your deciders
_do_.
Start with the above procedure. It is not known to halt. What would
your two purported deciders do about it?
> On 4/18/2012 7:45 AM, Leif Roar Moldskred wrote:
> > In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
> >
> > In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
> >
> >> There are only three possibilities:
> >> (a) Halting
> >> (b) Not Halting
> >> (c) Undecidable
> >> (a) Halting
> >> (b) Not Halting
> >> (c) Undecidable
> >> If it is not either (b) or (c) then it goes to here.
> > *sigh* How do you propose to distinguish between cases (a) and (b) in
> > a way that is guaranteed to complete in finite time?
>
> Provide any simple example, I will show you how.
var n := 1;
> > a way that is guaranteed to complete in finite time?
>
> Provide any simple example, I will show you how.
while 2 * n = p + q where p and q are primes do
n := n + 1;
end.
There clearly is a Turing machine that computes the above. Does it
halt? It doesn't use any input, but since you have such a problem with
the empty string, I further specify, completely arbitrarily, that the
machine represents the numbers 1, 2, 3, ..., 10, 11, ... as sequences
of decimal digits and the initial contents of the tape are 314159.
> As far as I can tell the only possible instance of an infinite time
> requirement is if the Halt decider simulates its input TM and the
> input TM does not halt. If it is given the the Halt decider does not
> simulate its input TM, then it can be concluded that the time to
> decide is finite.
complete certainty. To even start to convince anybody else, you would
certainly have to say something positive of what any of your deciders
_do_.
Start with the above procedure. It is not known to halt. What would
your two purported deciders do about it?
Peter Olcott
Apr 19, 2012, 5:52:32 AM4/19/12
to
On 4/18/2012 9:19 PM, Leif Roar Moldskred wrote:
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>> >
>>> >> *sigh* How do you propose to distinguish between cases (a) and (b) in
>>> >> a way that is guaranteed to complete in finite time?
>> > Provide any simple example, I will show you how.
> You have to be able to show that you can do it for_any_ TM. Showing
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>> >
>>> >> *sigh* How do you propose to distinguish between cases (a) and (b) in
>>> >> a way that is guaranteed to complete in finite time?
>> > Provide any simple example, I will show you how.
> it for a simple example would prove nothing.
For the time being call it the Decidability thesis:
Decidability is always Decidable.
In other words there can not possibly exist any example showing that
Decidability is not always decidable. Not wanting to unravel convoluted
examples is only my own personal preference, not a limit to the thesis.
Peter Olcott
Apr 19, 2012, 5:54:39 AM4/19/12
to
On 4/18/2012 10:51 PM, Bryan wrote:
> Peter Olcott wrote:
>> > Bryan wrote:
>>> > > Peter Olcott wrote:
>>>> > >> Boolean Halts(String tm, String input)
>>>> > >> {
>>>> > >> if tm halts on input
>>> > > How, at this point, could you think that's decidable?
>> >
>> > There are only three possibilities:
>> > (a) Halting
>> > (b) Not Halting
>> > (c) Undecidable
> (a) and (b) are mutually exclusive and jointly exhaustive.
No this is a false statement when referring to the possible return
> Peter Olcott wrote:
>> > Bryan wrote:
>>> > > Peter Olcott wrote:
>>>> > >> Boolean Halts(String tm, String input)
>>>> > >> {
>>>> > >> if tm halts on input
>>> > > How, at this point, could you think that's decidable?
>> >
>> > There are only three possibilities:
>> > (a) Halting
>> > (b) Not Halting
>> > (c) Undecidable
> (a) and (b) are mutually exclusive and jointly exhaustive.
values of every specific instance of TM/input pairs.
Peter Olcott
Apr 19, 2012, 5:59:40 AM4/19/12
to
On 4/19/2012 12:08 AM, Joshua Cranmer wrote:
> On 4/18/2012 9:09 PM, Peter Olcott wrote:
>> On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
>>> On 4/18/2012 7:33 PM, Peter Olcott wrote:
>>>> "Decidability" has been completely specified as of the first
>>>> posting of
>>>> this thread, please look at this again.
>>>
>>> I see one of two possible definitions in the first post:
>>> 1. Does not halt.
>>> 2. An input is decidable (i.e., a circular definition).
>>>
>> Actually both of these are incorrect.
>
> Then your first post is wrong on more than one level...
>
No, you simply did not bother to pay enough attention:
> On 4/18/2012 9:09 PM, Peter Olcott wrote:
>> On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
>>> On 4/18/2012 7:33 PM, Peter Olcott wrote:
>>>> "Decidability" has been completely specified as of the first
>>>> posting of
>>>> this thread, please look at this again.
>>>
>>> I see one of two possible definitions in the first post:
>>> 1. Does not halt.
>>> 2. An input is decidable (i.e., a circular definition).
>>>
>> Actually both of these are incorrect.
>
> Then your first post is wrong on more than one level...
>
The return value of halts == decidable
Leif Roar Moldskred
Apr 19, 2012, 6:03:09 AM4/19/12
to
In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:
> For the time being call it the Decidability thesis:
> Decidability is always Decidable.
Why on earth should we make that assumption, especially considering
> For the time being call it the Decidability thesis:
> Decidability is always Decidable.
that it directly contradicts the quite robust and time-tested, not to
mention _formal_, proofs that the Halting Problem is undecideable?
Your whole argument boils down tos "Ignoring what I don't understand
and assuming I'm right, I'm right." The problem is that you're
_wrong_.
--
Leif Roar Moldskred
Peter Olcott
Apr 19, 2012, 6:08:41 AM4/19/12
to
On 4/19/2012 1:14 AM, Jussi Piitulainen wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>> On 4/18/2012 7:45 AM, Leif Roar Moldskred wrote:
>>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>>
>>>> There are only three possibilities:
>>>> (a) Halting
>>>> (b) Not Halting
>>>> (c) Undecidable
>>>> If it is not either (b) or (c) then it goes to here.
>>> *sigh* How do you propose to distinguish between cases (a) and (b) in
>>> a way that is guaranteed to complete in finite time?
>> Provide any simple example, I will show you how.
> var n := 1;
> while 2 * n = p + q where p and q are primes do
> n := n + 1;
> end.
>
> There clearly is a Turing machine that computes the above. Does it
> halt? It doesn't use any input, but since you have such a problem with
> the empty string, I further specify, completely arbitrarily, that the
> machine represents the numbers 1, 2, 3, ..., 10, 11, ... as sequences
> of decimal digits and the initial contents of the tape are 314159.
The answer that I provided to Daryl regarding halting if the sequence of
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>> On 4/18/2012 7:45 AM, Leif Roar Moldskred wrote:
>>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>>
>>>> There are only three possibilities:
>>>> (a) Halting
>>>> (b) Not Halting
>>>> (c) Undecidable
>>>> If it is not either (b) or (c) then it goes to here.
>>> *sigh* How do you propose to distinguish between cases (a) and (b) in
>>> a way that is guaranteed to complete in finite time?
>> Provide any simple example, I will show you how.
> var n := 1;
> while 2 * n = p + q where p and q are primes do
> n := n + 1;
> end.
>
> There clearly is a Turing machine that computes the above. Does it
> halt? It doesn't use any input, but since you have such a problem with
> the empty string, I further specify, completely arbitrarily, that the
> machine represents the numbers 1, 2, 3, ..., 10, 11, ... as sequences
> of decimal digits and the initial contents of the tape are 314159.
9999999999999999 exists within PI, applies equally to any difficult
problems of this sort. Difficulty does not logically entail undecidable.
Allowing for an unlimited amount of technological advancement permits
problems of this sort to be solved without requiring an exhaustive
search of an infinite set. An unlimited amount of technological
advancement would create a Turing Machine that progressively approaches
omniscience.
Peter Olcott
Apr 19, 2012, 6:50:28 AM4/19/12
to
On 4/18/2012 10:51 PM, Bryan wrote:
> Peter Olcott wrote:
>> > Bryan wrote:
>>> > > Peter Olcott wrote:
>>>> > >> Boolean Halts(String tm, String input)
>>>> > >> {
>>>> > >> if tm halts on input
>>> > > How, at this point, could you think that's decidable?
>> >
>> > There are only three possibilities:
>> > (a) Halting
>> > (b) Not Halting
>> > (c) Undecidable
> (a) and (b) are mutually exclusive and jointly exhaustive.
There are three possible choices not two:
> Peter Olcott wrote:
>> > Bryan wrote:
>>> > > Peter Olcott wrote:
>>>> > >> Boolean Halts(String tm, String input)
>>>> > >> {
>>>> > >> if tm halts on input
>>> > > How, at this point, could you think that's decidable?
>> >
>> > There are only three possibilities:
>> > (a) Halting
>> > (b) Not Halting
>> > (c) Undecidable
> (a) and (b) are mutually exclusive and jointly exhaustive.
(a) It halts
(b) It does not halt
(c) Can't say whether it halts or not
The Halt Decider that I provided halts in its accept state indicating
that the input TM will halt on its input otherwise it halts in its
reject state. The Halt Decider halts in its reject state whenever it can
not correctly halt in its accept state.
This includes (but is not limited to):
(a) The input TM will *not* halt on its input.
(b) The input TM may halt, yet the Halt Decider can not halt in its
accept state because this will change the answer.
Peter Olcott
Apr 19, 2012, 6:52:10 AM4/19/12
to
On 4/19/2012 5:03 AM, Leif Roar Moldskred wrote:
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>
>> For the time being call it the Decidability thesis:
>> Decidability is always Decidable.
> Why on earth should we make that assumption, especially considering
> that it directly contradicts the quite robust and time-tested, not to
> mention _formal_, proofs that the Halting Problem is undecideable?
If you try and disprove it you will fail.
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>
>> For the time being call it the Decidability thesis:
>> Decidability is always Decidable.
> Why on earth should we make that assumption, especially considering
> that it directly contradicts the quite robust and time-tested, not to
> mention _formal_, proofs that the Halting Problem is undecideable?
Jussi Piitulainen
Apr 19, 2012, 8:57:56 AM4/19/12
to
Peter Olcott writes:
> On 4/19/2012 1:14 AM, Jussi Piitulainen wrote:
> On 4/19/2012 1:14 AM, Jussi Piitulainen wrote:
> > Peter Olcott writes:
> >> On 4/18/2012 7:45 AM, Leif Roar Moldskred wrote:
> >> On 4/18/2012 7:45 AM, Leif Roar Moldskred wrote:
> >>> In comp.theory Peter Olcott wrote:
> >>>
> >>>> There are only three possibilities:
> >>>> (a) Halting
> >>>> (b) Not Halting
> >>>> (c) Undecidable
> >>>> If it is not either (b) or (c) then it goes to here.
> >>> *sigh* How do you propose to distinguish between cases (a) and (b) in
> >>> a way that is guaranteed to complete in finite time?
> >> Provide any simple example, I will show you how.
> >
> > var n := 1;
> > while 2 * n = p + q where p and q are primes do
> > n := n + 1;
> > end.
> >
> > There clearly is a Turing machine that computes the above. Does it
> > halt? It doesn't use any input, but since you have such a problem
> > with the empty string, I further specify, completely arbitrarily,
> > that the machine represents the numbers 1, 2, 3, ..., 10, 11,
> > ... as sequences of decimal digits and the initial contents of the
> > tape are 314159.
>
> The answer that I provided to Daryl regarding halting if the
> sequence of 9999999999999999 exists within PI, applies equally to
> any difficult problems of this sort. Difficulty does not logically
> entail undecidable.
Agreed. But the question is outrageously simple, your answer is mere
> >>>
> >>>> There are only three possibilities:
> >>>> (a) Halting
> >>>> (b) Not Halting
> >>>> (c) Undecidable
> >>>> If it is not either (b) or (c) then it goes to here.
> >>> *sigh* How do you propose to distinguish between cases (a) and (b) in
> >>> a way that is guaranteed to complete in finite time?
> >> Provide any simple example, I will show you how.
> >
> > var n := 1;
> > while 2 * n = p + q where p and q are primes do
> > n := n + 1;
> > end.
> >
> > There clearly is a Turing machine that computes the above. Does it
> > halt? It doesn't use any input, but since you have such a problem
> > with the empty string, I further specify, completely arbitrarily,
> > that the machine represents the numbers 1, 2, 3, ..., 10, 11,
> > ... as sequences of decimal digits and the initial contents of the
> > tape are 314159.
>
> The answer that I provided to Daryl regarding halting if the
> sequence of 9999999999999999 exists within PI, applies equally to
> any difficult problems of this sort. Difficulty does not logically
> entail undecidable.
handwaving, and nobody else knows either.
> Allowing for an unlimited amount of technological advancement
> permits problems of this sort to be solved without requiring an
> exhaustive search of an infinite set. An unlimited amount of
> technological advancement would create a Turing Machine that
> progressively approaches omniscience.
Anyway, if the mighty computer of the future told you that the above
program never halts, or that it eventually halts, would you believe
it? What if there were two such computers, would you be confident of
the answer after only asking one?
If such a computer took a very long time coming up with the answer,
would you still _believe_ that it _would_ give your grandchildren, or
maybe their grandchildren, the _correct_ answer? Instead of giving an
incorrect answer or apologizing for the inconvenience.
> >> As far as I can tell the only possible instance of an infinite
> >> time requirement is if the Halt decider simulates its input TM
> >> and the input TM does not halt. If it is given the the Halt
> >> decider does not simulate its input TM, then it can be concluded
> >> that the time to decide is finite.
> >
> > What a remarkable leap of logic, from your own lack of imagination
> > to complete certainty. To even start to convince anybody else, you
> > would certainly have to say something positive of what any of your
> > deciders _do_.
> >
> > Start with the above procedure. It is not known to halt. What
> > would your two purported deciders do about it?
though in a completely unspecified way, until they come up with an
answer, this always takes a finite time, and the answer is always
correct. Is that it?
And you "prove" this by naive technological optimism.
Peter Olcott
Apr 19, 2012, 4:16:34 PM4/19/12
to
There are two ways that it may be decidable:
(1) Brute force keep testing every combination until the answer is
found. This will not work if the answer does not exist, yet it is not
known that the answer does not exist so the Decidability thesis is not
refuted.
(2) A new method of mathematical proof is developed that can determine
the answer without an exhaustive search of an infinite set.
Bryan
Apr 19, 2012, 4:51:29 PM4/19/12
to
Peter Olcott wrote:
> Bryan wrote:
> > Peter Olcott wrote:
> >> > There are only three possibilities:
> >> > (a) Halting
> >> > (b) Not Halting
> >> > (c) Undecidable
> > (a) and (b) are mutually exclusive and jointly exhaustive.
>
> There are three possible choices not two:
> (a) It halts
> (b) It does not halt
> (c) Can't say whether it halts or not
You can add any number of extras, such as: (d) Wants orange juice. It
> Bryan wrote:
> > Peter Olcott wrote:
> >> > There are only three possibilities:
> >> > (a) Halting
> >> > (b) Not Halting
> >> > (c) Undecidable
> > (a) and (b) are mutually exclusive and jointly exhaustive.
>
> There are three possible choices not two:
> (a) It halts
> (b) It does not halt
> (c) Can't say whether it halts or not
doesn't change the fact that (a) and (b) are mutually exclusive and
jointly exhaustive.
> The Halt Decider that I provided [...]
You provided no halt decider. In this discipline, a decider is Turing
machine. We have to show that a TM can perform the steps, not merely
imagine and proclaim it.
-Bryan
Joshua Cranmer
Apr 19, 2012, 6:08:37 PM4/19/12
to
result of a function whose definition you are withholding from us by
either maliciousness or ignorance (I can't tell which).
Rick Decker
Apr 19, 2012, 11:02:51 PM4/19/12
to
a decidable problem. Exactly one of two deciders is clearly the right one:
1. One which answers "yes" without reading any input, or
2. One which answers "no", also without reading any input.
The fact that we don't know which one is correct has no bearing on
the decidability of the problem. The fact that there _is_ a decider
is all that we're concerned with. I know that this may strike some
people as an unsatisfactory answer, but you just have to live with
it. The definition of a decidable problem (or language, if you will)
is that there is _some_ algorithm that produces a correct answer to
the question. The fact that we might not know which one is correct
is by definition immaterial.
Regards,
Rick
Peter Olcott
Apr 19, 2012, 11:10:16 PM4/19/12
to
On 4/19/2012 3:51 PM, Bryan wrote:
> Peter Olcott wrote:
>> Bryan wrote:
>>> Peter Olcott wrote:
>>>>> There are only three possibilities:
>>>>> (a) Halting
>>>>> (b) Not Halting
>>>>> (c) Undecidable
>>> (a) and (b) are mutually exclusive and jointly exhaustive.
>> There are three possible choices not two:
>> (a) It halts
>> (b) It does not halt
>> (c) Can't say whether it halts or not
> You can add any number of extras, such as: (d) Wants orange juice. It
> doesn't change the fact that (a) and (b) are mutually exclusive and
> jointly exhaustive.
In terms of what the input TM actually does you are correct, it either
> Peter Olcott wrote:
>> Bryan wrote:
>>> Peter Olcott wrote:
>>>>> There are only three possibilities:
>>>>> (a) Halting
>>>>> (b) Not Halting
>>>>> (c) Undecidable
>>> (a) and (b) are mutually exclusive and jointly exhaustive.
>> There are three possible choices not two:
>> (a) It halts
>> (b) It does not halt
>> (c) Can't say whether it halts or not
> You can add any number of extras, such as: (d) Wants orange juice. It
> doesn't change the fact that (a) and (b) are mutually exclusive and
> jointly exhaustive.
halts or fails to halt. In terms of what a Halt Analyzer can report,
there are the three possibilities that I listed above.
Peter Olcott
Apr 19, 2012, 11:16:31 PM4/19/12
to
On 4/19/2012 5:08 PM, Joshua Cranmer wrote:
> On 4/19/2012 4:59 AM, Peter Olcott wrote:
>> On 4/19/2012 12:08 AM, Joshua Cranmer wrote:
>>> On 4/18/2012 9:09 PM, Peter Olcott wrote:
>>>> On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
>>>>> I see one of two possible definitions in the first post:
>>>>> 1. Does not halt.
>>>>> 2. An input is decidable (i.e., a circular definition).
>>>>>
>>>> Actually both of these are incorrect.
>>>
>>> Then your first post is wrong on more than one level...
>>>
>> No, you simply did not bother to pay enough attention:
>> The return value of halts == decidable
>
> I suppose there is a third interpretation, which is that it is the
> result of a function whose definition you are withholding from us by
> either maliciousness or ignorance (I can't tell which).
>
None of my four text books provide such a specification, they all
> On 4/19/2012 4:59 AM, Peter Olcott wrote:
>> On 4/19/2012 12:08 AM, Joshua Cranmer wrote:
>>> On 4/18/2012 9:09 PM, Peter Olcott wrote:
>>>> On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
>>>>> I see one of two possible definitions in the first post:
>>>>> 1. Does not halt.
>>>>> 2. An input is decidable (i.e., a circular definition).
>>>>>
>>>> Actually both of these are incorrect.
>>>
>>> Then your first post is wrong on more than one level...
>>>
>> No, you simply did not bother to pay enough attention:
>> The return value of halts == decidable
>
> I suppose there is a third interpretation, which is that it is the
> result of a function whose definition you are withholding from us by
> either maliciousness or ignorance (I can't tell which).
>
provide the same hypothetical frameworks that I am providing. I would
imagine that an actual Turing machine that even attempts to decide
whether another TM halts would be quote cumbersome to specify.
My patented screen analyzer has nearly 100,000 state transitions just to
recognize a single font instance from screen pixels.
Peter Olcott
Apr 19, 2012, 11:24:57 PM4/19/12
to
Bryan
Apr 19, 2012, 11:06:47 PM4/19/12
to
Peter Olcott wrote:
> Bryan wrote:
> > Peter Olcott wrote:
> Bryan wrote:
> > Peter Olcott wrote:
> >> Boolean Halts(String tm, String input)
> >> {
> >> if tm halts on input
> > How, at this point, could you think that's decidable?
>
> >> {
> >> if tm halts on input
> > How, at this point, could you think that's decidable?
>
> >> // tm is a valid TM and halting is decidable
> >> return true;
> >> else // anything else, such as not decidable,
> >> return false; // not a valid TM, not halting
> > Except that not halting can leave you running forever in attempt to
> >> else // anything else, such as not decidable,
> >> return false; // not a valid TM, not halting
> > evaluate the condition of the 'if'.
>
> >> }
>
> >> // DecidabilityDecider
> >> Boolean Decidable(String tm, String input)
> >> {
> >> if (Halts(tm, input))
> >> return true;
> >> else
> >> return false;
>
> >> }
> > Decidable() calls Halts(), so since Halts can fail to halt, so can
> >> {
> >> if (Halts(tm, input))
> >> return true;
> >> else
> >> return false;
>
> >> }
> > Decidable. In fact Decidable is equivalent to Halts.
>
> >> M( String Input )
> >> {
> >> if ( Decidable( Input, Input ) )
> >> Loop Forever;
> >> if ( Decidable( Input, Input ) )
> >> else
> >> Exit;
>
> >> }
> >> Decidable(M, M); // Correctly returns False.
> >> }
> >> Decidable(M, M); // Correctly returns False.
> > You've left undefined how you answer, "if tm halts on input". Until
> > you do so, there's not telling whether Decidable(M, M) returns or runs
> > forever.
>
> I don't see how you could say this.
> > you do so, there's not telling whether Decidable(M, M) returns or runs
> > forever.
>
> My function specifies that it either returns true or returns false,
> neither of these is a loop.
Your function has a step: "if tm halts on input"
You've left undefined how it evaluates that conditional.
> Do you assume that this function simulates
> its input? That would be a false assumption.
No, I decline to assume. How, in steps a TM can execute, do you
evaluate "if tm halts on input"?
-Bryan
Jussi Piitulainen
Apr 20, 2012, 1:30:52 AM4/20/12
to
of the halting problem that may not be decidable. And that apart from
these undecidable instances the halting problem is decidable, in the
sense _you_ have been using the word.
When a Turing machine is run an encoding of itself as a string, one of
Rick's two deciders tells whether it will halt. Do you now accept
this?
Peter Olcott
Apr 20, 2012, 6:15:53 AM4/20/12
to
hundreds of millions of state transitions?
Peter Olcott
Apr 20, 2012, 6:31:15 AM4/20/12
to
On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
// function prototype
Boolean Halts( String tm, String input );
This Halts() function is defined differently than it is defined in the
first post of this thread. In this case it must determine halts or *not*
halts.
If this is *not* an undecidable instance then what element of the set
{true, false} can the invocation of Halts(M, M) correctly return?
(1) It can not correctly return true indicating that the input TM halts
on its input. If it returns true indicating that the input TM will halt
on its input, the input TM loops making this return value incorrect.
(2) It can not correctly return false indicating that the input TM will
*not* halt on its input. If it returns false indicating that the input
TM will *not* halt on its input, the input TM halts making this return
value incorrect.
(3) This only leaves neither true nor false. I am calling this
undecidable. What else can it be called?
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
// function prototype
Boolean Halts( String tm, String input );
This Halts() function is defined differently than it is defined in the
first post of this thread. In this case it must determine halts or *not*
halts.
If this is *not* an undecidable instance then what element of the set
{true, false} can the invocation of Halts(M, M) correctly return?
(1) It can not correctly return true indicating that the input TM halts
on its input. If it returns true indicating that the input TM will halt
on its input, the input TM loops making this return value incorrect.
(2) It can not correctly return false indicating that the input TM will
*not* halt on its input. If it returns false indicating that the input
TM will *not* halt on its input, the input TM halts making this return
value incorrect.
(3) This only leaves neither true nor false. I am calling this
undecidable. What else can it be called?
> When a Turing machine is run an encoding of itself as a string, one of
> Rick's two deciders tells whether it will halt. Do you now accept
> this?
No for the reasons stated above.
> Rick's two deciders tells whether it will halt. Do you now accept
> this?
Jussi Piitulainen
Apr 20, 2012, 7:33:02 AM4/20/12
to
Peter Olcott writes:
> On 4/19/2012 10:06 PM, Bryan wrote:
> > Your function has a step: "if tm halts on input" You've left
> > undefined how it evaluates that conditional.
>
> Wouldn't specifying this such that it works for any arbitrary TM
> take hundreds of millions of state transitions?
Good question. You are the one who thinks it can be done, more or
> On 4/19/2012 10:06 PM, Bryan wrote:
> > Your function has a step: "if tm halts on input" You've left
> > undefined how it evaluates that conditional.
>
> Wouldn't specifying this such that it works for any arbitrary TM
> take hundreds of millions of state transitions?
less, and _you_ have nothing specific to say about the way to do it or
about your reasons to think so.
Bryan thinks it cannot be done at all.
You are allowed to use high-level pseudocode, by the way. People will
know how to compile to lower-level constructs and even to a Turing
machine. The problem it that your function has a step that is not
known to be implementable (is, indeed, known to not be implementable).
Jussi Piitulainen
Apr 20, 2012, 8:22:08 AM4/20/12
to
Peter Olcott writes:
> On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
> On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
> > Peter Olcott writes:
> >> On 4/19/2012 10:02 PM, Rick Decker wrote:
> >>> <sigh> Just for fun, I'll weigh in on this. This is most
> >>> emphatically a decidable problem. Exactly one of two deciders is
> >>> clearly the right one:
> >>>
> >>> 1. One which answers "yes" without reading any input, or
> >>> 2. One which answers "no", also without reading any input.
> >>>
> >>> The fact that we don't know which one is correct has no bearing
> >>> on the decidability of the problem. The fact that there _is_ a
> >>> decider is all that we're concerned with. I know that this may
> >>> strike some people as an unsatisfactory answer, but you just
> >>> have to live with it. The definition of a decidable problem (or
> >>> language, if you will) is that there is _some_ algorithm that
> >>> produces a correct answer to the question. The fact that we
> >>> might not know which one is correct is by definition immaterial.
> >>>
> >>> Regards,
> >>>
> >>> Rick
> >>
> >> That reasoning seems correct to me.
> >
> > Yet you will continue to insist that there are _individual
> > instances_ of the halting problem that may not be decidable. And
> > that apart from these undecidable instances the halting problem is
> > decidable, in the sense _you_ have been using the word.
[description snipped]
> >> On 4/19/2012 10:02 PM, Rick Decker wrote:
> >>> <sigh> Just for fun, I'll weigh in on this. This is most
> >>> emphatically a decidable problem. Exactly one of two deciders is
> >>> clearly the right one:
> >>>
> >>> 1. One which answers "yes" without reading any input, or
> >>> 2. One which answers "no", also without reading any input.
> >>>
> >>> The fact that we don't know which one is correct has no bearing
> >>> on the decidability of the problem. The fact that there _is_ a
> >>> decider is all that we're concerned with. I know that this may
> >>> strike some people as an unsatisfactory answer, but you just
> >>> have to live with it. The definition of a decidable problem (or
> >>> language, if you will) is that there is _some_ algorithm that
> >>> produces a correct answer to the question. The fact that we
> >>> might not know which one is correct is by definition immaterial.
> >>>
> >>> Regards,
> >>>
> >>> Rick
> >>
> >> That reasoning seems correct to me.
> >
> > Yet you will continue to insist that there are _individual
> > instances_ of the halting problem that may not be decidable. And
> > that apart from these undecidable instances the halting problem is
> > decidable, in the sense _you_ have been using the word.
> If this is *not* an undecidable instance then what element of the
> set {true, false} can the invocation of Halts(M, M) correctly
> return?
> (3) This only leaves neither true nor false. I am calling this
> undecidable. What else can it be called?
confusing, frustrating, paradoxical, particular, mysterious,
classified, funny, unanswerable, inadmissible, illegal, possibly with
the prefix Halts- for the machine that cannot give the correct answer.
You need not be stuck with the one word that already has a very
different meaning in the context where you want to discuss your ideas.
People keep telling you it has. There are words to choose from.
Yes, no, maybe. True, false, sorry. Halts, halts not, mu.
The question remains, is the third answer interesting. And is the
three-valued thing implementable.
> > When a Turing machine is run an encoding of itself as a string,
> > one of Rick's two deciders tells whether it will halt. Do you now
> > accept this?
>
> No for the reasons stated above.
Patricia Shanahan
Apr 20, 2012, 10:47:18 AM4/20/12
to
On 4/20/2012 5:22 AM, Jussi Piitulainen wrote:
...
Three value halting decider-substitutes that return {true, false, mu}
are definitely implementable with "true" meaning that the input
definitely describes a TM computation that halts, "false" meaning that
the input definitely does not describe a TM computation that halts, and
"mu" all other cases.
Trivially, consider a TM that unconditionally returns "mu" for all
inputs. It meets the conditions I described above, though it is not very
useful. The usefulness of such a decider-substitute increases as the
density of "mu" results decreases.
PO has previously rejected this approach.
Patricia
...
> The question remains, is the third answer interesting. And is the
> three-valued thing implementable.
...
> three-valued thing implementable.
Three value halting decider-substitutes that return {true, false, mu}
are definitely implementable with "true" meaning that the input
definitely describes a TM computation that halts, "false" meaning that
the input definitely does not describe a TM computation that halts, and
"mu" all other cases.
Trivially, consider a TM that unconditionally returns "mu" for all
inputs. It meets the conditions I described above, though it is not very
useful. The usefulness of such a decider-substitute increases as the
density of "mu" results decreases.
PO has previously rejected this approach.
Patricia
Rick Decker
Apr 20, 2012, 11:34:53 AM4/20/12
to
decider. That means that the action of Halts is defined as:
For _any_ input (<tm>, s) where <tm> is a valid encoding of a TM
and s is a string,
1. Halts(<tm>, s) will eventually halt
2. Halts(<tm>, s) will answer "true" if tm will halt on input s.
3. Halts(<tm>, s) will answer "false" if tm will not halt on input s.
4. Halts(<tm>, s) will always eventually halt and will only give
"true" or "false" as its result.
That is the conventional description of what a halting decider must do.
Do you agree with this definition? If so, we can continue, if not, then
we're talking about different things.
>
> If this is *not* an undecidable instance then what element of the set
> {true, false} can the invocation of Halts(M, M) correctly return?
I don't understand what you mean by "an undecidable instance" so
> If this is *not* an undecidable instance then what element of the set
> {true, false} can the invocation of Halts(M, M) correctly return?
I'll assume the question is "what could be the answer returned by
Halts(M, M)?"
>
> (1) It can not correctly return true indicating that the input TM halts
> on its input. If it returns true indicating that the input TM will halt
> on its input, the input TM loops making this return value incorrect.
>
> (2) It can not correctly return false indicating that the input TM will
> *not* halt on its input. If it returns false indicating that the input
> TM will *not* halt on its input, the input TM halts making this return
> value incorrect.
Good. You're within epsilon of the conclusion. The conclusion is:
> (1) It can not correctly return true indicating that the input TM halts
> on its input. If it returns true indicating that the input TM will halt
> on its input, the input TM loops making this return value incorrect.
>
> (2) It can not correctly return false indicating that the input TM will
> *not* halt on its input. If it returns false indicating that the input
> TM will *not* halt on its input, the input TM halts making this return
> value incorrect.
(1) It cannot correctly answer "true".
(2) It cannot correctly answer "false".
The last step is to realize that our initial assumption, that Halts()
is a decider, was incorrect. In other words, there cannot be a
decider Halts() that will act as specified. Consequently, the
halting problem cannot be decidable.
>
> (3) This only leaves neither true nor false. I am calling this
> undecidable. What else can it be called?
Perfect. If I interpret your (3) correctly, you've just concluded
> (3) This only leaves neither true nor false. I am calling this
> undecidable. What else can it be called?
exactly what you should have, that the halting problem is undecidable,
since for _any_putative Halts() decider, there will be an
input pair on which it won't work as specified.
Now, if I understand your argument correctly, you're hoping to
modify the problem slightly by making a decider that will
work correctly on any but these pathological instances, like your
M. What you seem to be proposing is that there is some way
of recognizing those tms which cause this problem and not
consider them as acceptable inputs. Unfortunately, we can
prove that this is also an undecidable problem, which would
leave us no closer to decidability than we were at the start.
Regards,
Rick
Jussi Piitulainen
Apr 20, 2012, 11:47:08 AM4/20/12
to
interesting. The third value from an overly trivial analyzer is not.
> PO has previously rejected this approach.
in the case where the machine and its input being analyzed are defined
in terms of a halt analyzer in such a way that the analyzer cannot
return a correct value (hope I got the twist right). This would make
the three-valued analyzer very interesting but I suspect questions of
implementability (even in principle) remain. PO has not addressed such
questions.
Joshua Cranmer
Apr 20, 2012, 12:42:06 PM4/20/12
to
On 4/19/2012 10:16 PM, Peter Olcott wrote:
> None of my four text books provide such a specification, they all
> provide the same hypothetical frameworks that I am providing. I would
> imagine that an actual Turing machine that even attempts to decide
> whether another TM halts would be quote cumbersome to specify.
You miss the point of the hypothetical framework, then. They are
> None of my four text books provide such a specification, they all
> provide the same hypothetical frameworks that I am providing. I would
> imagine that an actual Turing machine that even attempts to decide
> whether another TM halts would be quote cumbersome to specify.
establishing the *nonexistence* of such a machine by showing that if one
did exist, then it would lead to a contradiction. The specification is
omitted because it can't exist.
Also note that it is conventional to describe most Turing machines in a
simplified imperative language style because it is rather trivial to
show that the imperative language can be implemented by a Turing
machine. The basic highlights of such a proof: N-tape Turing machines
are equivalent to 1-tape machines, all basic arithmetic operations are
possible on Turing machines, Turing machines are composable, showing
mappings from loops and conditionals to Turing machines. We can even go
so far as to say "Simulate M on w <for N steps>" because the existence
of a UTM has been established.
Patricia Shanahan
Apr 20, 2012, 12:47:00 PM4/20/12
to
On 4/20/2012 8:47 AM, Jussi Piitulainen wrote:
> Patricia Shanahan writes:
>> On 4/20/2012 5:22 AM, Jussi Piitulainen wrote:
>> ...
>>> The question remains, is the third answer interesting. And is the
>>> three-valued thing implementable.
>> ...
>>
>> Three value halting decider-substitutes that return {true, false, mu}
>> are definitely implementable with "true" meaning that the input
>> definitely describes a TM computation that halts, "false" meaning that
>> the input definitely does not describe a TM computation that halts, and
>> "mu" all other cases.
>>
>> Trivially, consider a TM that unconditionally returns "mu" for all
>> inputs. It meets the conditions I described above, though it is not very
>> useful. The usefulness of such a decider-substitute increases as the
>> density of "mu" results decreases.
>
> Yes. That's why I said the question remains whether the third value is
> interesting. The third value from an overly trivial analyzer is not.
In reality, limiting the "mu" cases for various undecidable static
> Patricia Shanahan writes:
>> On 4/20/2012 5:22 AM, Jussi Piitulainen wrote:
>> ...
>>> The question remains, is the third answer interesting. And is the
>>> three-valued thing implementable.
>> ...
>>
>> Three value halting decider-substitutes that return {true, false, mu}
>> are definitely implementable with "true" meaning that the input
>> definitely describes a TM computation that halts, "false" meaning that
>> the input definitely does not describe a TM computation that halts, and
>> "mu" all other cases.
>>
>> Trivially, consider a TM that unconditionally returns "mu" for all
>> inputs. It meets the conditions I described above, though it is not very
>> useful. The usefulness of such a decider-substitute increases as the
>> density of "mu" results decreases.
>
> Yes. That's why I said the question remains whether the third value is
> interesting. The third value from an overly trivial analyzer is not.
analysis questions is an important research area. For example, some of
the most promising approaches to deadlock recovery involve a combination
of static analysis and run-time checks. The better the static analysis,
the less time and memory needs to be spent on run-time checking.
>
>> PO has previously rejected this approach.
>
> I suspect he's now thinking that the third value would be used _only_
> in the case where the machine and its input being analyzed are defined
> in terms of a halt analyzer in such a way that the analyzer cannot
> return a correct value (hope I got the twist right). This would make
> the three-valued analyzer very interesting but I suspect questions of
> implementability (even in principle) remain. PO has not addressed such
> questions.
computable is computable. That means he expects his use of a function in
his pseudo-code to be accepted as proof of its computability.
Patricia
Joshua Cranmer
Apr 20, 2012, 1:19:44 PM4/20/12
to
On 4/20/2012 11:47 AM, Patricia Shanahan wrote:
> In reality, limiting the "mu" cases for various undecidable static
> analysis questions is an important research area. For example, some of
> the most promising approaches to deadlock recovery involve a combination
> of static analysis and run-time checks. The better the static analysis,
> the less time and memory needs to be spent on run-time checking.
Static analysis: where all the interesting problems are undecidable, and
> In reality, limiting the "mu" cases for various undecidable static
> analysis questions is an important research area. For example, some of
> the most promising approaches to deadlock recovery involve a combination
> of static analysis and run-time checks. The better the static analysis,
> the less time and memory needs to be spent on run-time checking.
we still try to solve them anyways :-) .
> And he won't. He deeply believes that any function he wants to be
> computable is computable. That means he expects his use of a function in
> his pseudo-code to be accepted as proof of its computability.
unless proven to be uncomputable", since I have seen hints that he
believes that the standard, unmodified Halting problem is truly
undecidable. It's also possible that talk of the Church-Turing thesis
has garbled his reasoning, since we discuss it as being "true" even
though it's not "proven" true or false, whence his belief that his
theorems are true unless they can be shown to be false.
Maybe I should start sprinkling my posts with reference to the notion of
superposition instead, since theorems are a mixture of true and false
until they are observed specifically to be true or false. :-)
Peter Olcott
Apr 20, 2012, 1:27:36 PM4/20/12
to
possible counter-example that I can imagine showing that it can't be
done fails.
When a potential Halt Decider attempts to decide whether or not another
TM halts on its input, it only has three choices:
a) Halt in its accept state indicating that the input TM will halt on
its input.
b) Halt in its reject state indicating that the input TM will *not* halt
on its input.
c) Loop
In those cases where neither of its halt states would provide the
correct answer, it could not correctly decide between halting and *not*
halting, so it seemed reasonable to call this instance undecidable
because it can't decide.
To make the above problem decidable for a large class of Halting
Problems instances, one only has to change the question:
Can you tell me that the input TM halts on its input?
(a) Yes I can tell you that it does halt.
(b) No I can't tell you that it halts.
(either does not halt or I can't tell you).
Peter Olcott
Apr 20, 2012, 1:29:44 PM4/20/12
to
What is the conventional terminology for the case where a TM can not
decide an instance?
Peter Olcott
Apr 20, 2012, 1:32:53 PM4/20/12
to
snipped, there is no other correct answer that I can provide.
Peter Olcott
Apr 20, 2012, 1:35:27 PM4/20/12
to
What is the value of X?
Peter Olcott
Apr 20, 2012, 1:49:48 PM4/20/12
to
because of Pathological Self-Reference every possible return value from
the complete set of all possible return values: {true, false} is incorrect.
So basically if we can throw out incorrect input along with incorrectly
specified Turing Machines, then we are good, otherwise the definition of
the problem is insufficiently (thus erroneously) specified.
>>
>> If this is *not* an undecidable instance then what element of the set
>> {true, false} can the invocation of Halts(M, M) correctly return?
>
> I don't understand what you mean by "an undecidable instance" so
> I'll assume the question is "what could be the answer returned by
> Halts(M, M)?"
>>
>> (1) It can not correctly return true indicating that the input TM halts
>> on its input. If it returns true indicating that the input TM will halt
>> on its input, the input TM loops making this return value incorrect.
>>
>> (2) It can not correctly return false indicating that the input TM will
>> *not* halt on its input. If it returns false indicating that the input
>> TM will *not* halt on its input, the input TM halts making this return
>> value incorrect.
>
> Good. You're within epsilon of the conclusion. The conclusion is:
> (1) It cannot correctly answer "true".
> (2) It cannot correctly answer "false".
>
> The last step is to realize that our initial assumption, that Halts()
> is a decider, was incorrect.
> In other words, there cannot be a
> decider Halts() that will act as specified. Consequently, the
> halting problem cannot be decidable.
a correct answer to an incorrect question.
>>
>> (3) This only leaves neither true nor false. I am calling this
>> undecidable. What else can it be called?
>
> Perfect. If I interpret your (3) correctly, you've just concluded
> exactly what you should have, that the halting problem is undecidable,
> since for _any_putative Halts() decider, there will be an
> input pair on which it won't work as specified.
>
> Now, if I understand your argument correctly, you're hoping to
> modify the problem slightly by making a decider that will
> work correctly on any but these pathological instances, like your
> M. What you seem to be proposing is that there is some way
> of recognizing those tms which cause this problem and not
> consider them as acceptable inputs. Unfortunately, we can
> prove that this is also an undecidable problem, which would
> leave us no closer to decidability than we were at the start.
>
>
> Regards,
>
> Rick
counter-example, and I will show the error.
Peter Olcott
Apr 20, 2012, 1:56:58 PM4/20/12
to
conventional) term that can be used to describe single instance
undecidability. In other words the case where neither true nor false is
the correct return value from a potential halt decider when attempting
to decide whether or not an input TM will halt on its input.
Peter Olcott
Apr 20, 2012, 2:01:05 PM4/20/12
to
specification were completely unreasonable requests.
Joshua Cranmer
Apr 20, 2012, 2:11:40 PM4/20/12
to
existence. In such a case, it is not only reasonable but expected that
you be able to provide the specification.
Leif Roar Moldskred
Apr 20, 2012, 2:26:30 PM4/20/12
to
In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:
>
> So when it can not decide an instance this can not be called undecidable?
> What is the conventional terminology for the case where a TM can not
> decide an instance?
"Proof that this TM is not a halting decider."
>
> So when it can not decide an instance this can not be called undecidable?
> What is the conventional terminology for the case where a TM can not
> decide an instance?
--
Leif Roar Moldskred
Jussi Piitulainen
Apr 20, 2012, 2:34:42 PM4/20/12
to
them is the correct answer (the question being whether the machine
halts on the input) and one of those two trivial machines does give
that correct answer.
There is no string that encodes a Turing machine that answers every
such question correctly, so such a string is never a part of the input
to these trivial machines. The proof that you have seen starts by
assuming that there is such a machine and proceeds to a contradiction.
Patricia Shanahan
Apr 20, 2012, 3:47:48 PM4/20/12
to
decider."
The key point is that what PO has been calling "undecidability" is not a
property of the input - every TM computation either halts or does not
halt, and the correct {true, false} answer is provided by many TMs. It
is a property of a particular TM when run with that input.
Patricia
Patricia Shanahan
Apr 20, 2012, 3:52:47 PM4/20/12
to
On 4/20/2012 11:11 AM, Joshua Cranmer wrote:
...
and "there exists" quantification.
Proof of a statement of the form "For every TM M, P(M) is true." should
not make any assumptions about the implementation of M, and does not
depend on the existence of any instance M. You can start by assuming
there is a TM M, and deducing P(M) from that.
That is entirely different from proving a statement of the form "There
exists a TM such that P(M) is true".
Patricia
...
> You're assuming that it exists and writing proofs that rely on its
> existence. In such a case, it is not only reasonable but expected that
> you be able to provide the specification.
>
Another way of looking at it is as the difference between "for every"
> existence. In such a case, it is not only reasonable but expected that
> you be able to provide the specification.
>
and "there exists" quantification.
Proof of a statement of the form "For every TM M, P(M) is true." should
not make any assumptions about the implementation of M, and does not
depend on the existence of any instance M. You can start by assuming
there is a TM M, and deducing P(M) from that.
That is entirely different from proving a statement of the form "There
exists a TM such that P(M) is true".
Patricia
Peter Olcott
Apr 20, 2012, 3:54:20 PM4/20/12
to
proving that it is false only requires a single valid counter-example.
Peter Olcott
Apr 20, 2012, 4:05:18 PM4/20/12
to
On 4/20/2012 1:34 PM, Jussi Piitulainen wrote:
> Peter Olcott writes:
>> On 4/20/2012 7:22 AM, Jussi Piitulainen wrote:
>>> Peter Olcott writes:
>>>> On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
>>>>> When a Turing machine is run an encoding of itself as a string,
>>>>> one of Rick's two deciders tells whether it will halt. Do you
>>>>> now accept this?
>>>> No for the reasons stated above.
>>> I knew you would.
>> 1. One which answers "yes" without reading any input, or
>> 2. One which answers "no", also without reading any input.
>>
>> Since both yes and no are wrong answers to the question that you
>> snipped, there is no other correct answer that I can provide.
> For any string that encodes a Turing machine and its input, one of
> them is the correct answer (the question being whether the machine
> halts on the input) and one of those two trivial machines does give
> that correct answer.
That is the wrong question.
> Peter Olcott writes:
>> On 4/20/2012 7:22 AM, Jussi Piitulainen wrote:
>>> Peter Olcott writes:
>>>> On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
>>>>> When a Turing machine is run an encoding of itself as a string,
>>>>> one of Rick's two deciders tells whether it will halt. Do you
>>>>> now accept this?
>>>> No for the reasons stated above.
>>> I knew you would.
>> 1. One which answers "yes" without reading any input, or
>> 2. One which answers "no", also without reading any input.
>>
>> Since both yes and no are wrong answers to the question that you
>> snipped, there is no other correct answer that I can provide.
> For any string that encodes a Turing machine and its input, one of
> them is the correct answer (the question being whether the machine
> halts on the input) and one of those two trivial machines does give
> that correct answer.
The question is not whether or not the input TM halts on its input.
I have pointed this out more than a hundred times and everyone's brain
seems to be hardwired to avoid seeing this:
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
(a) Halts(M, M) provide?
This IS NOT THE SAME QUESTION AS:
(b) Does M halt on its input M?
Question (a) is erroneous because of Patholgical Self-Reference, and
Question (b) is well-formed when it is posed without Pathological
Self-Reference.
Peter Olcott
Apr 20, 2012, 4:17:28 PM4/20/12
to
The input/TM combination results in a question that has no possible
correct answer from exhaustively complete set of all possible
answers:{true, false}.
It is self-evident (completely proven true entirely on the basis of the
meaning of the words in the sentence) that any question that lacks a
correct answer from the exhaustively complete set of all possible
answers must be ill-formed.
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
What correct return value from the set of {true, false} can the
invocation of Halts(M, M) provide?
exactly meets the above specified self-evident definition of ill-formed
question.
I see no way that anyone possibly argue against this that does not have
their brain hard-wired in refute mode.
Bryan
Apr 20, 2012, 4:20:52 PM4/20/12
to
Jussi Piitulainen wrote:
> Peter Olcott writes:
> Peter Olcott writes:
> > Bryan wrote:
> > > Your function has a step: "if tm halts on input" You've left
> > > undefined how it evaluates that conditional.
>
> > Wouldn't specifying this such that it works for any arbitrary TM
> > take hundreds of millions of state transitions?
>
> Good question. You are the one who thinks it can be done, more or
> less, and _you_ have nothing specific to say about the way to do it or
> about your reasons to think so.
>
> Bryan thinks it cannot be done at all.
As written in the opening post, "if tm halts on input", it cannot be
> > > Your function has a step: "if tm halts on input" You've left
> > > undefined how it evaluates that conditional.
>
> > Wouldn't specifying this such that it works for any arbitrary TM
> > take hundreds of millions of state transitions?
>
> Good question. You are the one who thinks it can be done, more or
> less, and _you_ have nothing specific to say about the way to do it or
> about your reasons to think so.
>
> Bryan thinks it cannot be done at all.
done by a TM. Next Peter said that it's allowed to *not* resolve the
conditional and return "cannot decide". In that case it is easily
implementable: ignore the input and return "cannot decide". Works ever
time.
-Bryan
Ralph Hartley
Apr 20, 2012, 4:22:17 PM4/20/12
to
On 04/20/2012 01:27 PM, Peter Olcott wrote:
> To make the above problem decidable for a large class of Halting
> Problems instances, one only has to change the question:
> Can you tell me that the input TM halts on its input?
> (a) Yes I can tell you that it does halt.
> (b) No I can't tell you that it halts.
> (either does not halt or I can't tell you).
So a TM that returns "no" for all inputs is a halting decider by your
> To make the above problem decidable for a large class of Halting
> Problems instances, one only has to change the question:
> Can you tell me that the input TM halts on its input?
> (a) Yes I can tell you that it does halt.
> (b) No I can't tell you that it halts.
> (either does not halt or I can't tell you).
definition?
It meets that specification, since it can never tell you that any TM
halts, and it always correctly answers "no".
Ralph Hartley
Leif Roar Moldskred
Apr 20, 2012, 4:25:35 PM4/20/12
to
In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:
>
> The input/TM combination results in a question that has no possible
> correct answer from exhaustively complete set of all possible
> answers:{true, false}.
Nonsense, and obvious nonsense at that. A particular TM running on a
>
> The input/TM combination results in a question that has no possible
> correct answer from exhaustively complete set of all possible
> answers:{true, false}.
particular input either halts or it does not halt.
--
Leif Roar Moldskred
Peter Olcott
Apr 20, 2012, 4:35:45 PM4/20/12
to
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
What correct return value from the set of {true, false} can the
invocation of Halts(M, M) provide?
(a) true.
invocation of Halts(M, M) provide?
(b) false.
(c) neither. The input/TM combination results in a question that has no
Leif Roar Moldskred
Apr 20, 2012, 5:29:13 PM4/20/12
to
In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:
>
> Of course you dishonestly remove the context that proves you are wrong.
When you run a given Turing Machine on a given input, the machine will
>
> Of course you dishonestly remove the context that proves you are wrong.
either halt or it will run forever. That's _regardless_ of context.
>
> M( String Input )
> {
> if ( Halts( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> What correct return value from the set of {true, false} can the
> invocation of Halts(M, M) provide?
Turing Machine.
--
Leif Roar Moldskred
Peter Olcott
Apr 20, 2012, 6:37:04 PM4/20/12
to
Did you get the wrong answer because:
(a) There was something wrong with the question.
(b) You are not very good at answering questions.
Which is it (a) or (b) ???
Joshua Cranmer
Apr 20, 2012, 7:17:22 PM4/20/12
to
On 4/20/2012 3:35 PM, Peter Olcott wrote:
> What correct return value from the set of {true, false} can the
> invocation of Halts(M, M) provide?
> (a) true.
> (b) false.
> (c) neither. The input/TM combination results in a question that has no
> possible correct answer from exhaustively complete set of all possible
> answers:{true, false}.
Not being able to provide a correct answer does not imply that there is
> What correct return value from the set of {true, false} can the
> invocation of Halts(M, M) provide?
> (a) true.
> (b) false.
> (c) neither. The input/TM combination results in a question that has no
> possible correct answer from exhaustively complete set of all possible
> answers:{true, false}.
no correct answer. For example, no DFA can correctly decide the language
{0^n 1^n}, but that doesn't mean that it can't be correctly decided.
Joshua Cranmer
Apr 20, 2012, 7:18:42 PM4/20/12
to
On 4/20/2012 3:05 PM, Peter Olcott wrote:
> The question is what correct return value can the invocation of a
> (a) Halts(M, M) provide?
>
> This IS NOT THE SAME QUESTION AS:
> (b) Does M halt on its input M?
>
> Question (a) is erroneous because of Patholgical Self-Reference, and
> Question (b) is well-formed when it is posed without Pathological
> Self-Reference.
The problem is that (a) is not a particularly useful question while (b) is.
> The question is what correct return value can the invocation of a
> (a) Halts(M, M) provide?
>
> This IS NOT THE SAME QUESTION AS:
> (b) Does M halt on its input M?
>
> Question (a) is erroneous because of Patholgical Self-Reference, and
> Question (b) is well-formed when it is posed without Pathological
> Self-Reference.
Peter Olcott
Apr 20, 2012, 7:32:49 PM4/20/12
to
On 4/20/2012 6:17 PM, Joshua Cranmer wrote:
> On 4/20/2012 3:35 PM, Peter Olcott wrote:
>> What correct return value from the set of {true, false} can the
>> invocation of Halts(M, M) provide?
>> (a) true.
>> (b) false.
>> (c) neither. The input/TM combination results in a question that has no
>> possible correct answer from exhaustively complete set of all possible
>> answers:{true, false}.
>
> Not being able to provide a correct answer does not imply that there
> is no correct answer.
In the case of Pathological Self-Reference: not being able to provide a
> On 4/20/2012 3:35 PM, Peter Olcott wrote:
>> What correct return value from the set of {true, false} can the
>> invocation of Halts(M, M) provide?
>> (a) true.
>> (b) false.
>> (c) neither. The input/TM combination results in a question that has no
>> possible correct answer from exhaustively complete set of all possible
>> answers:{true, false}.
>
> Not being able to provide a correct answer does not imply that there
> is no correct answer.
correct answer to one question does logically entail that there is no
possible correct answer to this question.
That there is no possible correct answer to the question involving
Pathological Self-Reference, does not imply that another different
question has no correct answer.
(a) What correct return value from the set of {true, false} can the
invocation of Halts(M, M) provide?
(b) Does M halt on input M?
(a) and (b) are two entirely different questions, the first one is
impossible to correctly answer and the second one is *not* impossible to
correctly answer.
Joshua Cranmer
Apr 20, 2012, 7:35:26 PM4/20/12
to
exist an x", it is possible to prove them true without needing
omniscience. Take, for example, the pumping lemma for regular languages.
It states that "for all regular languages, there exists a length p such
that, for all strings greater than p, there exists a decomposition s =
xyz such that <several conditions>." It's used manually in the negative
(i.e., for a language L, ApEsAx,y,z not phi). In these kinds of proofs
there are not one but two cases that require you to reason about any
possible input. By your argument, that ought to be effectively
impossible. Yet the pumping lemma is a powerful lemma that is used
heavily: any student in an introductory computability theory would be
expected to use it at least twice over the course of exams. It's usable
because you can often find structure that allows you to make sweeping
statements using only a few cases.
But in the cases where you can't prove it true and you can't prove it
false, you must be agnostic about its truth. You can make claims like
"if X is true, then Y holds", but you can't say "Y holds (since X)".
Perhaps one famous case is that there is an algorithm for testing
primality which is polynomial if the Riemann hypothesis is true, but
since RH is an unsolved problem as of late, it wasn't held to be a proof
that primality testing is polynomial (it took the AKS test to
conclusively hold it).
Peter Olcott
Apr 20, 2012, 7:36:01 PM4/20/12
to
On 4/20/2012 6:18 PM, Joshua Cranmer wrote:
> On 4/20/2012 3:05 PM, Peter Olcott wrote:
>> The question is what correct return value can the invocation of a
>> (a) Halts(M, M) provide?
>>
>> This IS NOT THE SAME QUESTION AS:
>> (b) Does M halt on its input M?
>>
>> Question (a) is erroneous because of Patholgical Self-Reference, and
>> Question (b) is well-formed when it is posed without Pathological
>> Self-Reference.
>
> The problem is that (a) is not a particularly useful question while
> (b) is.
>
The Problem with the Halting Problem is that is entirely based on the
> On 4/20/2012 3:05 PM, Peter Olcott wrote:
>> The question is what correct return value can the invocation of a
>> (a) Halts(M, M) provide?
>>
>> This IS NOT THE SAME QUESTION AS:
>> (b) Does M halt on its input M?
>>
>> Question (a) is erroneous because of Patholgical Self-Reference, and
>> Question (b) is well-formed when it is posed without Pathological
>> Self-Reference.
>
> The problem is that (a) is not a particularly useful question while
> (b) is.
>
ill-formed question shown in (a), thus making the Halting Problem itself
nothing more than an error of reasoning.
George Greene
Apr 21, 2012, 12:35:48 AM4/21/12
to
On Apr 19, 11:02 pm, Rick Decker <rdec...@hamilton.edu> wrote:
> 1. One which answers "yes" without reading any input, or
> 2. One which answers "no", also without reading any input.
>
> 1. One which answers "yes" without reading any input, or
> 2. One which answers "no", also without reading any input.
>
> The fact that we don't know which one is correct has no bearing on
> the decidability of the problem. The fact that there _is_ a decider
> is all that we're concerned with.
The point is that this entails that ALL FINITE questions (and
> the decidability of the problem. The fact that there _is_ a decider
> is all that we're concerned with.
therefore all individual questions)
ARE ALWAYS decidable. P.O. is so confused that he not only talks
about individual
quetsions being decidable, he even talks about an individual TM being
decidable, or an
individual input to a TM being decidable.
The kinds of things that CAN actually be decidable (or un) ARE
INFINITE families of (similar) questions.
Nobody but me has been willing to say this properly and much time has
been wasted as a result.
Far too many people have spent far too many weeks ALLOWING P.O. to use
"undecidable" INCORRECTLY.
That goes triple for his continuing to talk about a TM named
"Halts(,)". Even after he has conceded
that no such thing exists, the fact that he is still CALLING it that
still breeds confusion.
George Greene
Apr 21, 2012, 12:42:41 AM4/21/12
to
On Apr 20, 1:27 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> When a potential Halt Decider
So are you NOW FINALLY going to CALL it "PotentialHaltDecider"
INSTEAD OF "Halts(,)" ??? TO WHOM and what do we owe this
majestic evolution???????????????????????????????
> attempts to decide whether or not another
> TM halts on its input, it only has three choices:
> a) Halt in its accept state indicating that the input TM will halt on
> its input.
> b) Halt in its reject state indicating that the input TM will *not* halt
> on its input.
> c) Loop
or rather, fail to halt (the failure may not be true looping but
that''s the usual shorthand).
Congratulations.
You finally understand.
I don't know which TEACHER to congratulate (probably Darryl, but he
had to
wait a month for other people to soften you up) but at least this
Proves It Can Be Done!
> When a potential Halt Decider
So are you NOW FINALLY going to CALL it "PotentialHaltDecider"
INSTEAD OF "Halts(,)" ??? TO WHOM and what do we owe this
majestic evolution???????????????????????????????
> attempts to decide whether or not another
> TM halts on its input, it only has three choices:
> a) Halt in its accept state indicating that the input TM will halt on
> its input.
> b) Halt in its reject state indicating that the input TM will *not* halt
> on its input.
> c) Loop
or rather, fail to halt (the failure may not be true looping but
that''s the usual shorthand).
Congratulations.
You finally understand.
I don't know which TEACHER to congratulate (probably Darryl, but he
had to
wait a month for other people to soften you up) but at least this
Proves It Can Be Done!
Patricia Shanahan
Apr 21, 2012, 2:36:11 AM4/21/12
to
On 4/20/2012 9:35 PM, George Greene wrote:
> On Apr 19, 11:02 pm, Rick Decker<rdec...@hamilton.edu> wrote:
>> 1. One which answers "yes" without reading any input, or
>> 2. One which answers "no", also without reading any input.
>>
>> The fact that we don't know which one is correct has no bearing on
>> the decidability of the problem. The fact that there _is_ a decider
>> is all that we're concerned with.
>
> The point is that this entails that ALL FINITE questions (and
> therefore all individual questions)
> ARE ALWAYS decidable. P.O. is so confused that he not only talks
> about individual
> quetsions being decidable, he even talks about an individual TM being
> decidable, or an
> individual input to a TM being decidable.
>
> The kinds of things that CAN actually be decidable (or un) ARE
> INFINITE families of (similar) questions.
You got this right in the first paragraph, but wrong immediately above.
> On Apr 19, 11:02 pm, Rick Decker<rdec...@hamilton.edu> wrote:
>> 1. One which answers "yes" without reading any input, or
>> 2. One which answers "no", also without reading any input.
>>
>> The fact that we don't know which one is correct has no bearing on
>> the decidability of the problem. The fact that there _is_ a decider
>> is all that we're concerned with.
>
> The point is that this entails that ALL FINITE questions (and
> therefore all individual questions)
> ARE ALWAYS decidable. P.O. is so confused that he not only talks
> about individual
> quetsions being decidable, he even talks about an individual TM being
> decidable, or an
> individual input to a TM being decidable.
>
> The kinds of things that CAN actually be decidable (or un) ARE
> INFINITE families of (similar) questions.
Every set of finite strings is either decidable or undecidable. Of
course, if the set is finite we know which - it is decidable. All
undecidable sets are infinite.
Patricia
Ross A. Finlayson
Apr 21, 2012, 3:45:44 AM4/21/12
to
The constructible ones do.
And those are countable.
Peter Olcott
Apr 21, 2012, 8:23:06 AM4/21/12
to
On 4/20/2012 11:35 PM, George Greene wrote:
> On Apr 19, 11:02 pm, Rick Decker<rdec...@hamilton.edu> wrote:
>> 1. One which answers "yes" without reading any input, or
>> 2. One which answers "no", also without reading any input.
>>
>> The fact that we don't know which one is correct has no bearing on
>> the decidability of the problem. The fact that there _is_ a decider
>> is all that we're concerned with.
> The point is that this entails that ALL FINITE questions (and
> therefore all individual questions)
> ARE ALWAYS decidable.
That is a lie.
> On Apr 19, 11:02 pm, Rick Decker<rdec...@hamilton.edu> wrote:
>> 1. One which answers "yes" without reading any input, or
>> 2. One which answers "no", also without reading any input.
>>
>> The fact that we don't know which one is correct has no bearing on
>> the decidability of the problem. The fact that there _is_ a decider
>> is all that we're concerned with.
> The point is that this entails that ALL FINITE questions (and
> therefore all individual questions)
> ARE ALWAYS decidable.
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
Halts(M, M) could possibly provide?
Don't say that Halts() can not possibly exist that is a lie too.
Halts() could simply loop on the above input, and thus exist.
Peter Olcott
Apr 21, 2012, 8:29:04 AM4/21/12
to
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
What is the correct {true, false} return value that the invocation of
Halts(M, M) could possibly provide?
(a) true
(b) false
If you can not correctly decide between true and false, then this
individual case is *not* decidable, even if everyone in the universe
says otherwise, and even if it is defined as decidable within the field
of the Theory of Computation.
Patricia Shanahan
Apr 21, 2012, 9:49:36 AM4/21/12
to
On 4/21/2012 5:29 AM, Peter Olcott wrote:
> On 4/21/2012 1:36 AM, Patricia Shanahan wrote:
>> On 4/20/2012 9:35 PM, George Greene wrote:
>>> On Apr 19, 11:02 pm, Rick Decker<rdec...@hamilton.edu> wrote:
>>>> 1. One which answers "yes" without reading any input, or
>>>> 2. One which answers "no", also without reading any input.
>>>>
>>>> The fact that we don't know which one is correct has no bearing on
>>>> the decidability of the problem. The fact that there _is_ a decider
>>>> is all that we're concerned with.
>>>
>>> The point is that this entails that ALL FINITE questions (and
>>> therefore all individual questions)
>>> ARE ALWAYS decidable. P.O. is so confused that he not only talks
>>> about individual
>>> quetsions being decidable, he even talks about an individual TM being
>>> decidable, or an
>>> individual input to a TM being decidable.
>>>
>>> The kinds of things that CAN actually be decidable (or un) ARE
>>> INFINITE families of (similar) questions.
>>
>> You got this right in the first paragraph, but wrong immediately above.
>> Every set of finite strings is either decidable or undecidable. Of
>> course, if the set is finite we know which - it is decidable. All
>> undecidable sets are infinite.
>>
>> Patricia
>
> The first paragraph is a lie.
I have done you the courtesy of assuming that all your incorrect
> On 4/21/2012 1:36 AM, Patricia Shanahan wrote:
>> On 4/20/2012 9:35 PM, George Greene wrote:
>>> On Apr 19, 11:02 pm, Rick Decker<rdec...@hamilton.edu> wrote:
>>>> 1. One which answers "yes" without reading any input, or
>>>> 2. One which answers "no", also without reading any input.
>>>>
>>>> The fact that we don't know which one is correct has no bearing on
>>>> the decidability of the problem. The fact that there _is_ a decider
>>>> is all that we're concerned with.
>>>
>>> The point is that this entails that ALL FINITE questions (and
>>> therefore all individual questions)
>>> ARE ALWAYS decidable. P.O. is so confused that he not only talks
>>> about individual
>>> quetsions being decidable, he even talks about an individual TM being
>>> decidable, or an
>>> individual input to a TM being decidable.
>>>
>>> The kinds of things that CAN actually be decidable (or un) ARE
>>> INFINITE families of (similar) questions.
>>
>> You got this right in the first paragraph, but wrong immediately above.
>> Every set of finite strings is either decidable or undecidable. Of
>> course, if the set is finite we know which - it is decidable. All
>> undecidable sets are infinite.
>>
>> Patricia
>
> The first paragraph is a lie.
statements are due to an honest lack of understanding, rather than being
lies. Don't you think you owe the rest of us the same courtesy?
>
> M( String Input )
> {
> if ( Halts( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> What is the correct {true, false} return value that the invocation of
> Halts(M, M) could possibly provide?
know because you have still not told us anything about its implementation.
If Halts(Input, Input) fails to terminate or returns true, the correct
answer to whether that program terminates is "false". If Halts returns
anything other than "true" (due to its lack of specification I do not
know the range of its results) then the correct answer to whether the
program terminates is true.
Obviously, Halts is not a halting decider, because it does not get the
right answer, but I don't take existence of a halting decider as an
axiom. Indeed, any system of mathematics that incorporates all the usual
axioms but adds an axiom saying there is a TM that decides TM halting
would be inconsistent, and therefore useless.
Patricia
Peter Olcott
Apr 21, 2012, 10:37:46 AM4/21/12
to
several months I increase the harshness to reduce the chance that it
will be ignored in the future.
>
>
>>
>> M( String Input )
>> {
>> if ( Halts( Input, Input ) )
>> Loop Forever;
>> else
>> Exit;
>> }
>>
>> What is the correct {true, false} return value that the invocation of
>> Halts(M, M) could possibly provide?
>
> The correct {true, false} value depends on what Halts does which I don't
> know because you have still not told us anything about its
> implementation.
>
Every possible implementation.
>
>>
>> M( String Input )
>> {
>> if ( Halts( Input, Input ) )
>> Loop Forever;
>> else
>> Exit;
>> }
>>
>> What is the correct {true, false} return value that the invocation of
>> Halts(M, M) could possibly provide?
>
> The correct {true, false} value depends on what Halts does which I don't
> know because you have still not told us anything about its
> implementation.
>
> If Halts(Input, Input) fails to terminate or returns true, the correct
> answer to whether that program terminates is "false". If Halts returns
Here is the question:
What correct Boolean return value can the invocation
of (any possible implementation of) Halts(M, M)
possibly provide from the set of {true, false} ?
(a) true
(b) false
(c) neither, thus proving that the question is ill-formed.
Leif Roar Moldskred
Apr 21, 2012, 10:46:52 AM4/21/12
to
> What correct Boolean return value can the invocation
> of (any possible implementation of) Halts(M, M)
> possibly provide from the set of {true, false} ?
> (a) true
> (b) false
> (c) neither, thus proving that the question is ill-formed.
Depending on what you mean with Halts() today, the answer is actually
> of (any possible implementation of) Halts(M, M)
> possibly provide from the set of {true, false} ?
> (a) true
> (b) false
> (c) neither, thus proving that the question is ill-formed.
one of these two options:
(d) either; it depends on the particular implementation of
Halts()
(e) Halts() doesn't actually exist, so the question is
nonsensical and has no answer.
--
Leif Roar Moldskred
George Greene
Apr 21, 2012, 11:22:25 AM4/21/12
to
We may finally be getting close to the actual issue here.
Prior tryers have also gotten close to this; I don't remember who
but somebody did already suggest that you just call it h (as a
variable)
instead of Halts(,) because Halts(,) has A KNOWN *CONSTANT* meaning.
On Apr 21, 8:23 am, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> Don't say that Halts() can not possibly exist that is a lie too.
> Halts() could simply loop on the above input, and thus exist.
Your main problem is that you can't tell whether your name is the name
of A CONSTANT or of A VARIABLE.
Suppose you really wanted the age of your next girlfriend to be 24.
Suppose for various reasons that that
just couldn't happen. Suppose you were instead going to have to
settle for a girlfriend of age 23 or 25.
Suppose you had, in your mind, this fantasy of "my-24-year-old-
girlfriend". Suppose we told you
"that can't exist". Suppose you then met a 23-year-old woman with
whom you had mutual romantic
chemistry. Suppose you then try to say, "My fantasy is fulfilled!
My-24-year-old-girlfriend DOES exist
AND HERE she is!" We repeat, she *can't* exist. You canNOT then
just say "my-24-year-old-girlfriend can
just be *23*, and thereby exist". Well, I mean, YOU COULD, if the
NAME you had chosen to REFER to her
by was "my Dulcinea" INSTEAD OF "my-24-yr-old-girlfriend". But you,
being a dumbass, couldn't tell the difference.
You are NOT talking about a Halt-analzyer that, regardless of its
changing characteristics, will
stay NAMED "Halts(,)". Halts is NOT THAT KIND of name. Halts(,) is
like *5*, or like 24.
You can't ask "what's the value of 24 today?" or "what's the value of
5 today"?
Suppose you really thought you needed 24 of something and the number
of these things
you needed had always generally been assumed to be 24. Suppose things
started going wrong
and there began to be evidence that you REALLY needed a number of
these things that
was divisible by 5. You CAN"T just say, "well, we can just change the
value of 24 to 25 and then
24 will then meet our goal of being divisible by 5". 24 IS NOT a
variable-name! IT'S A CONSTANT!!
If you are going to have something THAT IS a variable name, you should
NOT PICK a name that
LOOKS LIKE, sounds like, and is USUALLY INTERPRETED AS a CONSTANT!!
If you are just talking about DIFFERENT *CANDIDATES* for a halt-
analyzer, different
POSSIBLE TMs that you COULD use to try to analyze halting, THEN YOU
HAVE TO SAY SOMETHING
about how THEY behave -- YOU HAVE TO WRITE SOME CODE for them. You
can't just CALL them a
name THAT IS ALREADY TAKEN and that ALREADY MEANS something ELSE!
IT DOES NOT MATTER that self-reference is occuring and IT DOES NOT
MATTER how pathological it is.
YOU WILL STILL HAVE A WELL-DEFINED ANSWER TO ALL HALTING QUESTIONS
about REAL tm's
that ACTUALLY exist. YOU ONLY run into contradiction and problems
when you try to invoke something
that CAN'T BE a TM, LIKE Halts(,).
*JUST*STOP* C A L L I NG it Halts(,)!
!!!!!!!!!!!!!!!!!!!!! THAT'S AN *ORDER*!!!!!!!!!!!!!!!!!!!!!!!
And Darryl and Josh and Patricia and EVERYBODY ELSE, DAMMIT, GET WITH
THE *PROGRAM*.
THIS IS THE CORE POINT.
YOU guys know what the universal-generalization-inference-rule is EVEN
IF HE DOESN'T.
YOU guys know that you have to begin by saying "let a be" AN ARBITRARY
thing such that whatever,
and then, when the result is proved from this completely NEW name "a"
that is NOT mentioned
in the axioms, YOU CAN UNIVERSALLY GENERALIZE it to ANY "a". There is
confusion in texts
as to whether this name is a variable-name or an arbitrary constant
(don't-CARE confusion;
it's under-determined BECAUSE IT DOESN'T MATTER) but the point is, IT
CAN'T be any name
that is ALREADY IN use. IT HAS to be something free to change around
to ANYthing that
COULD meet all the relevant constraints. Since the denial of an
existential is a universal,
the assumption that any arbitrary "a" satisfies some criteria can
quickly turn into a NON-existence
proof, a proof that FOR ALL a, a is NOT (whatever; in this case, A
HALTS(,) TM), indirectly.
But in order to avoid confusing P.O., THE NAME *truly*MUST*be* "a" AND
NOT Halts(,),
since otherwise, well, YOU SEE what confusion has reigned for two
months now.
Prior tryers have also gotten close to this; I don't remember who
but somebody did already suggest that you just call it h (as a
variable)
instead of Halts(,) because Halts(,) has A KNOWN *CONSTANT* meaning.
On Apr 21, 8:23 am, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> Don't say that Halts() can not possibly exist that is a lie too.
> Halts() could simply loop on the above input, and thus exist.
of A CONSTANT or of A VARIABLE.
Suppose you really wanted the age of your next girlfriend to be 24.
Suppose for various reasons that that
just couldn't happen. Suppose you were instead going to have to
settle for a girlfriend of age 23 or 25.
Suppose you had, in your mind, this fantasy of "my-24-year-old-
girlfriend". Suppose we told you
"that can't exist". Suppose you then met a 23-year-old woman with
whom you had mutual romantic
chemistry. Suppose you then try to say, "My fantasy is fulfilled!
My-24-year-old-girlfriend DOES exist
AND HERE she is!" We repeat, she *can't* exist. You canNOT then
just say "my-24-year-old-girlfriend can
just be *23*, and thereby exist". Well, I mean, YOU COULD, if the
NAME you had chosen to REFER to her
by was "my Dulcinea" INSTEAD OF "my-24-yr-old-girlfriend". But you,
being a dumbass, couldn't tell the difference.
You are NOT talking about a Halt-analzyer that, regardless of its
changing characteristics, will
stay NAMED "Halts(,)". Halts is NOT THAT KIND of name. Halts(,) is
like *5*, or like 24.
You can't ask "what's the value of 24 today?" or "what's the value of
5 today"?
Suppose you really thought you needed 24 of something and the number
of these things
you needed had always generally been assumed to be 24. Suppose things
started going wrong
and there began to be evidence that you REALLY needed a number of
these things that
was divisible by 5. You CAN"T just say, "well, we can just change the
value of 24 to 25 and then
24 will then meet our goal of being divisible by 5". 24 IS NOT a
variable-name! IT'S A CONSTANT!!
If you are going to have something THAT IS a variable name, you should
NOT PICK a name that
LOOKS LIKE, sounds like, and is USUALLY INTERPRETED AS a CONSTANT!!
If you are just talking about DIFFERENT *CANDIDATES* for a halt-
analyzer, different
POSSIBLE TMs that you COULD use to try to analyze halting, THEN YOU
HAVE TO SAY SOMETHING
about how THEY behave -- YOU HAVE TO WRITE SOME CODE for them. You
can't just CALL them a
name THAT IS ALREADY TAKEN and that ALREADY MEANS something ELSE!
IT DOES NOT MATTER that self-reference is occuring and IT DOES NOT
MATTER how pathological it is.
YOU WILL STILL HAVE A WELL-DEFINED ANSWER TO ALL HALTING QUESTIONS
about REAL tm's
that ACTUALLY exist. YOU ONLY run into contradiction and problems
when you try to invoke something
that CAN'T BE a TM, LIKE Halts(,).
*JUST*STOP* C A L L I NG it Halts(,)!
!!!!!!!!!!!!!!!!!!!!! THAT'S AN *ORDER*!!!!!!!!!!!!!!!!!!!!!!!
And Darryl and Josh and Patricia and EVERYBODY ELSE, DAMMIT, GET WITH
THE *PROGRAM*.
THIS IS THE CORE POINT.
YOU guys know what the universal-generalization-inference-rule is EVEN
IF HE DOESN'T.
YOU guys know that you have to begin by saying "let a be" AN ARBITRARY
thing such that whatever,
and then, when the result is proved from this completely NEW name "a"
that is NOT mentioned
in the axioms, YOU CAN UNIVERSALLY GENERALIZE it to ANY "a". There is
confusion in texts
as to whether this name is a variable-name or an arbitrary constant
(don't-CARE confusion;
it's under-determined BECAUSE IT DOESN'T MATTER) but the point is, IT
CAN'T be any name
that is ALREADY IN use. IT HAS to be something free to change around
to ANYthing that
COULD meet all the relevant constraints. Since the denial of an
existential is a universal,
the assumption that any arbitrary "a" satisfies some criteria can
quickly turn into a NON-existence
proof, a proof that FOR ALL a, a is NOT (whatever; in this case, A
HALTS(,) TM), indirectly.
But in order to avoid confusing P.O., THE NAME *truly*MUST*be* "a" AND
NOT Halts(,),
since otherwise, well, YOU SEE what confusion has reigned for two
months now.
Patricia Shanahan
Apr 21, 2012, 11:26:03 AM4/21/12
to
On 4/21/2012 7:46 AM, Leif Roar Moldskred wrote:
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>
>> What correct Boolean return value can the invocation
>> of (any possible implementation of) Halts(M, M)
>> possibly provide from the set of {true, false} ?
>> (a) true
>> (b) false
>> (c) neither, thus proving that the question is ill-formed.
>
> Depending on what you mean with Halts() today, the answer is actually
> one of these two options:
>
> (d) either; it depends on the particular implementation of
> Halts()
I based my answer on the assumption that Halts is meant to be some TM.
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>
>> What correct Boolean return value can the invocation
>> of (any possible implementation of) Halts(M, M)
>> possibly provide from the set of {true, false} ?
>> (a) true
>> (b) false
>> (c) neither, thus proving that the question is ill-formed.
>
> Depending on what you mean with Halts() today, the answer is actually
> one of these two options:
>
> (d) either; it depends on the particular implementation of
> Halts()
> (e) Halts() doesn't actually exist, so the question is
> nonsensical and has no answer.
>
on this.
I think the relevant question is "Does this TM computation halt?" and
that question indeed has a {true, false} answer for every choice of TM
computation. That assumes Halts is meant to be a TM-computable function.
If you assume Halts is something that decides TM halting, it is not a TM
computable function, so no program incorporating it specifies a TM, and
there is no TM halting question to answer.
Patricia
Patricia Shanahan
Apr 21, 2012, 11:40:10 AM4/21/12
to
On 4/21/2012 7:37 AM, Peter Olcott wrote:
> On 4/21/2012 8:49 AM, Patricia Shanahan wrote:
...
> On 4/21/2012 8:49 AM, Patricia Shanahan wrote:
>> I have done you the courtesy of assuming that all your incorrect
>> statements are due to an honest lack of understanding, rather than
>> being lies. Don't you think you owe the rest of us the same courtesy?
>
> When people continue to ignore my reasoning many hundreds of times over
> several months I increase the harshness to reduce the chance that it
> will be ignored in the future.
I don't think anyone posting in this thread has been ignoring your
>> statements are due to an honest lack of understanding, rather than
>> being lies. Don't you think you owe the rest of us the same courtesy?
>
> When people continue to ignore my reasoning many hundreds of times over
> several months I increase the harshness to reduce the chance that it
> will be ignored in the future.
reasoning. We just disagree with it.
There is only one instance in which I have deliberately chosen to ignore
something you wrote, as distinct from being too busy or deciding others
have already written everything I would have written.
That is https://groups.google.com/group/sci.logic/msg/2ff9f20c715d9256
where you indicated your claimed quote from Sipser was in a "paragraph
named Diagonalization".
I have still not found that paragraph. It is neither on page 230, the
last page reference you gave, nor in the section headed "THE HALTING
PROBLEM IS UNDECIDABLE", where I would expect to find any relevant
definitions. Please give specific page number and position on page in
the 1997 edition.
Patricia
Peter Olcott
Apr 21, 2012, 11:57:06 AM4/21/12
to
defined as the wrong answer, therefore your answer is incorrect.
Is your answer incorrect because:
(a) The question is ill-formed.
(b) You are just not very good at answering questions.
Peter Olcott
Apr 21, 2012, 12:01:43 PM4/21/12
to
On 4/21/2012 10:26 AM, Patricia Shanahan wrote:
> On 4/21/2012 7:46 AM, Leif Roar Moldskred wrote:
>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>>
>>> What correct Boolean return value can the invocation
>>> of (any possible implementation of) Halts(M, M)
>>> possibly provide from the set of {true, false} ?
>>> (a) true
>>> (b) false
>>> (c) neither, thus proving that the question is ill-formed.
>>
>> Depending on what you mean with Halts() today, the answer is actually
>> one of these two options:
>>
>> (d) either; it depends on the particular implementation of
>> Halts()
>
> I based my answer on the assumption that Halts is meant to be some TM.
>
>> (e) Halts() doesn't actually exist, so the question is
>> nonsensical and has no answer.
>>
>
> It depends on what you mean by "the question". Clearly PO and I disagree
> on this.
>
> On 4/21/2012 7:46 AM, Leif Roar Moldskred wrote:
>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>>
>>> What correct Boolean return value can the invocation
>>> of (any possible implementation of) Halts(M, M)
>>> possibly provide from the set of {true, false} ?
>>> (a) true
>>> (b) false
>>> (c) neither, thus proving that the question is ill-formed.
>>
>> Depending on what you mean with Halts() today, the answer is actually
>> one of these two options:
>>
>> (d) either; it depends on the particular implementation of
>> Halts()
>
> I based my answer on the assumption that Halts is meant to be some TM.
>
>> (e) Halts() doesn't actually exist, so the question is
>> nonsensical and has no answer.
>>
>
> It depends on what you mean by "the question". Clearly PO and I disagree
> on this.
>
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
What correct Boolean return value can the invocation
of (any possible implementation of) Halts(M, M)
possibly provide from the set of {true, false} ?
(a) true
(b) false
(c) neither, thus proving that the question itself is ill-formed.
of (any possible implementation of) Halts(M, M)
possibly provide from the set of {true, false} ?
(a) true
(b) false
Any question that is not semantically identical to the above question is
defined to be the *WRONG* question. If you disagree, then your lack of
agreement is defined to be incorrect.
George Greene
Apr 21, 2012, 12:19:51 PM4/21/12
to
On Apr 21, 10:46 am, Leif Roar Moldskred <le...@dimnakorr.com> wrote:
> Depending on what you mean with Halts() today,
Leif, PLEASE, this is NOT helping!
> Depending on what you mean with Halts() today,
HE DOESN'T KNOW THE DIFFERENCE between A CONSTANT AND A VARIABLE!
He is using Halts(,) AS A TM *VARIABLE* but DOES NOT *KNOW* this!
IF YOU DO, THEN STOP asking him what HE means (that NEVER MATTERS; he
is
CONFUSED!) AND TELL him what IS ACTUALLY happening!!
Patricia Shanahan
Apr 21, 2012, 12:38:34 PM4/21/12
to
On 4/21/2012 9:01 AM, Peter Olcott wrote:
...
mathematics and computational theory, you do not get to define what is
or is not a valid question.
The question I want to focus on is exactly the question that lies at the
heart of the undecidability of TM halting, by the common definitions
used in papers and books in the field.
Patricia
...
> Any question that is not semantically identical to the above question is
> defined to be the *WRONG* question. If you disagree, then your lack of
> agreement is defined to be incorrect.
Unfortunately for you, but fortunately for the general coherence of
> defined to be the *WRONG* question. If you disagree, then your lack of
> agreement is defined to be incorrect.
mathematics and computational theory, you do not get to define what is
or is not a valid question.
The question I want to focus on is exactly the question that lies at the
heart of the undecidability of TM halting, by the common definitions
used in papers and books in the field.
Patricia
Peter Olcott
Apr 21, 2012, 12:58:03 PM4/21/12
to
On 4/21/2012 11:38 AM, Patricia Shanahan wrote:
> On 4/21/2012 9:01 AM, Peter Olcott wrote:
> ...
>> Any question that is not semantically identical to the above question is
>> defined to be the *WRONG* question. If you disagree, then your lack of
>> agreement is defined to be incorrect.
>
> Unfortunately for you, but fortunately for the general coherence of
> mathematics and computational theory, you do not get to define what is
> or is not a valid question.
>
No one gets to define what is and what is not a valid question.
> On 4/21/2012 9:01 AM, Peter Olcott wrote:
> ...
>> Any question that is not semantically identical to the above question is
>> defined to be the *WRONG* question. If you disagree, then your lack of
>> agreement is defined to be incorrect.
>
> Unfortunately for you, but fortunately for the general coherence of
> mathematics and computational theory, you do not get to define what is
> or is not a valid question.
>
This is tautologically specified by the meaning of the underlying terms.
When I say that question X is invalid, and you say no that
is not true question Y is valid, your error is known as
the non-sequitur logical fallacy.
> The question I want to focus on is exactly the question that lies at the
> heart of the undecidability of TM halting, by the common definitions
> used in papers and books in the field.
>
> Patricia
>
is known as the fallacy of equivocation error. They never realized that
they were focusing on the wrong question.
Leif Roar Moldskred
Apr 21, 2012, 1:13:31 PM4/21/12
to
> When I say that question X is invalid, and you say no that
> is not true question Y is valid, your error is known as
> the non-sequitur logical fallacy.
That's ... astoundingly wrong.
> is not true question Y is valid, your error is known as
> the non-sequitur logical fallacy.
--
Leif Roar Moldskred
Peter Olcott
Apr 21, 2012, 1:36:18 PM4/21/12
to
That's astoundingly ignorant.
http://en.wikipedia.org/wiki/Non_sequitur_(logic)
Non sequitur (Latin for "it does not follow"), in formal logic, is an argument in which its conclusion does not follow from its premises.
http://en.wikipedia.org/wiki/Non_sequitur_(logic)
Non sequitur (Latin for "it does not follow"), in formal logic, is an argument in which its conclusion does not follow from its premises.
Leif Roar Moldskred
Apr 21, 2012, 1:48:01 PM4/21/12
to
In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:
> [-- text/plain, encoding 7bit, charset: ISO-8859-1, 15 lines --]
>
> On 4/21/2012 12:13 PM, Leif Roar Moldskred wrote:
>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>> When I say that question X is invalid, and you say no that
>>> is not true question Y is valid, your error is known as
>>> the non-sequitur logical fallacy.
>> That's ... astoundingly wrong.
>>
> That's astoundingly ignorant.
That too, but I was trying to be nice.
> On 4/21/2012 12:13 PM, Leif Roar Moldskred wrote:
>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>> When I say that question X is invalid, and you say no that
>>> is not true question Y is valid, your error is known as
>>> the non-sequitur logical fallacy.
>> That's ... astoundingly wrong.
>>
> That's astoundingly ignorant.
> http://en.wikipedia.org/wiki/Non_sequitur_(logic)
>
> /*Non sequitur*/ (Latin </wiki/Latin> for "it does not follow"), in
> formal logic, is an argument in which its conclusion does not follow
> from its premises.
You can't have a non sequitur without first having a logical argument
> from its premises.
-- a premise followed by a conclusion. "No, question Y is valid" is a
plain statement. It _can not be_ a non sequitur because it is not a
logical argument.
Furthermore, if you are going to accuse someone of having made a non
sequitur it behooves you to show _why_ the conclusion doesn't follow
from the premise.
Anyway, you've been an amusing buffoon, but for my part the well of
idle amusement is running dry, so I'll leave you to your
misapprehensions and attempts at feigning competence.
(And for the record, no, the above is not an ad hominew. It's a
plain insult.)
--
Leif Roar Moldskred
George Greene
Apr 21, 2012, 2:03:23 PM4/21/12
to
On Apr 21, 12:58 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> No one gets to define what is and what is not a valid question.
This is OUR field. WE get to define EVERYthing, INCLUDING "Question"
> No one gets to define what is and what is not a valid question.
and "question".
> This is tautologically specified by the meaning of the underlying terms.
"decidable",
for example. The meanings of the underlying terms ARE STIPULATED *BY
US*.
WE get to define EVERYthing.
> When I say that question X is invalid, and you say no that
> is not true question Y is valid, your error is known as
> the non-sequitur logical fallacy.
If you had, you wouldn't be committing so many.
It might help if you would tell a little more about your age or your
college,
or why you care about this question, or how it comes to be the case
that
you EVEN HAVE TIME to write all this.
> The reason that they have gotten the wrong answer for all of these years
> is known as the fallacy of equivocation error. They never realized that
> they were focusing on the wrong question.
Bryan
Apr 21, 2012, 4:07:46 PM4/21/12
to
Peter Olcott wrote:
> None of my four text books provide such a specification, they all
> provide the same hypothetical frameworks that I am providing.
There's no reason to go smearing respectable textbooks.
> I would
> imagine that an actual Turing machine that even attempts to decide
> whether another TM halts would be quote cumbersome to specify.
Let me point you to how I did it in the predecessor to this thread:
"What's more, given a TM, call it 'PHaults' (pseudo-halts), that never
answers incorrectly, we can construct a TM that correctly answers all
the same cases as PHaults, plus always answers correctly when the
answer is 'Halts'. Proof by construction: We interleave emulation of
both PHalts on input (m, s) and m on input s. When either of them
halts we have the answer: the output of PHaults if it halts first, or
'Halts' if m halts first."
You don't have to go down to state transitions. Anything anyone has
ever proven TM's can do is granted. Emulating arbitrary Turing
machines, interleaving them and such, *that* you will find in your
four textbooks.
Peter, your first, critical, step was: "if tm halts on input". I hope
those theory texts look good on your shelf, because you sure ain't
applying their content.
-Bryan
> None of my four text books provide such a specification, they all
> provide the same hypothetical frameworks that I am providing.
There's no reason to go smearing respectable textbooks.
> I would
> imagine that an actual Turing machine that even attempts to decide
> whether another TM halts would be quote cumbersome to specify.
Let me point you to how I did it in the predecessor to this thread:
"What's more, given a TM, call it 'PHaults' (pseudo-halts), that never
answers incorrectly, we can construct a TM that correctly answers all
the same cases as PHaults, plus always answers correctly when the
answer is 'Halts'. Proof by construction: We interleave emulation of
both PHalts on input (m, s) and m on input s. When either of them
halts we have the answer: the output of PHaults if it halts first, or
'Halts' if m halts first."
You don't have to go down to state transitions. Anything anyone has
ever proven TM's can do is granted. Emulating arbitrary Turing
machines, interleaving them and such, *that* you will find in your
four textbooks.
Peter, your first, critical, step was: "if tm halts on input". I hope
those theory texts look good on your shelf, because you sure ain't
applying their content.
-Bryan
Peter Olcott
Apr 21, 2012, 4:17:04 PM4/21/12
to
On 4/21/2012 12:48 PM, Leif Roar Moldskred wrote:
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>> [-- text/plain, encoding 7bit, charset: ISO-8859-1, 15 lines --]
>>
>> On 4/21/2012 12:13 PM, Leif Roar Moldskred wrote:
>>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>>> When I say that question X is invalid, and you say no that
>>>> is not true question Y is valid, your error is known as
>>>> the non-sequitur logical fallacy.
>>> That's ... astoundingly wrong.
>>>
>> That's astoundingly ignorant.
> That too, but I was trying to be nice.
>
>> http://en.wikipedia.org/wiki/Non_sequitur_(logic)
>>
>> /*Non sequitur*/ (Latin</wiki/Latin> for "it does not follow"), in
>> formal logic, is an argument in which its conclusion does not follow
>> from its premises.
> You can't have a non sequitur without first having a logical argument
> -- a premise followed by a conclusion. "No, question Y is valid" is a
> plain statement. It _can not be_ a non sequitur because it is not a
> logical argument.
(a) Question Y is a valid question (premise)
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>> [-- text/plain, encoding 7bit, charset: ISO-8859-1, 15 lines --]
>>
>> On 4/21/2012 12:13 PM, Leif Roar Moldskred wrote:
>>> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>>>> When I say that question X is invalid, and you say no that
>>>> is not true question Y is valid, your error is known as
>>>> the non-sequitur logical fallacy.
>>> That's ... astoundingly wrong.
>>>
>> That's astoundingly ignorant.
> That too, but I was trying to be nice.
>
>> http://en.wikipedia.org/wiki/Non_sequitur_(logic)
>>
>> /*Non sequitur*/ (Latin</wiki/Latin> for "it does not follow"), in
>> formal logic, is an argument in which its conclusion does not follow
>> from its premises.
> You can't have a non sequitur without first having a logical argument
> -- a premise followed by a conclusion. "No, question Y is valid" is a
> plain statement. It _can not be_ a non sequitur because it is not a
> logical argument.
(b) Therefore question X is a valid question (conclusion)
(b) Does not logically follow from (a), thus the conclusion
that (b) does logically follow from (a) is non-sequitur.
Peter Olcott
Apr 21, 2012, 4:30:07 PM4/21/12
to
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
else
Exit;
}
What correct Boolean return value can the invocation
of (any possible implementation of) Halts(M, M)
possibly provide from the set of {true, false} ?
(a) true
(b) false
(c) neither, thus proving that the question itself is ill-formed.
every possible implementation of M and Halts.
To make the syntax a little more conventional
I would have to say something like:
For every element m of the infinite set of Turing Machines M
that is derived from elements h of the infinite set of Turing Machines H:
What correct Boolean return value can the invocation
This seems far too clumsy of a way to say the same thing that
I already said using far less convoluted and clumsy terms.
If you try to find any possible implementation of the combination of
Halts and M such that the invocation Halts can correctly return a
Boolean value from the set of {true, false}, you will fail, thus
conclusively proving that the above question is ill-formed, and
therefore the Halting Problem itself is entirely based on an ill-formed
question.
Bryan
Apr 21, 2012, 4:40:48 PM4/21/12
to
Peter Olcott wrote:
> M( String Input )
> {
> if ( Halts( Input, Input ) )
> Loop Forever;
> else
> Exit;
>
> }
>
> What correct Boolean return value can the invocation
> of (any possible implementation of) Halts(M, M)
> possibly provide from the set of {true, false} ?
You've conflated two questions. What is the correct answer? The
> M( String Input )
> {
> if ( Halts( Input, Input ) )
> Loop Forever;
> else
> Exit;
>
> }
>
> What correct Boolean return value can the invocation
> of (any possible implementation of) Halts(M, M)
> possibly provide from the set of {true, false} ?
correct answer is false. Can Halts() provide it? No.
-Bryan
Peter Olcott
Apr 21, 2012, 5:00:12 PM4/21/12
to
{true, false} just like they are in the Halting Problem.
Why did you not provide the correct answer?
(a) The question ill-formed.
(b) You are not very good at answering questions.
Bryan
Apr 21, 2012, 5:38:21 PM4/21/12
to
Peter Olcott wrote:
> Bryan wrote:
> > Peter Olcott wrote:
> >> M( String Input )
> >> {
> >> if ( Halts( Input, Input ) )
> >> Loop Forever;
> >> else
> >> Exit;
> >> }
>
> >> What correct Boolean return value can the invocation
> >> of (any possible implementation of) Halts(M, M)
> >> possibly provide from the set of {true, false} ?
> > You've conflated two questions. What is the correct answer? The
> > correct answer is false. Can Halts() provide it? No.
>
> Bryan wrote:
> > Peter Olcott wrote:
> >> M( String Input )
> >> {
> >> if ( Halts( Input, Input ) )
> >> Loop Forever;
> >> else
> >> Exit;
> >> }
>
> >> What correct Boolean return value can the invocation
> >> of (any possible implementation of) Halts(M, M)
> >> possibly provide from the set of {true, false} ?
> > You've conflated two questions. What is the correct answer? The
> > correct answer is false. Can Halts() provide it? No.
>
> Sorry *WRONG* answer, answers are limited to the set of
> {true, false} just like they are in the Halting Problem.
That's the "invincible ignorance" fallacy.
> {true, false} just like they are in the Halting Problem.
Assuming Halts() is a TM that attempts to decide the language Halts
and never answers incorrectly, the correct answer to Halts(M, M) is
'false'. Evaluating the conditional if( Halts( Input, Input ) ) must
not terminate, because if it does it would violate the assumption.
Given Halts(), I can construct another pseudo-decider for halting
that:
1) Never answers the halting problem incorrectly
2) Answers in every case that Halts() answers
3) Correctly answers the instance Halts(M, M)
Proof by construction: The TM checks if the input is Halts(M, M); if
so it answers 'false' and if not it goes to emulation of Halts().
Apart from that we've assumed rather than defined Halts(), there's
nothing improper or ill-defined about Halts(M, M). It's an instance
that does not halt. Halts() does not answer incorrectly, because it
never arrives at an answer.
> Why did you not provide the correct answer?
> (a) The question ill-formed.
> (b) You are not very good at answering questions.
quite the fountain of fallacies, delivered with a heavy dose of what
psychologists call "projection".
-Bryan
Bryan
Apr 21, 2012, 5:53:03 PM4/21/12
to
George Greene wrote:
> So are you NOW FINALLY going to CALL it "PotentialHaltDecider"
> INSTEAD OF "Halts(,)" ??? TO WHOM and what do we owe this
> majestic evolution???????????????????????????????
[...]
> Congratulations.
> You finally understand.
> I don't know which TEACHER to congratulate (probably Darryl, but he
> had to
> wait a month for other people to soften you up) but at least this
> Proves It Can Be Done!
Alas, within a day he regressed.
Goals should be realistic.This isn't just months. Try a groups search
for keywords: peter olcott halting
http://groups.google.com/advanced_search
-Bryan
> So are you NOW FINALLY going to CALL it "PotentialHaltDecider"
> INSTEAD OF "Halts(,)" ??? TO WHOM and what do we owe this
> majestic evolution???????????????????????????????
[...]
> Congratulations.
> You finally understand.
> I don't know which TEACHER to congratulate (probably Darryl, but he
> had to
> wait a month for other people to soften you up) but at least this
> Proves It Can Be Done!
Alas, within a day he regressed.
Goals should be realistic.This isn't just months. Try a groups search
for keywords: peter olcott halting
http://groups.google.com/advanced_search
-Bryan
Peter Olcott
Apr 21, 2012, 6:11:25 PM4/21/12
to
On 4/21/2012 4:38 PM, Bryan wrote:
> Peter Olcott wrote:
>> > Bryan wrote:
>>> > > Peter Olcott wrote:
>>>> > >> M( String Input )
>>>> > >> {
>>>> > >> if ( Halts( Input, Input ) )
>>>> > >> Loop Forever;
>>>> > >> else
>>>> > >> Exit;
>>>> > >> }
>> >
>>>> > >> What correct Boolean return value can the invocation
>>>> > >> of (any possible implementation of) Halts(M, M)
>>>> > >> possibly provide from the set of {true, false} ?
>>> > > You've conflated two questions. What is the correct answer? The
>>> > > correct answer is false. Can Halts() provide it? No.
>> >
>> > Sorry*WRONG* answer, answers are limited to the set of
> Peter Olcott wrote:
>> > Bryan wrote:
>>> > > Peter Olcott wrote:
>>>> > >> M( String Input )
>>>> > >> {
>>>> > >> if ( Halts( Input, Input ) )
>>>> > >> Loop Forever;
>>>> > >> else
>>>> > >> Exit;
>>>> > >> }
>> >
>>>> > >> What correct Boolean return value can the invocation
>>>> > >> of (any possible implementation of) Halts(M, M)
>>>> > >> possibly provide from the set of {true, false} ?
>>> > > You've conflated two questions. What is the correct answer? The
>>> > > correct answer is false. Can Halts() provide it? No.
>> >
>> > {true, false} just like they are in the Halting Problem.
> That's the "invincible ignorance" fallacy.
The "conflated" question is the same question that every potential halt
> That's the "invincible ignorance" fallacy.
decider is asked.
The answer is limited to {true, false} just like the question posed to
you was limted to {true, false}.
You failed to correctly answer this question with the limitation of a
{true, false} answer for the same reason that the potential halt decider
fails to answer this question.
The question itself is ill-formed.
The potential halt decider is not simply asked whether or not M halts on
input M. It is asked whether or not M halts on input M within the
specific context of Pathological Self-Reference.
Peter Olcott
Apr 21, 2012, 6:32:29 PM4/21/12
to
halt decider is that it can not provide a correct {true, false} return
value to an invocation that has no correct {true, false} return value
(in other words the only questions that it can not answer are incorrect
questions) there is no relevant difference between a potential halt
decider and an actual halt decider.
Joshua Cranmer
Apr 21, 2012, 6:59:26 PM4/21/12
to
On 4/21/2012 5:32 PM, Peter Olcott wrote:
> Since the *only* reason that the potential halt decider is not an actual
> halt decider is that it can not provide a correct {true, false} return
> value to an invocation that has no correct {true, false} return value
In the wonderful notation of Wikipedia: [citation needed]
> Since the *only* reason that the potential halt decider is not an actual
> halt decider is that it can not provide a correct {true, false} return
> value to an invocation that has no correct {true, false} return value
Also, note that it is not the only reason, but the only reason that you
appear to be able to comprehend. There are other proofs of the
undecidability of the Halting problem which do not necessitate a
self-referential problem as input. You have either dismissed them as
"then it must involve Pathological self-reference" without giving any
proof of that fact or you have ignored them because you do not
understand the proof.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
George Greene
Apr 21, 2012, 7:29:37 PM4/21/12
to
Halts(,) DOES NOT EXIST. YOU MUST *CALL* this SOMETHING ELSE.
THERE IS NO Halts(,) TM and in order for M to be a TM, the thing you
invoke to
return a boolean to this if, MUST BE AN TM THAT ACTUALLY *EXISTS*.
If you are not going to DESCRIBE this TM in any way, if you are NOT
going to write any CODE for it,
then ALL we have to go on (by way of expectations about its behavior)
IS ITS NAME, so its NAME
better either say NOTHING (meaning it can be any old generic TM; this
result will apply TO ALL TMs),
or it better say SOMETHING ACCURATE about what the TM *does*. The TM
DEFINITELY DOES NOT
answer all halting questions corectly, SINCE NO TM CAN DO that.
Peter Olcott
Apr 21, 2012, 10:26:59 PM4/21/12
to
On 4/21/2012 5:59 PM, Joshua Cranmer wrote:
> On 4/21/2012 5:32 PM, Peter Olcott wrote:
>> Since the *only* reason that the potential halt decider is not an actual
>> halt decider is that it can not provide a correct {true, false} return
>> value to an invocation that has no correct {true, false} return value
>
> In the wonderful notation of Wikipedia: [citation needed]
>
> Also, note that it is not the only reason, but the only reason that
> you appear to be able to comprehend. There are other proofs of the
> undecidability of the Halting problem which do not necessitate a
> self-referential problem as input. You have either dismissed them as
> "then it must involve Pathological self-reference" without giving any
> proof of that fact or you have ignored them because you do not
> understand the proof.
>
They were not actually undecidable problems, in terms of having
> On 4/21/2012 5:32 PM, Peter Olcott wrote:
>> Since the *only* reason that the potential halt decider is not an actual
>> halt decider is that it can not provide a correct {true, false} return
>> value to an invocation that has no correct {true, false} return value
>
> In the wonderful notation of Wikipedia: [citation needed]
>
> Also, note that it is not the only reason, but the only reason that
> you appear to be able to comprehend. There are other proofs of the
> undecidability of the Halting problem which do not necessitate a
> self-referential problem as input. You have either dismissed them as
> "then it must involve Pathological self-reference" without giving any
> proof of that fact or you have ignored them because you do not
> understand the proof.
>
no possible correct return value from the exhaustively complete
set of all possible return values. They were merely problems where
the correct answer is currently unknown.
Joshua Cranmer
Apr 21, 2012, 10:49:37 PM4/21/12
to
problem is a problem where there exists no way, in general, to find the
correct answer. They have correct answers, and the correct answers may
be unknown... but nor may the correct answers ever be known. The example
I will use today is in solving polynomials over the field of integers:
it is known that no algorithm (discovered or undiscovered) can
conclusively identify if a given polynomial has solutions in the field
of integers. But every polynomial either has solutions or it doesn't
have solutions... but it is impossible to be able to conclusively say
that it doesn't have solutions, in general (note: this is a recognizable
problem but not a decidable one).
Bryan
Apr 22, 2012, 2:20:26 AM4/22/12
to
Peter Olcott wrote:
> George Greene wrote:
> > The point is that this entails that ALL FINITE questions (and
> > therefore all individual questions)
> > ARE ALWAYS decidable.
>
> That is a lie.
There you go again. Projecting.
-Bryan
> George Greene wrote:
> > The point is that this entails that ALL FINITE questions (and
> > therefore all individual questions)
> > ARE ALWAYS decidable.
>
> That is a lie.
There you go again. Projecting.
-Bryan
Peter Olcott
Apr 22, 2012, 4:03:26 AM4/22/12
to
indicate patterns that were previously unknown such that these patterns
can be used to decide other properties of these same sets. It may
require omniscience to prove that this is impossible.
> can conclusively identify if a given polynomial has solutions in the
> field of integers. But every polynomial either has solutions or it
> doesn't have solutions... but it is impossible to be able to
> conclusively say that it doesn't have solutions, in general (note:
> this is a recognizable problem but not a decidable one).
>
Peter Olcott
Apr 22, 2012, 4:17:56 AM4/22/12
to
M( String Input )
{
if ( Halts( Input, Input ) )
Loop Forever;
{
if ( Halts( Input, Input ) )
else
Exit;
}
Since it is impossible to correctly decide between a
{true, false} return value to the invocation of Halts(M, M)
the single instance above is not decidable no matter
who says it is. If it is defined as decidable then it is
defined incorrectly.
Peter Olcott
Apr 22, 2012, 9:49:23 AM4/22/12
to
On 4/22/2012 12:01 AM, George Greene wrote:
>>> In all the example that you keep bringing up:
>>> H(x,y) is assumed to be a partially correct halt decider.
>>> M(x) is defined by:
>>> If H(x,x) = false, then halt, otherwise loop.
>>> Then M(M) doesn't halt. So the question: "Does M halt on input M?"
>>> has the correct answer "no". H(M,M) doesn't return that answer, but
>>> it's the correct answer.
> On Apr 21, 11:14 pm, Peter Olcott<NoS...@OCR4Screen.com> wrote:
>> The ill-formed question that the potential halt decider is required to
>> answer
> DOES NOT EXIST. The question that H *is* answering here IS NOT ill-
> formed.
The actual question to the potential halt decider is not:
Does the input TM halt on its input?
That is *not* the question. Stating that this is the entire question is
a lie. If you continue to insist this, that makes you a liar.
The actual question to the potential halt decider is what return value
(more literally halting state) can be provided that indicates whether or
not the input TM halts on its input?
The potential halt decider is not asked to write its answer on a piece
of paper or to provide its answer by making a telephone call. It is
*only* asked to provide this answer in terms of a return value (more
literally final state) that it can provide.
Since neither return value of the set {true, false} (or final state of
{accept, reject} ) provides the correct return value to the invocation
of this potential halt decider, and these return values form the
exhaustively complete enumeration of all possible return values, the
question posed to the potential halt decider is an ill-formed question.
An ill-formed question is defined as any question that lacks a correct
answer from the set of all possible answers. Citation:(Peter Olcott
2012, sci.logic, comp.theory forums)
My latest example of an ill-formed question is:
How many feet long is the color of your car?
(The answer is limited to numeric values, and non response counts as
incorrect answer).
> H *IS NOT* a Halting Decider! *NO* TM is a Halting Decider!
> The ONLY question you can H ask is "How does H feel about this input?"
> In order for it to be something more, you would have TO KNOW something
> about
> the behavior of H. H is AN ARBITRARY TM here. THE ONLY constraint
> you have
> imposed on it is that it never answer wrongly. H *could* be, for all
> *YOU* know, the
> TM that NEVER answers ANYthing (that loops ALL the time).
> IN ANY case, the M(m) question that you keep accusing of having
> "pathological self-reference"
> DOES NOT EXHIBIT pathological self-reference. It exhibits plenty of
> self-reference but there
> is NOTHING PATHOLOGICAL about it. It only SEEMS pathological when you
> require
> that values returned from H be "correct" if and only if they match
> the real halting answer.
> THAT IS NOT A LEGITIMATE REQUIREMENT OF "CORRECTNESS" FOR *ANY* TM,
> SINCE NO TM can meet that requirement.
> More to the point, even attempting to allege "correctness" or
> "incorrectness" FOR ANY
> TM IS STUPID. ALL TMs ALWAYS CORRECTLY do what THEY do and ALWAYS
> CORRECTLY
> answer that question THAT THEY are programmed to answer.
>
>>> In all the example that you keep bringing up:
>>> H(x,y) is assumed to be a partially correct halt decider.
>>> M(x) is defined by:
>>> If H(x,x) = false, then halt, otherwise loop.
>>> Then M(M) doesn't halt. So the question: "Does M halt on input M?"
>>> has the correct answer "no". H(M,M) doesn't return that answer, but
>>> it's the correct answer.
> On Apr 21, 11:14 pm, Peter Olcott<NoS...@OCR4Screen.com> wrote:
>> The ill-formed question that the potential halt decider is required to
>> answer
> DOES NOT EXIST. The question that H *is* answering here IS NOT ill-
> formed.
The actual question to the potential halt decider is not:
Does the input TM halt on its input?
That is *not* the question. Stating that this is the entire question is
a lie. If you continue to insist this, that makes you a liar.
The actual question to the potential halt decider is what return value
(more literally halting state) can be provided that indicates whether or
not the input TM halts on its input?
The potential halt decider is not asked to write its answer on a piece
of paper or to provide its answer by making a telephone call. It is
*only* asked to provide this answer in terms of a return value (more
literally final state) that it can provide.
Since neither return value of the set {true, false} (or final state of
{accept, reject} ) provides the correct return value to the invocation
of this potential halt decider, and these return values form the
exhaustively complete enumeration of all possible return values, the
question posed to the potential halt decider is an ill-formed question.
An ill-formed question is defined as any question that lacks a correct
answer from the set of all possible answers. Citation:(Peter Olcott
2012, sci.logic, comp.theory forums)
My latest example of an ill-formed question is:
How many feet long is the color of your car?
(The answer is limited to numeric values, and non response counts as
incorrect answer).
> H *IS NOT* a Halting Decider! *NO* TM is a Halting Decider!
> The ONLY question you can H ask is "How does H feel about this input?"
> In order for it to be something more, you would have TO KNOW something
> about
> the behavior of H. H is AN ARBITRARY TM here. THE ONLY constraint
> you have
> imposed on it is that it never answer wrongly. H *could* be, for all
> *YOU* know, the
> TM that NEVER answers ANYthing (that loops ALL the time).
> IN ANY case, the M(m) question that you keep accusing of having
> "pathological self-reference"
> DOES NOT EXHIBIT pathological self-reference. It exhibits plenty of
> self-reference but there
> is NOTHING PATHOLOGICAL about it. It only SEEMS pathological when you
> require
> that values returned from H be "correct" if and only if they match
> the real halting answer.
> THAT IS NOT A LEGITIMATE REQUIREMENT OF "CORRECTNESS" FOR *ANY* TM,
> SINCE NO TM can meet that requirement.
> More to the point, even attempting to allege "correctness" or
> "incorrectness" FOR ANY
> TM IS STUPID. ALL TMs ALWAYS CORRECTLY do what THEY do and ALWAYS
> CORRECTLY
> answer that question THAT THEY are programmed to answer.
>
It is loading more messages.
0 new messages