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?

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

Except that not halting can leave you running forever in attempt to
evaluate the condition of the 'if'.

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

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

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

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

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

On 4/17/2012 6:44 PM, Peter Olcott 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. 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.

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

On Apr 17, 11:16 pm, Bryan <bryanjugglercryptograp...@yahoo.com>
wrote:
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                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."

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

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.

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

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

-Bryan

On 4/17/2012 10:16 PM, Bryan 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.
This is rte partial function that Patricia wrote about yesterday.
No this is false. Halts() always halts. It only examines the input TM's
specification, it does not run it.
This assumption is false.
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.

On 4/17/2012 11:26 PM, Joshua Cranmer wrote:

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

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.

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.

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?

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

On 4/18/2012 5:15 AM, Peter Olcott wrote:

You have not established that such a function would be computable. See
my other response to your message.

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

On 4/18/2012 7:07 AM, Joshua Cranmer wrote:

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

On 04/17/2012 07:44 PM, Peter Olcott wrote:

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

On 4/18/2012 7:45 AM, Leif Roar Moldskred wrote:
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.

On 4/18/2012 9:07 AM, Joshua Cranmer wrote:

Try and show a valid counter-example where it is not computable.

On 4/18/2012 9:57 AM, Patricia Shanahan wrote:

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.

On 4/18/2012 11:35 AM, Ralph Hartley wrote:

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.

On 4/18/2012 5:31 PM, Daryl McCullough wrote:

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.

On 4/18/2012 5:19 PM, Peter Olcott wrote:

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.

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

On 4/18/2012 7:26 PM, Joshua Cranmer wrote:

"Decidability" has been completely specified as of the first posting of
this thread, please look at this again.

On 4/18/2012 7:33 PM, Peter Olcott 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).

In the first sense, it is exactly equivalent to the Halting problem, and
so the property is known to be uncomputable. In the second sense, it has
a circular definition, so no conclusion can be reached.

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

On 4/18/2012 7:46 PM, Joshua Cranmer wrote:

Yes this is it.

No, not at all. Look at it again and see if you can see the difference.

On 4/18/2012 7:46 PM, Joshua Cranmer wrote:
Actually both of these are incorrect.

In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:

You have to be able to show that you can do it for _any_ TM. Showing
it for a simple example would prove nothing.

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