Proof that Decidability is Always Decidable

[Peter Olcott]

Boolean Halts(String tm, String input)
{
if tm halts on input
// 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
}

// DecidabilityDecider
Boolean Decidable(String tm, String input)
{
if (Halts(tm, input))
return true;
else
return false;
}

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

Decidable(M, M); // Correctly returns False.

Is decidability a non-trivial property of a recursively enumerable set?

[Bryan]

Peter Olcott wrote:
> Boolean Halts(String tm, String input)
> {
>    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
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
Decidable. In fact Decidable is equivalent to Halts.

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

> 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.

--
--Bryan

[George Greene]

On Apr 17, 7:44 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> Boolean Halts(String tm, String input)
> {
>    if tm halts on input
>      // 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
>
> }

The above IS NOT a TM.
There IS NO WAY OF EVALUATING "if tm halts on input",
ESPECIALLY if the tm DOESN'T halt on the input.
If it DOES halt, then there is a way of confirming that (you just run
the TM on the input -- the Universal TM *IS* a TM).
But THIS DOESN'T SAY to just run the tm on the input.
RATHER, THIS takes "if" of a boolean-condition THAT *NO* TM CAN
RELIABLY EVALUATE.
Considered over ALL its possible tm,input pairs, *EVERY* TM fails to
halt-returning-the-correct-answer
(to the question of whether the TM designated by the tm input-string
halts on the input input-string)
IN INFINITELY many cases.

[George Greene]

> Peter Olcott  wrote:
> > Boolean Halts(String tm, String input)
> > {
> >    if tm halts on input

On Apr 17, 11:16 pm, Bryan <bryanjugglercryptograp...@yahoo.com>
wrote:

> How, at this point, could you think that's decidable?

The point is NOT that it's not "decidable".
The point IS that *there IS NO TM* that CAN DO this.
If you are asking to evaluate this condition then you ARE NOT calling
any TM.
Therefore, this code IS NOT CODE FOR any TM.

If he actually wants to CALL A TM THAT RETURNS SOMETHING BOOLEAN (at
least
some of the time), which WOULD make this "if" syntactically legal in
code for a TM
(and might therefore make this a TM), then he needs to go ahead AND
ACTUALLY WRITE A CALL
to the boolean-valued TM *that*he*is*calling* to test whether tm halts
on input.
And if there IS such a TM, then shouldn't THAT TM, RATHER THAN THE
OUTER ONE HERE,
be the one CALLED "Halts()"? Of course, he has already conceded that
no such TM exists,
but in that case, WHY IS HE CALLING *THIS*one, "Halts()"??

> Peter Olcott wrote:
> > Boolean Halts(String tm, String input)

THAT kind of willful perversity simply should not be engaged.
The CORRECT response to this would've occurred EVEN EARLIER, AFTER THE
HEADING.
It would've been something along the lines of:
"DUMBASS, YOU KNOW that is NOT an appropriate name FOR ANY TM,
especially not this one."

[Joshua Cranmer]

On 4/17/2012 6:44 PM, Peter Olcott wrote:
> Boolean Halts(String tm, String input)
> {
> if tm halts on input
> // 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
> }

This reminds me of a math joke I once saw. A professor was at the
blackboard, and wrote down as a proof:
1. <assumption>
2. Some magic happens
3. <result>

The other professor commented "I think you need to explain step 2 a bit
more..."

This joke seems to me to illustrate exactly what you're doing: you have
a nice magic blob called "halts on input". The problem is that the
halting problem is known to be undecidable in the general case, so the
statement "if tm halts on input" renders whatever function includes it
an uncomputable function. Note that the comments imply something
different from what the statements say as well, not that it matters too
much when you've screwed yourself by line 3.

If you want to show that what you want exists, you must either provide a
complete implementation (what you have is most certainly not complete)
or you must nonconstructively show that it must exist, perhaps by saying
that its nonexistence leads to a contradiction.

> Decidable(M, M); // Correctly returns False.

That may be true, but decidable is, by construction, an uncomputable
function, so it matters not one whit.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

[George Greene]

On Apr 17, 11:16 pm, Bryan <bryanjugglercryptograp...@yahoo.com>
wrote:

> Decidable() calls Halts(), so since Halts can fail to halt, so can
> Decidable. In fact Decidable is equivalent to Halts.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Exactly!
But this is because what P.O. MEANS by an "individual input that is
'undecidable' for&by a TM"
IS THAT THE TM FAILS TO DECIDE the disposition of the input, i.e.,
that it fails to halt-with-its-tape-(or state)-containing-the-output-
that-the-TM-(viewed as a function)-returns-as-a-value-corresponding-to-
the-argument-input. In other words, IT LOOPS on this input instead of
returning a value.
So it REALLY IS equivalent to halting checker -- the input is
"decidable" iff it halts.

I kind of hesitated to spell this out because it requires using P.O.'s
MISmeaning of "decidable".
I hope I put enough quotes and qualifiers ("individual" and "for&by")
with it to avoid endorsing it.
It really would've been Better to say NOTHING BEYOND
"that's NOT what 'decidable' MEANS, DUMBASS."

[Joshua Cranmer]

On 4/17/2012 6:44 PM, Peter Olcott wrote:

> Boolean Halts(String tm, String input)
> {
> if tm halts on input
> // 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
> }

Based on your comments (instead of your code), we also get into trouble
very quickly. To be able to define this function, you have an implicit
assumption that it can be written. Namely, you are assuming that
"decidability" [1] of a halting instance is decidable to be able to
write this function. Since you are purporting to prove this fact, note
that your proof will now look like the following:
1. Assume p
2. <some more steps>
3. Therefore, p.

That is not a valid logical proof; it is a circular argument. The only
facts related to p that you can prove if you begin with "assume p" are
either not p (if assume p leads to a contradiction) or "p is independent
of the logical system" (if assume p provably leads to no contradictions
under the additional assumption that the logical system is consistent).
Indeed, you deign to go further and say:
4. System implies not p.
5. Therefore, system is wrong.

I hope that you able to appreciate the magnitude of your error.

[1] When in Rome... despite the fact this term is extremely obfuscatory.

[Bryan]

Joshua Cranmer wrote:
> This reminds me of a math joke I once saw. A professor was at the
> blackboard, and wrote down as a proof:
> 1. <assumption>
> 2. Some magic happens
> 3. <result>
>
> The other professor commented "I think you need to explain step 2 a bit
> more..."

By Sidney Harris:
http://www.sciencecartoonsplus.com/pages/gallery.php

-Bryan

[Peter Olcott]

On 4/17/2012 10:16 PM, 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
If it is not either (b) or (c) then it goes to here.
This is rte partial function that Patricia wrote about yesterday.

>
>> // 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
> evaluate the condition of the 'if'.

No this is false. Halts() always halts. It only examines the input TM's
specification, it does not run it.

>
>> }
>
>> // 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
> Decidable. In fact Decidable is equivalent to Halts.

This assumption is false.

>
>> M( String Input )
>> {
>> if ( Decidable( Input, Input ) )
>> Loop Forever;
>> else
>> Exit;
>>
>> }
>> 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.

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.

>
> --
> --Bryan

[Peter Olcott]

On 4/17/2012 11:26 PM, Joshua Cranmer wrote:
> On 4/17/2012 6:44 PM, Peter Olcott wrote:
>> Boolean Halts(String tm, String input)
>> {
>> if tm halts on input
>> // 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
>> }
>
> This reminds me of a math joke I once saw. A professor was at the
> blackboard, and wrote down as a proof:
> 1. <assumption>
> 2. Some magic happens
> 3. <result>
>
> The other professor commented "I think you need to explain step 2 a
> bit more..."

This is a partial function on the subset of the input that is decidable
and does halt.
>

> This joke seems to me to illustrate exactly what you're doing: you
> have a nice magic blob called "halts on input". The problem is that
> the halting problem is known to be undecidable in the general case, so
> the statement "if tm halts on input" renders whatever function
> includes it an uncomputable function. Note that the comments imply
> something different from what the statements say as well, not that it
> matters too much when you've screwed yourself by line 3.
>
> If you want to show that what you want exists, you must either provide
> a complete implementation (what you have is most certainly not
> complete) or you must nonconstructively show that it must exist,
> perhaps by saying that its nonexistence leads to a contradiction.
>
>> Decidable(M, M); // Correctly returns False.
>
> That may be true, but decidable is, by construction, an uncomputable
> function, so it matters not one whit.
>

A TM that reports whether or not another TM halts has only three
possible cases:
(a) Halts and is decidable.
(b) Fails to halt and is decidable.
(c) Is not decidable.
This TM reports (a) as true, and (b) and (c) as false.
Its input has no other possible category besides the above three.

[Peter Olcott]

On 4/17/2012 10:16 PM, Bryan wrote:

I don't see how you could say this.
My function specifies that it either returns true or returns false,
neither of these is a loop. Do you assume that this function simulates
its input? That would be a false assumption.

[George Greene]

On Apr 18, 12:26 am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> This reminds me of a math joke I once saw. A professor was at the
> blackboard, and wrote down as a proof:
> 1. <assumption>
> 2. Some magic happens
> 3. <result>
>
> The other professor commented "I think you need to explain step 2 a bit
> more..."
>
> This joke seems to me to illustrate exactly what you're doing: you have
> a nice magic blob called "halts on input". The problem is that the
> halting problem is known to be undecidable in the general case, so the
> statement "if tm halts on input" renders whatever function includes it
> an uncomputable function.

The above is logically equivalent to "Dumbass."
It will (unfortunately) NOT be equivalent in EFFECT.

He has ALREADY CONCEDED that he KNOWS that there is no TM
"that always halt and always gives the correct answer".
I repeat, if he knows this, then the FIRST objection to EVERYthing HAS
to be,
"So why are you calling this program Halts(,)?" Every attempt to
tolerate
bad linguistic practices just misleads him into thinking he is doing
something acceptable.

You and Bryan need to be very aware that we have been down this road
before with Ben Bacarisse and Patricia Shanahan and Darryl McCullough
and
several other commentators. There really is a sense in which some
people
need to get the hell out of MY way. Not necessarily you, though. You
are doing fine.
If YOURS doesn't work, then maybe MORE of us need to give up.

[George Greene]

On Apr 18, 6:15 am, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> A TM that reports whether or not another TM halts has only three
> possible cases:

BULLSHIT! It has only TWO possible cases!
EITHER IT HALTS OR IT DOESN'T!
Any other outcome IS WRONG, and if the TM EVER does ANYthing else
(e.g. FAILS to halt), then it IS NOT "A TM that reports whether or not
another TM halts".
In point of fact, in the general case, THERE IS NO TM that always
correctly reports
whether a TM (it does NOT NEED to be ANOTHER tm; it COULD be THIS
one!)
halts on arbitrary input.

> (a) Halts and is decidable.

IT *IS NOT POSSIBLE* for an INDIVIDUAL tm to "BE [un]decidable",
DUMBASS!
THAT IS *NOT* WHAT "decidable" MEANS!!!! ANY AND EVERY *individual*
question
is decidable! If the Question corresponding to a TM (as a whole) is
decidable, then that
just means that the TM ALWAYS (always) halts!

> (b) Fails to halt and is decidable.
> (c) Is not decidable.
> This TM reports (a) as true, and (b) and (c) as false.
> Its input has no other possible category besides the above three.

IT DOESN'T EVEN HAVE THESE THREE, DUMBASS.
THERE IS NO SUCH THING as undecidablity for INDIVIDUAL input!
What you ACTUALLY MEAN is IT LOOPS on the input (As a result of which
the TM fails to decide on a return-value for the input-argument).

[George Greene]

On Apr 18, 1:03 am, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> On 4/17/2012 6:44 PM, Peter Olcott wrote:
>
> > Boolean Halts(String tm, String input)
> > {
> > if tm halts on input
> > // 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
> > }
>
> Based on your comments (instead of your code), we also get into trouble
> very quickly. To be able to define this function, you have an implicit
> assumption that it can be written. Namely, you are assuming that
> "decidability" [1] of a halting instance is decidable to be able to
> write this function.

But in [1], HE DOESN'T EVEN CALL any function! He leaves it in
NATURAL LANGUAGE!
That is just a failure of programming. This is supposed to be pseudo-
CODE, in a pseudo-PROGRAMMING-language, NOT NATURAL language!

He also can't be calling this "Halts()",
and he can't be using "decidable" and "undecidable" for INDIVIDUAL
inputs.
IT IS INFINITARY *PROBLEMS* (like the halting problem) THAT CAN be
decidable or un-!
FINITE questions are ALL TRIVIALLY decidable!

[Leif Roar Moldskred]

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?

It doesn't matter how many times you wrap a badly named function
around it: it's the halting problem all the way down.

--
Leif Roar Moldskred

[Daryl McCullough]

On Tuesday, April 17, 2012 7:44:14 PM UTC-4, Peter Olcott wrote:
> Boolean Halts(String tm, String input)
> {
> if tm halts on input
> // 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
> }

You need to prove that there is such a program Halts(tm,input).
Why do you think that such a program exists?

[Charlie-Boo]

On Apr 18, 12:05 am, George Greene <gree...@email.unc.edu> wrote:
> On Apr 17, 7:44 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
>
> > Boolean Halts(String tm, String input)
> > {
> >    if tm halts on input
> >      // 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
>
> > }
>
> The above IS NOT a TM.

Right. It is a set expressed in a program that should only represent
sets. Expressing includes sets that cannot be represented and so is
not an executable language. Godel showed us that when he proved that
we can express "It is not provable on its number." but we cannot
represent it. There is no wff that is provable iff its free variable
is replaced by the number of a wff that is not provable when its free
variable is replace by its number.

C-B

[Joshua Cranmer]

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.

[Patricia Shanahan]

On 4/18/2012 7: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.
>

This is, I think, the major problem in PO's thinking. He deeply believes
that any algorithm he wants to exist must exist.

That means he can skip the work the rest of us would have to do to prove
a function is computable, such as to writing out an algorithm, proving
it always terminates, and proving that when it terminates its result
matches the function.

Patricia

[Daryl McCullough]

On Wednesday, April 18, 2012 10:57:50 AM UTC-4, Patricia Shanahan wrote:
> This is, I think, the major problem in PO's thinking.
> He deeply believes that any algorithm he wants to
> exist must exist.

I think that it's a little subtler than that. What he
seems to think (and I've seen other posters with similar
arguments against Cantor's theorem and Godel's theorem,
etc.) that if he can tweak things so that a proof of
*nonexistence* of something is blocked, then that allows
for its existence.

For example, some people respond to Cantor's
theorem or Godel's theorem by wanting to *weaken*
the axioms sufficiently that the proofs don't go
through. That, of course, doesn't accomplish
anything by itself. A system doesn't become more
complete through weakening it.

[Ralph Hartley]

On 04/17/2012 07:44 PM, Peter Olcott wrote:
> Boolean Halts(String tm, String input)
> {
> if tm halts on input
> // 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
> }

> // DecidabilityDecider
> Boolean Decidable(String tm, String input)
> {
> if (Halts(tm, input))
> return true;
> else
> return false;
> }
>
> M( String Input )
> {
> if ( Decidable( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> Decidable(M, M); // Correctly returns False.

But

RunForever(String input) {
for (int x=0; true; x++); // obvious infinite loop
}

Decidable(RunForever,anything);

Also returns False, if Halts() behaves as described.

Is that correct?

Are *all* non-halting TMs "undecidable"?

Ralph Hartley

[Peter Olcott]

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.

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.

[Peter Olcott]

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.

[Peter Olcott]

On 4/18/2012 9:57 AM, Patricia Shanahan wrote:
> On 4/18/2012 7: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.
>>
>
> This is, I think, the major problem in PO's thinking. He deeply believes
> that any algorithm he wants to exist must exist.

There are only thee possibilities for a TM:
(1) Halting
(2) Not Halting
(3) Undecidable

If it only cares about (1) and can thus roll (2) and (3) together, and
it does not determine (1) by simulating its input, then it seems to
logically follow that it could divide any input into (1) or {2, 3} in
finite time.

[Peter Olcott]

A TM computation can only do one of three things:
(1) Halt in its accept state.
(2) Halt in its reject state.
(3) Loop, which means to never decide, either true or false.

[Daryl McCullough]

On Wednesday, April 18, 2012 6:18:26 PM UTC-4, Peter Olcott wrote:
> 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.

Okay, suppose you have a machine that is searching for
the sequence "9999999999999999999999999999999999" in the
decimal expansion of pi. Will that halt, or not?

--
Daryl McCullough
Ithaca, NY

[Daryl McCullough]

On Wednesday, April 18, 2012 6:22:25 PM UTC-4, Peter Olcott wrote:

> There are only thee possibilities for a TM:
> (1) Halting
> (2) Not Halting
> (3) Undecidable

Actually, there are only two possibilities:
either the Turing Machine halts on a given
input, or it doesn't.

> If it only cares about (1) and can thus roll
> (2) and (3) together, and it does not determine
> (1) by simulating its input

Then how does it figure out whether (1) is the
case? The alternative besides simulation is to
look for a mathematical proof that the Turing
Machine does or doesn't halt. What if that search
itself fails to halt?

[Peter Olcott]

It will halt using an greater understanding of PI than is currently
available, thus the brute force approach that would take an infinite
amount of time if this sequence does not occur, is not logically entailed.

Allowing for an unlimited amount of technological advances, this method
that determines whether or not this sequence occurs in PI could
eventually (within finite time) figure out for itself how to determine
this answer.

This TM could start with the sum total of every detail of all knowledge
that is currently available, and have the logical reasoning ability
greater than any individual that has ever existed in any subject.
Furthermore it could have one ability to no human has, it could avoid
ever making the same mistake twice.

A machine such as this could answer your question within finite time.

[Joshua Cranmer]

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.

I will also take the time to point out that failing to find a
counterexample does not make a proof. And before you retort your tired
counterclaim about the Church-Turing Thesis, let me point out that it is
not a theorem but a fact which is considered to be evidentially true by
the fact that several different computation models have been shown to be
more no more powerful than a Turing machine, as well as the fact that a
Turing machine can emulate pretty much all the mathematics we know with
the exception of that which involves infinite sets (which our physical
knowledge implies can't be done anyways, since our universe is, as far
as we can tell, merely finite). About the only process that can't be
emulated by a Turing machine given current knowledge [1] is basically
consciousness, or, more specifically, intuition and creativity. Finding
a counterexample to the Church-Turing Thesis pretty much necessitates
discovering a radical flaw in our current models of physics, so it can
be considered "proven" only in the same sense that the Standard Model of
physics or the Laws of Thermodynamics are considered "proven."

Now, if you still want a counterexample badly, I will point out that
there exists a large set of problems that are undecidable yet
recognizable. While I can't say if you'd dismiss the recognizers as not
being "decidable", given the closest definitions I have seen you give,
they are not. Today's example is *thumbs through Wikipedia* the Turing
machine that decides whether or not the polynomial equation (using
integer coefficients) described by its input has a solution in the integers.

[1] Okay, quantum mechanics can "do" things exponentially faster, but
it's still possible with a powerful enough Turing machine.

[Peter Olcott]

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.

[Joshua Cranmer]

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. In the second sense, it has
a circular definition, so no conclusion can be reached.

[Peter Olcott]

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.

> 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.

[Peter Olcott]

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.

[Leif Roar Moldskred]

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

[Daryl McCullough]

On Wednesday, April 18, 2012 7:05:08 PM UTC-4, Peter Olcott wrote:
> On 4/18/2012 5:31 PM, Daryl McCullough wrote:

> > Okay, suppose you have a machine that is searching for
> > the sequence "9999999999999999999999999999999999" in the
> > decimal expansion of pi. Will that halt, or not?
>

> It will halt using an greater understanding of PI than is currently
> available, thus the brute force approach that would take an infinite
> amount of time if this sequence does not occur, is not logically entailed.

I'm asking how, today, you would write a Turing machine that can
answer that question. Your answer seems to be that you can't, but
maybe someday.

> This TM could start with the sum total of every detail of all knowledge
> that is currently available, and have the logical reasoning ability
> greater than any individual that has ever existed in any subject.
> Furthermore it could have one ability to no human has, it could avoid
> ever making the same mistake twice.

> A machine such as this could answer your question within finite time.

*WHY* do you believe that?

So what you're claiming, based on nothing other than a guess
on your part, is that at some future date, there will be a
mathematical theory T that will allow all questions about
halting of programs to be answered. There are two responses
to this claim:

(1) You haven't given any reason to believe its true.
(2) It's provably false.

[Daryl McCullough]

On Tuesday, April 17, 2012 7:44:14 PM UTC-4, Peter Olcott wrote:
> Boolean Halts(String tm, String input)
> {
> if tm halts on input
> // 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
> }
>
> // DecidabilityDecider
> Boolean Decidable(String tm, String input)
> {
> if (Halts(tm, input))
> return true;
> else
> return false;
> }
>
> M( String Input )
> {
> if ( Decidable( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> Decidable(M, M); // Correctly returns False.
>

> Is decidability a non-trivial property of a recursively enumerable set?

Note, you haven't actually programmed a machine that
does what you claim it does. You're guessing that
there might be such a machine. So what you're really
saying---what your "Disproof of Rice's Theorem" amounts
to (I know that's another thread, but it's the same idea)
is this:

Rice's Theorem says that such and such is impossible.
So if I had a such and such, that would prove that
Rice's Theorem is wrong.

It's as if someone told you that there is no such thing
as a perpetual motion machine, and you replied by saying:
Well, if I had a perpetual motion machine, I could prove
you wrong.

If you want to *prove* something, you can't start by
*imagining* that you have something. You have to *prove*
that such a thing exists, not assume it. You can't prove
that there are unicorns by assuming that you have a pet
unicorn in your back yard.

[Bryan]

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

[Owen Jacobson]

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?)

[George Greene]

On Apr 18, 6:18 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> 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.

Well,yes, in this case, the thing that is attempting to be a halt
decider
(NOT "the Halt decider", SINCE NO SUCH THING EXISTS) WILL NOT HALT,
so it will NOT decide, so it will NOT be a decider -- you can't always
get what you want.

> 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.

No, it can't. You are reversing cause and effect here.
Just because simulating your input can cause you not to halt
does NOT mean that whenever you don't halt, you must have been
simulating your input. There are plenty of other reasons why you
might fail to halt.

> > It doesn't matter how many times you wrap a badly named function
> > around it: it's the halting problem all the way down.

Indeed, and the first bad name was "Halts()". The second one was
"Decidable()",
which, thank Leif & Josh & everybody for pointing out, IS ALSO
"Halts()", since
you keep (wrongly) using "undecidable", about an individual input and
by a TM,
to mean that the TM fails to decide (i.e., HALT) on an output for the
input.

[George Greene]

On Apr 18, 6:22 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> There are only thee possibilities for a TM:
> (1) Halting
> (2) Not Halting
> (3) Undecidable

DUMBASS: (3) *IS*NOT* a "possiblity" for a TM!
AN INDIVIDUAL TM *CANNOT BE* "undecidable"!
THAT IS *NOT* what "undecidable" MEANS!

[George Greene]

On Apr 18, 7:05 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> This TM could start with the sum total of every detail of all knowledge
> that is currently available, and have the logical reasoning ability
> greater than any individual that has ever existed in any subject.

Humans are finite. TMs are not (their programs are but their tapes
are not).
There are plenty of TMs that ALREADY have "reasoning powers" beyond
those
of any human for that reason alone. Despite that, THERE ARE STILL
limits.
None of them is smart enough to violate Rice's Theorem, for example.
None of them is smart enough to decide, FOR ANY tm (including itself),
whether it does or doesn't accept-halt on the empty string.

[George Greene]

On Apr 18, 11:01 pm, Daryl McCullough <stevendaryl3...@yahoo.com>
wrote:

> So what you're claiming, based on nothing other than a guess
> on your part, is that at some future date, there will be a
> mathematical theory T that will allow all questions about
> halting of programs to be answered. There are two responses
> to this claim:
>
> (1) You haven't given any reason to believe its true.
> (2) It's provably false.

Darryl, please, (2) IS NOT helping. He's SEEN the proof.
The proof produces ONE contradictory case. He thinks he can
just pre-screen it and move on; you know, kind of like the diagonal-
deniers think they can just add the missing anti-diagonal onto the
list (at the front, usually).

[George Greene]

On Apr 18, 8:33 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> "Decidability" has been completely specified as of the first posting of
> this thread, please look at this again.

IDIOT, YOU SPECIFIED IT *AS* *HALTS()*!! You specified it as
> Boolean Decidable(tm,input)

> if (Halts(tm, input))
> return true;
> else
> return false;

IDIOT, THERE IS A MUCH SHORTER VERSION OF THIS PROGRAM, NAMELY,
return(Halts(tm, input)).

The "Decidable" that you have defined SIMPLY *IS* Halts() !
And since Halts() DOES NOT EXIST (as a TM), THIS "Decidable" DOESN'T
EITHER!

[George Greene]

On Apr 18, 8:26 pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> Note that your function is not sufficiently well-defined, as you are
> still incredibly vague on what "decidability" is

DAMMIT, he IS NOT *vague*!!! He's *WRONG*!!
YOU know the difference -- so ACT LIKE YOU KNOW!!

Just for the record, he very explicitly thought for a long time
that an individual input was undecidable FOR AND BY A SPECIFIC
TM (the correct notion of undecidability is NOT relevant to a specific
TM,
but rather to a specific problem; the question is whether there does
or
doesn't exist a TM that solves or "decides" all infinity of the
littler questions
"inside" the problem)
IF AND ONLY IF THE TM *FAILED* to decide upon an answer for it.
Of course, since the ONLY way the TM so fails is BY FAILING TO HALT
(IF it ever halts, then the answer IS whatever the tape or the state
then SAYS it is),
HIS version of undecidability IS EQUIVALENT to not halting. His
introduction of
halts
doesn't halt
is undecidable (as 3 dispositions of the same individual input)
IS NEW.
The newer version is becomING more unclear than the old one, but
INSTEAD OF ALL THOSE LONG PARAGRAPHS, just pin him down in ONE
sentence: WHAT KIND of NOUN does the ADJECTIVE "undecidable" apply
to??
WHAT *KINDS* of things CAN BE "undecidable"??
If he would ever figure THAT out, you MIGHT get somewhere!!

[Joshua Cranmer]

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...

[Jussi Piitulainen]

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.

> 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?

[Peter Olcott]

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

> 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]

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
values of every specific instance of TM/input pairs.

[Peter Olcott]

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:
The return value of halts == decidable

[Leif Roar Moldskred]

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?

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]

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
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]

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:
(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]

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.

[Jussi Piitulainen]

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.

> 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.

Not allowing for unlimited resources, that dream may destroy itself.

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?

So your answer is that your "Turing machines" advance without limit,
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.

[Aatu Koskensilta]

Daryl McCullough <stevend...@yahoo.com> writes:

> If you want to *prove* something, you can't start by *imagining* that
> you have something. You have to *prove* that such a thing exists, not
> assume it. You can't prove that there are unicorns by assuming that
> you have a pet unicorn in your back yard.

Just to muddy the waters here, let me observe that the proof of Löb's
theorem (and the Santa Claus paradox in general) in effect amounts to
just imagining you have what you would like to have.

--
Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen."
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

[Daryl McCullough]

On Thursday, April 19, 2012 6:08:41 AM UTC-4, Peter Olcott wrote:

> 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.

For your purposes, it's not good enough to have a
sequence of Turing machines *approaching* omniscience.
You are claiming the existence of a *SINGLE* Turing
machine that can correctly answer all halting
problems.

If you're just claiming that for any halting
problem there exists (or will exist, someday)
a computer program that correctly solves that
problem, that's not controversial. It's provable,
as a matter of fact.

If TM_1 is the best halting decider we have today,
it's likely there will be a better decider TM_2 in 10
years, and an even better one TM_3 10 years after
that. What you're claiming is that there will be
a day in which we are *done* making improvements,
and we'll have the best possible halting decider.

What reason is there for believing that? None.

It's one thing to have confidence in the forward
march of progress, things keep getting better and
better. It's something quite different to believe
that we will ever achieve perfection. (This is beside
the fact that there is a proof that there is no
perfect halt decider.)

[Peter Olcott]

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.

[Peter Olcott]

On 4/19/2012 9:48 AM, Daryl McCullough wrote:
> On Thursday, April 19, 2012 6:08:41 AM UTC-4, Peter Olcott wrote:
>
>> 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.
> For your purposes, it's not good enough to have a
> sequence of Turing machines *approaching* omniscience.
> You are claiming the existence of a *SINGLE* Turing
> machine that can correctly answer all halting
> problems.

No that has never been the case. In this thread I am talking about
Decidability. In this case the DecidabilityDecider reports true in all
the cases where the input TM halts on its input.

> If you're just claiming that for any halting
> problem there exists (or will exist, someday)
> a computer program that correctly solves that
> problem, that's not controversial. It's provable,
> as a matter of fact.

So far I have only seen two kinds of Halting Problems:
(1) Problems that depend upon information that is currently unknown. In
this case as soon as this info is available, this instance of the
Halting Problem is solved.

(2) Problems that are based on semantically ill-formed questions. I can
now precisely specify this set. I will do that in another thread later
on. In this case one merely screen out the erroneous input, leaving
every other case of this type of HP decidable.

[Bryan]

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.

> 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]

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).

[Daryl McCullough]

On Thursday, April 19, 2012 4:38:27 PM UTC-4, Peter Olcott wrote:
> On 4/19/2012 9:48 AM, Daryl McCullough wrote:

> > For your purposes, it's not good enough to have a
> > sequence of Turing machines *approaching*
> > omniscience. You are claiming the existence
> > of a *SINGLE* Turing machine that can
> > correctly answer all halting problems.
>
> No that has never been the case.
> In this thread I am talking about
> Decidability. In this case the
> DecidabilityDecider reports true in all
> the cases where the input TM halts on its input.

You're claiming that that there is (or will be)
a DecidabilityDecider that works for all inputs.
So you're not just assuming that we will continually
improve, but that it is possible to get a perfect
such machine (although it's not clear exactly what
a decidability decider is supposed to do).

> > If you're just claiming that for any halting
> > problem there exists (or will exist, someday)
> > a computer program that correctly solves that
> > problem, that's not controversial. It's provable,
> > as a matter of fact.
> So far I have only seen two kinds of Halting Problems:
> (1) Problems that depend upon information that
> is currently unknown.

You need to be clearer about your terminology.
The halting problem is this: Does there exist
a machine H(x,y) that returns true if machine
x halts on input y, and returns false otherwise?

There is only one halting problem, in this sense.

The other meaning that you might be giving to
"a halting problem" is a specific pair (x,y):
Does x halt on input y?

Every such question is a matter of
information that may be currently unknown.

There is no such thing as an unanswerable
halting question of this type. Every single
one can be answered. But the issue is whether
there is a "universal" halt decider that can
answer all such questions.

> In this case as soon as this info is available,
> this instance of the Halting Problem is solved.
>
> (2) Problems that are based on semantically
> ill-formed questions.

Even we limit ourselves to semantically well-formed
questions, there is no computer program that can
answer all of them.

Consider equations of the form such as:

27 x^3 -98 y z + 105 w^5 - 4002 = 0

For each such equation, there is a corresponding
question: Does the equation have a solution, where
all the variables are replaced by integers?

There is no computer program that can answer all
such questions correctly. Every such question is
semantically well-formed.

[George Greene]

On Apr 19, 4:38 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> So far I have only seen two kinds of Halting Problems:
> (1) Problems that depend upon information that is currently unknown. In
> this case as soon as this info is available, this instance of the
> Halting Problem is solved.

There are a lot of problems about TMs where the answer is currently
unknown --
for example, the problem that Darryl gave you about the lengths of
strings of
consecutive 9's in the decimal expansion of Pi -- but not very many
of them are halting PROBLEMS. Just because we don't know whether a
given
TM halts OR NOT does NOT mean there is a PROBLEM! It does NOT mean
that ANY INDIVIDUAL thing is semantically ill-formed or undecidable!
It JUST
means we DON'T KNOW yet! IN EITHER case, the TM in question EITHER
HALTS
OR IT DOESN'T, and just because we don't know WHICH, does NOT mean we
have
a PROBLEM!
In the case of the Halting problem, we KNOW that there is NO TM that
always
gets it right. That is sort of what makes it a PROBLEM -- you CAN'T
get it
right, with ANY TM, no MATTER HOW smart the TM is, because,
ultimately,
to solve a halting problem, you have to be "smarter than" the machine
whose halting
you are trying to analyze, and you CAN'T be smarter than YOURSELF --
so you will
always either loop or otherwise fail on SOME of the questions about
YOURSELF
(if you are an analyzer TM), when faced with a PROBLEM like Halting.

> (2) Problems that are based on semantically ill-formed questions. I can
> now precisely specify this set.

If you can, it will not be enough. It will turn out that there will
STILL be infinitely
many OTHER cases, BEYOND these that you can recognize, that STILL
force your candidate-analyzer (which you STILL may NOT NAME
"Halts(,)" )
to loop or get it wrong.

[George Greene]

On Apr 19, 4:38 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:

> No that has never been the case. In this thread I am talking about
> Decidability. In this case the DecidabilityDecider reports true in all
> the cases where the input TM halts on its input.

If that is all you are trying to do then you DON'T have to INVENT
anything NEW! THE UNIVERSAL TM ALREADY DOES THAT.
Except in the case where the TM halts returning false on its input.
But that is an easy case to recognize-and-recode.
"Decidability" isn't. What you ACTUALLY MEAN by "decidable" here
is "it halts on its input", which means YOUR DecidabilityDecider IS
JUST
"Halts(,)" ALL OVER AGAIN!

[George Greene]

On Apr 19, 4:38 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:

> In this case one merely screen out the erroneous input, leaving
> every other case of this type of HP decidable.

The INPUT is NEVER erroneous.
if the input specifies a TM THEN IT IS CORRECT.
The Halting question is semantically WELL-formed for ALL TMs and ALL
possible
input strings and IT HAS a WELL-defined answer in ALL cases. The fact
that
this or that TM fails to give it is basically the same kind of fact as
the fact that
no number is big enough to be bigger than every number, and no set is
big enough
to contain all its own subsets.

[George Greene]

On Apr 19, 6:08 pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> 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).

That is the FIRST interpretation.
The original such withholding was his withholding OF ANY ACTUAL CODE
for
PolAAAAhatm(,), for which he withheld, first and foremost, THE NAME.
Instead of giving his pseud-TM a name that might actually give
somebody
a clue as to what it means or does, he *calls* this (attempted)TM
"Halts(,)", which as he himself already conceded,
actually CANNOT be the CORRECT name OF ANY tm, SINCE EVERY
tm(m,i) gets the question "does m halt on i?" WRONG an INFINITE number
of times!

[Rick Decker]

<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

[Peter Olcott]

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
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]

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
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]

That reasoning seems correct to me.

[Bryan]

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?
>

> >>       // 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
> > 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
> > Decidable. In fact Decidable is equivalent to Halts.
>
> >> M( String Input )
> >> {
> >> if ( Decidable( Input, Input ) )
> >>     Loop Forever;
> >> else
> >>     Exit;
>
> >> }
> >> 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.
> 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]

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.

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]

Wouldn't specifying this such that it works for any arbitrary TM take
hundreds of millions of state transitions?

[Daryl McCullough]

On Friday, April 20, 2012 6:15:53 AM UTC-4, Peter Olcott wrote:
> 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?

It's worse than that--no finite number is good enough.

[Daryl McCullough]

On Thursday, April 19, 2012 10:48:15 AM UTC-4, Aatu Koskensilta wrote:
> Daryl McCullough <stevend...@yahoo.com> writes:
>
> > If you want to *prove* something, you can't start by *imagining* that
> > you have something. You have to *prove* that such a thing exists, not
> > assume it. You can't prove that there are unicorns by assuming that
> > you have a pet unicorn in your back yard.
>
> Just to muddy the waters here, let me observe that the proof of Löb's
> theorem (and the Santa Claus paradox in general) in effect amounts to
> just imagining you have what you would like to have.

Yeah. Even though in a sense Lob's theorem is equivalent to Godel's
theorem, it seems weirder.

On a different topid: You're never on Facebook! You must actually
have a life.

--
Daryl McCullough
Ithaca, NY

[Peter Olcott]

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?

> 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.

[Peter Olcott]

That is not true if the undecidable input can be ignored.
In these instances it simply reports false.

[Daryl McCullough]

Well, first your machine would have to figure out whether the
input is "undecidable" in your sense, and that can take an infinite
amount of time.

As I said in another post, we can limit ourselves to completely
unproblematic instances of the halting problem--questions of the
form:

Will the search for a integer-valued solutions to a given
arithmetic equation ever terminate?

If you have an arithmetic equation such as

12 x_1^3 - 34 x_1 * x_2 + 87 x_3^2 - 6 x_1 * x_2 * x_3 - 49 = 0

Then you can ask the question: Is there an integer-valued solution?
For example, the equation
x^2 + 2x + y^2 + 2y - z^2 + 2z + 1 = 0

has the solution: x=2, y=3, z=4

The equation x^2 - 2 = 0 has no solution.

So let Solvable(Q) be the program that given an arithmetic
equation Q, searches for a solution--an assignment to the
variables that makes the equation true.

There is no computer program that can correctly answer all
possible questions of the form "Does Solvable halt on input Q?"

None of those questions are "ill-formed" or "undecidable".

[Peter Olcott]

It does not seem that you have shown that.

[Jussi Piitulainen]

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).

[Daryl McCullough]

Of course *I* haven't. It was a very difficult theorem, finally
proved in the 60s. It's the MRDP theorem, named after the logicians
that proved it: Matiyasevich, Robinson, Davis and Putnam.

The gist of the proof amounts to showing that for any pair TM,x
where TM is a Turing machine and x is an input, there is a
corresponding arithmetic equation Q such that knowing whether
TM halts on input x is equivalent to knowing whether Q has any
solutions. So every question about halting can be converted into
a question of pure arithmetic. No question of pure arithmetic
can be "ill-formed".

[Daryl McCullough]

On Friday, April 20, 2012 7:41:21 AM UTC-4, Daryl McCullough wrote:

> The gist of the proof amounts to showing that for any pair TM,x
> where TM is a Turing machine and x is an input, there is a
> corresponding arithmetic equation Q such that knowing whether
> TM halts on input x is equivalent to knowing whether Q has any
> solutions. So every question about halting can be converted into
> a question of pure arithmetic. No question of pure arithmetic
> can be "ill-formed".

Actually, it had been known for years that halting can be formalized
in arithmetic, but the MRDP theorem shows that it can be formalized
in a really tiny part of arithmetic: the question of which Diophantine
equations have solutions.

[Jussi Piitulainen]

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.

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.

I knew you would.

[Patricia Shanahan]

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.

PO has previously rejected this approach.

Patricia

[Rick Decker]

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.


Regards,

Rick

[Jussi Piitulainen]

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.

[Frederick Williams]

Daryl McCullough wrote:

> For example, some people respond to Cantor's
> theorem or Godel's theorem by wanting to *weaken*
> the axioms sufficiently that the proofs don't go
> through. That, of course, doesn't accomplish
> anything by itself. A system doesn't become more
> complete through weakening it.

You refer, I suppose, to an incompleteness theorem. The name might be
attached to either of these (and maybe other things besides, I don't
know):

(i) For some closed formula phi, neither |- phi nor |- ~phi.

(ii) For some formula phi,
it is not the case that if |= phi then |- phi.

One way of weakening axioms is by removing certain symbols from the
language so that some things cannot even be stated (axiomatically, or
otherwise. Without negation (primitive or definable) (i) cannot be
stated.

|= phi means that all models (of the appropriate signature) satisfy
phi. Suppose we removed a non-logical symbol from the language, then
the phi's of which |= phi is true will be different. Possibly it will
only be true of those for which |- phi is true also.

I don't know, I'm just thinking aloud.

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[Joshua Cranmer]

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.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

[Frederick Williams]

Frederick Williams wrote:
>
> Daryl McCullough wrote:
>
> > For example, some people respond to Cantor's
> > theorem or Godel's theorem by wanting to *weaken*
> > the axioms sufficiently that the proofs don't go
> > through. That, of course, doesn't accomplish
> > anything by itself. A system doesn't become more
> > complete through weakening it.
>
> You refer, I suppose, to an incompleteness theorem. The name might be
> attached to either of these (and maybe other things besides, I don't
> know):
>
> (i) For some closed formula phi, neither |- phi nor |- ~phi.
>
> (ii) For some formula phi,
> it is not the case that if |= phi then |- phi.
>
> One way of weakening axioms is by removing certain symbols from the
> language so that some things cannot even be stated (axiomatically, or
> otherwise. Without negation (primitive or definable) (i) cannot be
> stated.
>
> |= phi means that all models (of the appropriate signature) satisfy
> phi. Suppose we removed a non-logical symbol from the language, then
> the phi's of which |= phi is true will be different. Possibly it will
> only be true of those for which |- phi is true also.

Argh! The line above should be 'only be true of those phi for which |-
phi is true also.'

Isn't it strange that errors don't leap out at you when you type, nor
when you read before posting, but the second you read your own post they
do?

[Patricia Shanahan]

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
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.

Patricia

[Peter Olcott]

Ill-Formed Question in Arithmetic:
X = -5^0.5 + 9/0
What is the value of X?

I suspect that the extremely difficult proof has a subtle undetectable
error when is formed its mathematical mapping from TM to arithmetic.

[Joshua Cranmer]

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
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. :-)

[Peter Olcott]

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]

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]

Since both yes and no are wrong answers to the question that you
snipped, there is no other correct answer that I can provide.

[Peter Olcott]

[Peter Olcott]

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.

[Daryl McCullough]

Peter Olcott wrote:

> Ill-Formed Question in Arithmetic:
> X = -5^0.5 + 9/0
> What is the value of X?

The questions that I was talking about are
questions of the form: Is there a integer value
of X making the equation true?

Every question of that form is well-formed and
has an answer, yes or no. There are no counter-examples.

[Peter Olcott]

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.

[Peter Olcott]

So in other words the several requests for me to provide the
specification were completely unreasonable requests.

[Daryl McCullough]

Peter Olcott wrote:

> Before I further elaborate these details
> I need a good (hopefully
> conventional) term that
> can be used to describe single instance
> undecidability.

Relative to a specification S of what a
program M is supposed to do, we can say
that an input x is in the domain of M
if M(x) halts on x and returns the correct
value. Otherwise, x is outside the domain
of M.