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.
> On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
>> Peter Olcott<NoS...@OCR4Screen.com> writes:
>>> On 4/19/2012 10:02 PM, Rick Decker wrote:
>>>> On 4/19/12 4:16 PM, Peter Olcott wrote:
>>>>> On 4/19/2012 7:57 AM, Jussi Piitulainen wrote:
>>>>>> Peter Olcott writes:
>>>>>>> On 4/19/2012 1:14 AM, Jussi Piitulainen wrote:
>>>>>>>> Peter Olcott writes:
>>>>>>>>> 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
>>>>>> handwaving, and nobody else knows either.
>>>>> Since no one knows either way, the Decidability thesis is not refuted.
>>>>> 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.
>>>> <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.
> M( String Input )
> {
> if ( Halts( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
> 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.
Fine. In the accepted proof we start by assuming that Halts() is a
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
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.
> (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.
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.
> 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.
> 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 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.
-- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
> 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
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.
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.
> 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 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.
I don't think it's this so much as it is "any function is computable 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. :-)
-- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
> 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
> 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).
The *only* reason that I propose that it can be done is that every 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 writes:
>> 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]
>> If this is *not* an undecidable instance then what element of the
>> set {true, false} can the invocation of Halts(M, M) correctly
>> return?
> [description of why both true and false would be incorrect snipped]
>> (3) This only leaves neither true nor false. I am calling this
>> undecidable. What else can it be called?
> Oh, many things. Bad, erroneous, other, neither, third, unfair,
> 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.
> The question remains, is the third answer interesting. And is the
> three-valued thing implementable.
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?
> Peter Olcott writes:
>> 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]
>> If this is *not* an undecidable instance then what element of the
>> set {true, false} can the invocation of Halts(M, M) correctly
>> return?
> [description of why both true and false would be incorrect snipped]
>> (3) This only leaves neither true nor false. I am calling this
>> undecidable. What else can it be called?
> Oh, many things. Bad, erroneous, other, neither, third, unfair,
> 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.
> 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.
> 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.
> 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.
> On 4/20/12 6:31 AM, Peter Olcott wrote:
>> On 4/20/2012 12:30 AM, Jussi Piitulainen wrote:
>>> Peter Olcott<NoS...@OCR4Screen.com> writes:
>>>> On 4/19/2012 10:02 PM, Rick Decker wrote:
>>>>> On 4/19/12 4:16 PM, Peter Olcott wrote:
>>>>>> On 4/19/2012 7:57 AM, Jussi Piitulainen wrote:
>>>>>>> Peter Olcott writes:
>>>>>>>> On 4/19/2012 1:14 AM, Jussi Piitulainen wrote:
>>>>>>>>> Peter Olcott writes:
>>>>>>>>>> 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
>>>>>>> handwaving, and nobody else knows either.
>>>>>> Since no one knows either way, the Decidability thesis is not >>>>>> refuted.
>>>>>> 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.
>>>>> <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.
>> M( String Input )
>> {
>> if ( Halts( Input, Input ) )
>> Loop Forever;
>> else
>> Exit;
>> }
>> 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.
> Fine. In the accepted proof we start by assuming that Halts() is a
> 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.
This definition ignores the cases where the input is erroneous such that 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.
No it was the implied assumption that invalid input can not occur.
> In other words, there cannot be a
> decider Halts() that will act as specified. Consequently, the
> halting problem cannot be decidable.
The Halting Problem is erroneously specified. There can not possibly be 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
It seems to me that any such proof would fail. Try and form a simple counter-example, and I will show the error.
> 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.
>> 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.
Before I further elaborate these details I need a good (hopefully 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.
> 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 > 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.
So in other words the several requests for me to provide the specification were completely unreasonable requests.
> On 4/20/2012 11:42 AM, Joshua Cranmer wrote:
>> 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
>> 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.
> So in other words the several requests for me to provide the
> specification were completely unreasonable requests.
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.
-- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
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?
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.
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.
> 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."
Or, more specifically, "Instance for which this TM fails as a halting
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.
> 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"
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".
> On 4/20/2012 1:01 PM, Peter Olcott wrote:
>> On 4/20/2012 11:42 AM, Joshua Cranmer wrote:
>>> 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
>>> 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.
>> So in other words the several requests for me to provide the
>> specification were completely unreasonable requests.
> 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.
Sometimes proving that something is true requires omniscience, yet proving that it is false only requires a single valid counter-example.
> 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.
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:
> On 4/20/2012 11:26 AM, Leif Roar Moldskred wrote:
>> 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."
> Or, more specifically, "Instance for which this TM fails as a halting
> 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
It is a property of the particular input when run with that TM.
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.
Jussi Piitulainen wrote:
> 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
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.
> 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 definition?
It meets that specification, since it can never tell you that any TM halts, and it always correctly answers "no".
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
particular input either halts or it does not halt.
> 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
> particular input either halts or it does not halt.
Of course you dishonestly remove the context that proves you are wrong.
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}.
