Sketch of a Disproof of Rice's Theorem

[Peter Olcott]

Continuation of "Pathological Self-Reference and the Halting Problem"

Paraphrase from page 237 of Dexter Kozen's 1997 Automata and
Computability His example proves that a TM that accepts the empty string
is undecidable. Basically I only translated his English prose into the
AnyString() pseudo-code provided below:

My adaptation shows that deciding the decidability of a TM that accepts
the empty string is decidable.

// if t(m) halts
// Accept <sigma>*
// if t(m) does not halt
// Accept NULL (Empty Set)
Boolean AnyString()
{
TM m; // Turing Machine hard-wired into finite-control
String x; // Input data hard-wired into finite-control
m(x);
return true;
}

// This function works correctly for all input that is decidable:
// 1) returns true where tm halts on input. (halts in accept state)
// 2) returns false where tm does not halt on input. (halts in reject state)
// 3) loops on undecidable input.
// function prototype
Boolean Halts(String tm, String input);

// function prototype
Boolean DecidabilityDecider(String tm, String input);

// function invocation
DecidabilityDecider(AnyString, "");

// pseudo-code of above function invocation

if (Decidable(Halts, m, x))
if (Halts(m,x))
return true;
else
return false;
else
return false;

Hypothesis:
1) For the set of possible input strings to the universal set of Turing
Machines there exists no way to show that decidability is undecidable.

2) Reduction of DecidabilityDecider(String tm, String input) to the
Halting Problem is not possible.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> Continuation of "Pathological Self-Reference and the Halting Problem"

Much could be said of this but here is, to my mind, the key issue:

<snip>

> // This function works correctly for all input that is decidable:
> // 1) returns true where tm halts on input. (halts in accept state)
> // 2) returns false where tm does not halt on input. (halts in reject state)
> // 3) loops on undecidable input.
> // function prototype
> Boolean Halts(String tm, String input);

You have not said what "decidable" means here. I can't simply use the
standard meaning because decidability is a property of sets and not of
individual cases.

If you mean "This function works correctly for all input cases that have
a correct true/false answer" then no such machine or function exists.

But in recent postings you been using another meaning. Your magical
DecidabilityDecider had the task of spotting the cases where the Halts
machine got the answer wrong. Using that meaning, Halts can be any
machine at all and the "undecidable inputs" are just the ones it gets
wrong. You've rejected this interpretation of what you mean.

So we are back to the first two of Patricia's questions: what is this
"bug-free" Halts function, and can you prove that such a thing exists?

<snip>
--
Ben.

[George Greene]

On Mar 27, 8:03 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> My adaptation shows that deciding the decidability of a TM that accepts
> the empty string is

.................
Is UNGRAMMATICAL, DUMBASS.
AN INDIVIDUAL TM IS NOT EVEN *THE*KIND* of thing THAT CAN BE
decidable or undecidable!! What CAN be decidable or undecidable IS
A FIRST-ORDER PREDICATE!!!
What CAN be decidable or undecidable is A PROBLEM!!
What CAN be decidable or undecidable is AN INFINITE COLLECTION
of the SAME question ABOUT (countably) infinitely MANY DIFFERENT
things, EACH
of which has to be (encodable by) A FINITE STRING!!!

The KIND of Question that can be decidable(or un-) is "is it even?",
about infinitely many
different natural numbers (because each of them can be encoded as a
string).
A decidable question corresponds to a (totally) recursive language.
If a Question is decidable then there is a TM that 1) always halts,
and 2) ALWAYS
GIVES THE RIGHT ANSWER TO ALL INFNITY instances of the problem, to
all infinity questions making up the Question (or the problem).

"the decidability of a TM" is either 1) MEANINGLESS or 2) TRUE, i.e.,
EVERY individual TM, is "decidable" because it's ONLY ONE TM!
ANYTHING *FINITE* is decidable!! For any FINITE set of questions
each-of-whose-answers-is-a-finite-string, THERE IS a TM that always
halts
on all n (for the relevant finite n) of those questions and always
gives the right
one of the n right answers!
***ALWAYS**!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

As long as the #of questions making up your Question (or problem) is
finite, the Question IS ALWAYS decidable, EVEN IF YOU DON'T KNOW
how to decide it! Even if you don't know whether the answer to the
question is
true or false, if it is only ONE question, then EITHER the TM that
always
says true or the TM that always says false ANSWERS IT CORRECTLY,
SO IT IS DECIDABLE!!!!!!!!!!!!!!

PREDICATES can be undecidable because they involve answering
INFINITELY
many yes-no questions about INFNITELY many DIFFERENT individual finite
strings!
It is necessary that your Question be ABOUT things of UNbounded length/
size
BEFORE IT CAN be even POSSIBLY DEBATABLE whether it is decidable!!!
Since ALL individual TM programs ARE FINITE, "decidability" CANNOT
ARISE
(as a question) FOR AN *INDIVIDUAL* TM!!!!!!!!!!!!!

[Peter Olcott]

On 3/27/2012 8:56 PM, Ben Bacarisse wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>
>> Continuation of "Pathological Self-Reference and the Halting Problem"
> Much could be said of this but here is, to my mind, the key issue:
>
> <snip>
>> // This function works correctly for all input that is decidable:
>> // 1) returns true where tm halts on input. (halts in accept state)
>> // 2) returns false where tm does not halt on input. (halts in reject state)
>> // 3) loops on undecidable input.
>> // function prototype
>> Boolean Halts(String tm, String input);
> You have not said what "decidable" means here. I can't simply use the
> standard meaning because decidability is a property of sets and not of
> individual cases.

The set of elements of <sigma>* that Halts() halts in its accept state T
The set of elements of <sigma>* that Halts() halts in its reject state F
(T <union> F) derives the set named Decidable

> If you mean "This function works correctly for all input cases that have
> a correct true/false answer" then no such machine or function exists.

It you payed better attention you would have seen that I already
specified the third alternative of undecidable inputs.

>
> But in recent postings you been using another meaning. Your magical
> DecidabilityDecider had the task of spotting the cases where the Halts
> machine got the answer wrong. Using that meaning, Halts can be any

I am uncomfortable with calling a failure to respond a wrong answer.
Within the conventional meaning of the term {wrong answer} and the
conventional meaning of the term {failure to respond} calling a {failure
to respond} a {wrong answer} is a lie. How about we just call these
undecidable cases instead.

> machine at all and the "undecidable inputs" are just the ones it gets
> wrong. You've rejected this interpretation of what you mean.
>
> So we are back to the first two of Patricia's questions: what is this
> "bug-free" Halts function, and can you prove that such a thing exists?
>
> <snip>

Once the undecidable inputs are screened out there is nothing in
computing theory that says that the remaining inputs can not always be
correctly decided.

[George Greene]

On Mar 27, 8:03 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:

> Continuation of "Pathological Self-Reference and the Halting Problem"
>
> Paraphrase from page 237 of Dexter Kozen's 1997 Automata and
> Computability His example proves that a TM that accepts the empty string
> is undecidable.

It DOES NOT, DUMBASS.

It proves that THE QUESTION, about AN ARBITRARY TM,
about ANY AND EVERY TM, about the INFNITY OF ALL TMs,
about whether each and every DIFFERENT one of THEM -- every
TM that, unlike your analyzers and deciders, ACTUALLY EXISTS --
accepts the empty string, is undecidable.
This Question is INFINITELY MANY DIFFERENT questions!
It is ALL OF THE FOLLOWING questions AT ONCE:
"Does TM#1 accept the empty string?"
"Does TM#2 accept the empty string?"
"Does TM#3 accept the empty string?"
"Does TM#4 accept the empty string?" etc. etc. etc.

It is ONLY INFINITE FAMILIES of questions like this THAT CAN be
decidable/undecidable!
It is to and only to INFINITE FAMILIES of similar questions (ABOUT
infinitely many
different things, questions with a PARAMETER that can range in size
from zero up
without bound, unless you want to count countable-infinity as an
unachieved bound)

The undecidability-proof (the Rice's Theorem proof) that you are
looking at proves THIS:
There is no TM-that-halts-on-every-input (accept-halt or reject-halt)
that accept halts
on-and-only-on those input strings that are encodings of a TM that
accepts the empty string.

Let us call (for reasons that we pray you will accept) a TM that
accept-halts or reject-halts
on every input, with all due respect to our past president, "A
DECIDER".
What Rice's theorem says is that NO non-trivial predicate has A
DECIDER.
Since halting-on-yourself is a non-trivial predicate, IT CANNOT HAVE A
DECIDER.

[George Greene]

On Mar 27, 9:56 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:

> You have not said what "decidable" means here.  I can't simply use the
> standard meaning because decidability is a property of sets and not of
> individual cases.

And the point does bear stressing that before any DOUBT about the
question of decidability can arise, the sets HAVE to be INFINITE sets.
Finite sets are decidable trivially.
It should perhaps also be stressed to him that these are sets whose
different elements are the different possible input-strings describing
instances of the problem. I think it is helpful here in ascii-land
to style an instance as a "question" and the infinitary collection of
all of them (all applications of the same predicate/problem to
different input-things) as the (singular) "Question".

[George Greene]

On Mar 27, 10:17 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> The set of elements of <sigma>* that Halts() halts in its accept state T

This is still not grammatical. Halts(.) TAKES AT LEAST ONE ARGUMENT/
INPUT.
Done right, IT TAKES TWO (one to identify the TM and a second to be
the
input that the TM will run on).
You have to NAME the generic element of <sigma>* so that we KNOW that
THAT
is what you are supplying as the argument(s) of Halts(.).

> The set of elements of <sigma>* that Halts() halts in its reject state F
> (T <union> F) derives the set named Decidable

You CANNOT NAME a set "Decidable" because DECIDABLE ALREADY *HAS*
A MEANING around here! And its meaning IS NOT a set!!! Its meaning IS
a PROPERTY of PROBLEMS!!!
Or a property of LANGUAGES, each of which is IN ITS turn a set!
If the set you are CALLING "Decidable" is not equal to <sigma>*
Then Halts(.) IS NOT DECIDABLE !!

> > If you mean "This function works correctly for all input cases that have
> > a correct true/false answer" then no such machine or function exists.

DUH.
The question is NOT whether WE mean that.
The question is whether YOUR Halts(.) means that.
If THAT'S what it means then IT IS NOT A TM.
It can STILL be a FUNCTION, though.
Not ALL functions are TM-computable.
This is a pure matter of cardinality.
Since TM-programs have to be finite, there can only be
countably-infnitely many of them. But since they have to
give infinitely many true/false answers, obviously, the class
or space of all countably-infinitely-long bit strings has size
2^[countably-infinite], SO IT'S BIGGER.

> It you payed better attention you would have seen that I already
> specified the third alternative of undecidable inputs.

If you had the first clue what "undecidable" MEANS then you would
KNOW that there CAN'T BE ANY SUCH THING as an "undecidable"
INDIVIDUAL INPUT. It is PROBLEMS or LANGUAGES (ALL of which
involve INFINITELY MANY yes/no questions) that CAN be (or not be)
decidable or undecidable! OTHER kinds of things DON'T GET to play!

[Peter Olcott]

On 3/27/2012 8:56 PM, Ben Bacarisse wrote:

None of the theory of computation can show that a TM that has the
purpose of detecting halting can not always have exactly three actions:
(a) Correctly Halt in its accept state indicating that the input TM will
halt on its input
(b) Correctly Halt in its reject state indicating that the input TM will
not halt on its input
(c) Loop on undecidable cases.

None of computing theory can show that a
Boolean DecidabilityDecider(String tm, String input) can not always
1) Correctly halt in its accept state indicating that its input TM is a
decider for its input.
2) Correctly halt in its reject state indicating that its input TM is a
not decider for its input.

//
// A true halt decider for all valid input
//
if (DecidabilityDecider(Halts, tm, input))
if (Halts, (tm, input) )

return true;
else
return false;
else

Print("Input to Halts() is Semantically Mal-Formed!")

[Peter Webb]

Peter, you and I are going to become famous and rich.

I can provide a TM which steps through every even number until it finds one
that isn't the sum of two primes, and then it halts. This means it only
halts if Goldbach's conjecture is false.

As a follow-up - and ensuring our place in mathematical history - I can
write a TM which checks every odd number and halts if it finds one which is
the sum of its divisors. If you can show that it does not halt, then we have
proved that no odd perfect numbers exist. If it does halt, we have found an
odd perfect number.

All that is missing is for you to create your TM which determines if an
arbitrary TM halts, and we will become famous.

Please let me know when you have done this, and I will get ready for us to
assume our rightful place in the pantheon of mathematical greats!

[George Greene]

On Mar 27, 10:41 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> None of the theory of computation can show

SHUT *UP*!!! You have not studied ENOUGH of the theory of
computation to be entitled to BEGIN ANY sentence with that phrase!
None of the theory of computation THAT YOU HAVE SEEN SO FAR,
maybe. But the use of "can"???? MY GOD!! EVEN EXPERTS in the field
aren't sure what CAN happen, later, eventually, after further
advances!
Couldn't you AT LEAST have the PRUDENCE to phrase it,
"Nothing I've seen in the theory of computation shows me that..."
??? WELL? COULDN'T you?? Can't you see that the sheer arrogance
of the phrasing invites abuse????

> that a TM that has the purpose of

SHUT *UP*!!!!! *NO* TM *EVER*HAS*ANY* *PURPOSE*!!!!
They ALL only have FACTUAL ACTIONS! They ALL just do what the do!
Their purpose is to do EXACTLY what they DO do! NO TM CAN EVER
fail to achieve ITS OWN purpose!!
Now, of course, it could fail to achieve some purpose that Peter
Olcott
HOPED it could achieve, YES, THAT COULD happen.
IF we were confident that your native language was English and that
you had seen a smattering of English-language TV and movies then we
could refer you to an entertainment franchise dubbed "Mission:
Impossible"
about secret agents sent on missions that most agents could not
possibly
complete successfully. But NO TM has a mission INHERENT to ITSELF!
The MISSIONS all come FROM OUTSIDE TM-land, from other logical
criteria,
and sometimes, NO TM *CAN* accomplish them! The mission of
"halting on all and only those input-strings encoding the program of a
TM that doesn't halt on its own program-string"
REALLY IS "Mission: Impossible". No such TM exists.

> detecting halting can not always have exactly three actions:
> (a) Correctly Halt in its accept state indicating that the input TM will
> halt on its input
> (b) Correctly Halt in its reject state indicating that the input TM will
> not halt on its input
> (c) Loop on undecidable cases.

"Correctly halt" IS NOT an ACTION. The action is Halt.
If THAT TM halted then halting WAS the correct action for THAT TM.
It may not have been the correct action "for the Halts() TM" but THAT
IS IRRELEVANT
since THE Halts() TM DOES NOT EXIST IN THE FIRST PLACE.

And as for (c), THERE IS NO SUCH THING as an undecidable individual
case,
wherefore THERE ARE NO "undecidable cases".

[George Greene]

On Mar 27, 10:57 pm, "Peter Webb" <r.peter.webb...@gmail.com> wrote:
> All that is missing is for you to create your TM which determines if an
> arbitrary TM halts, and we will become famous.

You may not live so long.
Even if Olcott's halt-determining TM really exists, you STILL may not
live so long.
Even if Goldbach's conjecture really is false and even if you
have already written that TM and even if it is already running fast on
a supercomputer, YOU STILL may not live so long, even if you are right
and even if your TM is the correct one for solving that problem.

[Joshua Cranmer]

On 3/27/2012 9:41 PM, Peter Olcott wrote:
> None of the theory of computation can show that a TM that has the
> purpose of detecting halting can not always have exactly three actions:
> (a) Correctly Halt in its accept state indicating that the input TM will
> halt on its input
> (b) Correctly Halt in its reject state indicating that the input TM will
> not halt on its input
> (c) Loop on undecidable cases.

You seem to be attempting what is conventionally the "halts, doesn't
halt, I can't tell" model of the halting problem.

> None of computing theory can show that a
> Boolean DecidabilityDecider(String tm, String input) can not always
> 1) Correctly halt in its accept state indicating that its input TM is a
> decider for its input.
> 2) Correctly halt in its reject state indicating that its input TM is a
> not decider for its input.

I'm not sure what you mean by this.
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

[Patricia Shanahan]

On 3/27/2012 8:54 PM, Joshua Cranmer wrote:
> On 3/27/2012 9:41 PM, Peter Olcott wrote:
>> None of the theory of computation can show that a TM that has the
>> purpose of detecting halting can not always have exactly three actions:
>> (a) Correctly Halt in its accept state indicating that the input TM will
>> halt on its input
>> (b) Correctly Halt in its reject state indicating that the input TM will
>> not halt on its input
>> (c) Loop on undecidable cases.
>
> You seem to be attempting what is conventionally the "halts, doesn't
> halt, I can't tell" model of the halting problem.

I've tried suggesting that. I believe there are three differences:

1. The three result model is useful.

2. The three result model can be implemented.

3. (and this may be the issue) The three result model does not in any
way contradict halting undecidability, Rice's Theorem, or any other
established result.

Patricia

[Ross A. Finlayson]

Do you, know any computer programs that are intractable to static
analysis?

I imagine one might, in bulk to limits of the de-compiler, write out
the complete program (using knowledge of worst-case asymptotics of the
decompiler) or otherwise write deterministic programs intractable to
static analysis. But, seriously, what all behavior is undefined in a
general virtual machine framework?

It's like, for a function with one input variable, given that you can
read all the program and data which don't change except according to
the program execution that you control, and there are no other
variables, there is an output bit, I think you can state
deterministically what that is. (With defined behavior in a virtual
machine framework.)

Isn't the coding deterministic for the (virtual) program model?
(Arithmetic is.)

Is there a program outside the decider program limits? Sure there is
(unless that's built into the program model, for example, i.e. for
any.) So if you use Rice's theorem and you're already using all the
computing resources then yeah there are programs intractable to you.
But, you might be hard pressed to actually find any program in use to
be intractable (in the general sense).

[Peter Olcott]

On 3/27/2012 10:54 PM, Joshua Cranmer wrote:
> On 3/27/2012 9:41 PM, Peter Olcott wrote:
>> None of the theory of computation can show that a TM that has the
>> purpose of detecting halting can not always have exactly three actions:
>> (a) Correctly Halt in its accept state indicating that the input TM will
>> halt on its input
>> (b) Correctly Halt in its reject state indicating that the input TM will
>> not halt on its input
>> (c) Loop on undecidable cases.
>
> You seem to be attempting what is conventionally the "halts, doesn't
> halt, I can't tell" model of the halting problem.
>
>> None of computing theory can show that a
>> Boolean DecidabilityDecider(String tm, String input) can not always
>> 1) Correctly halt in its accept state indicating that its input TM is a
>> decider for its input.
>> 2) Correctly halt in its reject state indicating that its input TM is a
>> not decider for its input.
>
> I'm not sure what you mean by this.

You have removed too much of the context for me to explain.

[Peter Olcott]

It is the part that you removed that is significant.
The non trivial property of decidability can always be decided for a
recursively enumerable set.
Because this property can always be decided a halt decider that decides
all of its input can be made.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/27/2012 8:56 PM, Ben Bacarisse wrote:
>> Peter Olcott<NoS...@OCR4Screen.com> writes:
>>
>>> Continuation of "Pathological Self-Reference and the Halting Problem"
>> Much could be said of this but here is, to my mind, the key issue:
>>
>> <snip>
>>> // This function works correctly for all input that is decidable:
>>> // 1) returns true where tm halts on input. (halts in accept state)
>>> // 2) returns false where tm does not halt on input. (halts in reject state)
>>> // 3) loops on undecidable input.
>>> // function prototype
>>> Boolean Halts(String tm, String input);
>> You have not said what "decidable" means here. I can't simply use the
>> standard meaning because decidability is a property of sets and not of
>> individual cases.
>
> The set of elements of <sigma>* that Halts() halts in its accept state T
> The set of elements of <sigma>* that Halts() halts in its reject state F
> (T <union> F) derives the set named Decidable

An interesting change. Your last definition had the stipulation that
the result had to be correct. Now, T union F is just the set of inputs
on which Halts halts. The "decidability decider" must just decide the
complement of that set. It is, in effect, a halt decider. Is this just
a mistake, or have you changed your mind?

>> If you mean "This function works correctly for all input cases that have
>> a correct true/false answer" then no such machine or function exists.
> It you payed better attention you would have seen that I already
> specified the third alternative of undecidable inputs.

Yes, but I am asking you to tell me the specification of Halts. You've
rejected lots of examples because they are not "bug-free". I am very
happy that you permit a set of inputs on which a putative halt decider
may not halt, but you have to say what these cases are. With no
restrictions, people will show reductions to halting by picking any
Halts implementation they like.

If you don't define "bug-free" there are simple machines for which
neither T union F not its complement are decidable (and it's even easier
with you new definition).

>> But in recent postings you been using another meaning. Your magical
>> DecidabilityDecider had the task of spotting the cases where the Halts
>> machine got the answer wrong. Using that meaning, Halts can be any
>
> I am uncomfortable with calling a failure to respond a wrong
> answer. Within the conventional meaning of the term {wrong answer} and
> the conventional meaning of the term {failure to respond} calling a
> {failure to respond} a {wrong answer} is a lie. How about we just call
> these undecidable cases instead.

Because they are decidable. All halting cases are decidable. I see
no problem with "wrong". A putative decider for some set that does not
halt on some input is wrong.

>> machine at all and the "undecidable inputs" are just the ones it gets
>> wrong. You've rejected this interpretation of what you mean.
>>
>> So we are back to the first two of Patricia's questions: what is this
>> "bug-free" Halts function, and can you prove that such a thing exists?
>>
>> <snip>
>
> Once the undecidable inputs are screened out there is nothing in
> computing theory that says that the remaining inputs can not always be
> correctly decided.

Yes, once the wrong numbers are screened out from this function

Bool is_this_one_of_next_weeks_lottery_numbers(int n)

there is nothing stopping me from being very rich. Stating a condition
is not the same as showing that anything can meet it.

--
Ben.

[Peter Olcott]

On 3/27/2012 10:54 PM, Joshua Cranmer wrote:
> On 3/27/2012 9:41 PM, Peter Olcott wrote:
>> None of the theory of computation can show that a TM that has the
>> purpose of detecting halting can not always have exactly three actions:
>> (a) Correctly Halt in its accept state indicating that the input TM will
>> halt on its input
>> (b) Correctly Halt in its reject state indicating that the input TM will
>> not halt on its input
>> (c) Loop on undecidable cases.
>
> You seem to be attempting what is conventionally the "halts, doesn't
> halt, I can't tell" model of the halting problem.
>
>> None of computing theory can show that a
>> Boolean DecidabilityDecider(String tm, String input) can not always
>> 1) Correctly halt in its accept state indicating that its input TM is a
>> decider for its input.
>> 2) Correctly halt in its reject state indicating that its input TM is a
>> not decider for its input.
>
> I'm not sure what you mean by this.

You are still at the premise, please move on to the reasoning and its
tentative conclusion.

[Peter Olcott]

On 3/27/2012 11:53 PM, Patricia Shanahan wrote:

Right you are still looking at the premises, and have not yet examined
the reasoning or its tentative conclusion.

Here is a preview of the reasoning:

Boolean HaltDecider(String tm, String input)
{
if (Decidable(Halts, tm, input))
if (Halts(tm, input))

return true;
else
return false;
else

Print("The input is semantically incorrect!");
}

[Peter Olcott]

You did not yet get to the reasoning, you are still on the premises.
Premises are defined as true, and they are also self consistent.

[Peter Olcott]

On 3/28/2012 5:29 AM, Ben Bacarisse wrote:

>> The set of elements of<sigma>* that Halts() halts in its accept state T
>> > The set of elements of<sigma>* that Halts() halts in its reject state F
>> > (T<union> F) derives the set named Decidable
> An interesting change. Your last definition had the stipulation that
> the result had to be correct.

So when a halt decider halts in its accept state for all input tms that
halt on their input and halts in its reject state for all tms that do
not halt on their input, this is *incorrect* ?

[Peter Olcott]

On 3/28/2012 5:29 AM, Ben Bacarisse wrote:

> Now, T union F is just the set of inputs
> on which Halts halts. The "decidability decider" must just decide the
> complement of that set. It is, in effect, a halt decider. Is this just
> a mistake, or have you changed your mind?

T <union> F is the inputs which Halts correctly decides.
The Decidability Decider matches these inputs so that it can screen out
semantically invalid inputs.

if (Decidable(Halts, tm, input))
if (Halts(tm, input))

return true;
else
return false;
else

Print("Semantically Invalid Input");

[Peter Olcott]

On 3/28/2012 5:29 AM, Ben Bacarisse wrote:

> If you don't define "bug-free" there are simple machines for which
> neither T union F not its complement are decidable (and it's even easier
> with you new definition).

Bug free means that:
1) Whenever Halts() halts in its accept state its input tm would halt on
its input.
2) Whenever Halts() halts in its reject state its input tm would not
halt on its input.
3) The only cases that Halts() does not halt are those cases that are
undecidable for it.

Wasn't this entirely self-evidently logically entailed by the term
"bug-free" ?
Is there anything at all that "bug-free" could possibly correctly mean
besides the above specification?

[Peter Olcott]

On 3/28/2012 5:29 AM, Ben Bacarisse wrote:

> Because they are decidable. All halting cases are decidable. I see
> no problem with "wrong". A putative decider for some set that does not
> halt on some input is wrong.

OK fine, then what time is it (yes or no) ?
a) It must be in hours and minutes because it is time.
b) It can't be in hours and minutes because a (yes or no) answer is
specified.
c) If you don't answer this counts as a wrong answer.

This is the exact same situation as a Turing Machine that is provided
input defined with Pathological Self-Reference.

[George Greene]

On Mar 28, 7:03 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> So when a halt decider halts

Since THERE IS NO SUCH THING as a "halt decider", THIS IS A STUPID
QUESTION.

You claim to AGREE with us that there is no TM that gets ALL the "does
m halt on i?"
questions RIGHT. THEREFORE, THERE IS NO halt decider.
Any TM that YOU (and NObody else) are WRONGLY CALLING a halt decider
THEREFORE OUGHT to be called SOMETHING ELSE. But if it can't meet the
criterion of "being a halt decider" just WHAT criteria are you asking
it to meet?
Just WHICH tm's are you trying to deal with here?

[George Greene]

On Mar 28, 5:38 am, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> The non trivial property of decidability can always be decided for a
> recursively enumerable set.

Every recursively enumerable set is either decidable or semi-
decidable,
BY DEFINITION. Recursively-enumerable-but-not-recursive MEANS
semi-decidable, BY DEFINTION. Just plain recursive, or total
recursive,
or totally recursive, MEANS "decidable", BY DEFINITION.

> Because this property can always be decided a halt decider that decides
> all of its input can be made.

No, it can't, because a set that is recursively enumerable BUT NOT
RECURSIVE,
i.e., that is recursively enumerable but DOES NOT HAVE a recursively
enumerable COMPLEMENT,
CANNOT BE the-set-accepted BY ANY tm that always halts.

Sets that are recursively-enumerable-but-not(totally)-recursive have
the property
of being the halt-set of some TM, while their complement is,
correspondingly, the
set of inputs on which that same TM *does*not* halt. Since there is
no TM that can
TELL you that some-tm-that-is-known-to-accept-some-recursively-
enumerable-but-not-totally-recursive,
i.e., SEMI-decidable, language, will NEVER halt on some input, you are
always, in practice
going to be IN DOUBT FOR A LONG TIME about the status of A GREAT many
of the possible
elements of such a set. Indeed, there is no TM-computable bound on
the amount of time
you might have to WAIT for a confirmation, EVEN WHEN ONE IS
FORTHCOMING.
Proof-search is ALSO LIKE that.

[George Greene]

On Mar 28, 7:00 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> You did not yet get to the reasoning, you are still on the premises.
> Premises are defined as true,

NO, they are PRESUMED trie.

> and they are also self consistent.

Not necessarily. Everybody is free to proffer
inconsistent premises if he wants to. But he is NOT
free to KEEP claiming that they are consistent, AFTER
a contradiction is derived from them.

[George Greene]

On Mar 28, 7:12 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> Bug free means

existing, since ALL TMs are "bug free" BY DEFINITION.

> that:
> 1) Whenever Halts() halts in its accept state its input tm would halt on
> its input.

Since Halts() does not exist, THIS IS MEANINGLESS.
What you MEAN to say is that if you have some CANDIDATE tm
h -- NOT Halts(), then *h*, NOT Halts(), is bug-free if h satisfies
all these constraints. It will of course turn out that you have
specified the constraints SO POORLY that TONS of h's will meet them
WITHOUT being "bug-free" -- they will have TONS of bugs in the form
of FAILURE TO ANSWER questions that CLEARLY ARE answerable.

> 2) Whenever Halts() halts in its reject state its input tm would not
> halt on its input.
> 3) The only cases that Halts() does not halt are those cases that are
> undecidable for it.

OK, here are two TMs.
Each of them is very simple. It just has 1 instruction and 1 state
(the start state).
It reads the first cell of its input tape (as all TMs are required to
do) and then
TM#1, named H, halts.
TM#2, named L, writes something in its cell and advances 1 cell to the
right,
and then transitions back to the same state (whence it must
necessarily do the same thing again,
and thus keep advancing to the right forever, and therefore never
halt, which is why we named it L).
H stands for "Halt"; L stands for "Loop".

There must, therefore, ALSO exist a THIRD tm, call it h (h takes 2 arg/
parms)
that halts/accept-true when its first input is H (it doesn't matter
what the 2nd input is since
H ignores its input anyway), and halts/reject-false when its 1st input
is L (it doesn't matter
what the 2nd input is since L loops on all inputs). This simple tm h
is simple because IT LOOPS
ON ALL other inputs. In other words, it knows that 1 program (namely
H) that halts on all inputs
will halt, and that 1 program (namely L) that loops on all inputs will
loop, BUT IT KNOWS *NOTHING* else.
ALL other cases ARE[what YOU WRONGLY call]"UNDECIDABLE" for THIS h.

This is why Ben is wrong to indulge your definitions; we can't EVEN
SAY what the problem
is if you have already stolen the word.

Confronted with h, YOU HAVE A PROBLEM.
YOUR PROBLEM IS, that by your definition, h IS BUG-FREE.

> Wasn't this entirely self-evidently logically entailed by the term
> "bug-free" ?

> Is there anything at all that "bug-free" could possibly correctly mean
> besides the above specification?

Well, SURE, it could MEAN that h actually WAS bug-free, that in
ADDITION to
satisfying "If h accept-halts, it machine input halts on its argument
input", h ALSO
satisfied THE CONVERSE of that, namely, "if its machine input doesn't
halt on its
argument input THEN h accept-halts". And analogously for reject-
halts.
IN OTHER words, INSTEAD of starting with "Whenever", bug-free MIGHT
have meant
that h accept-halts WHENEVER its machine-input halts on its argument-
input.
In other words, YOU SAID IT BACKWARDS.

[George Greene]

On Mar 28, 7:16 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> On 3/28/2012 5:29 AM,
Ben Bacarisse wrote:> Because they are decidable.  All halting cases
are decidable.

Ben is missing the point here; all INDIVIDUAL cases OF ANYthing are
"decidable".
"Decidable" does not even START TO HAVE meaning UNTIL AFTER you are
dealing
with AN INFINITE FAMILY of similar questions, and an infinite number
of individual answers.

[George Greene]

On Mar 28, 1:48 am, "Ross A. Finlayson" <ross.finlay...@gmail.com>
wrote:

> Do you, know any computer programs that are intractable to static
> analysis?

No INDIVIDUAL program is intractable.
The question is, IF YOU write *1* program that PERFORMS static
analysis, can we find a computer program that is intractable FOR YOUR
1
program. AND YES, we can ALWAYS find a few.

There is no 1 program that can statically analyze all the others, and
there is no 1 program that is invulnerable to static analysis by ALL
the analyzers.
But EVERY analyzer will fail to analyze SOME program.

> It's like, for a function with one input variable, given that you can
> read all the program and data which don't change except according to
> the program execution that you control, and there are no other
> variables, there is an output bit, I think you can state
> deterministically what that is.  (With defined behavior in a virtual
> machine framework.)

YOU can state deterministically what this output bit is, IF THERE IS
an output bit!
BUT *WHAT*IF* the program LOOPS and NEVER GETS AROUND TO FINISHING
its computation of the output bit?!?? What THEN??? SOME programs DO
LOOP
on SOME inputs! If you have been running this program on its input
in your
virtual machine framework, deterministically, FOR A LONG TIME, AND IT
STILL HASN'T
PUT OUT its output bit, and you still haven't determined its output
bit, then HOW DO YOU
KNOW if this program IS EVER going to put out an output bit for this
input? MIGHT
this INSTEAD be one of those inputs for which the program simply WILL
NEVER put out
an output bit?

> Isn't the coding deterministic for the (virtual) program model?
> (Arithmetic is.)

NO, IT ISN'T.
If you write a deterministic program to print out the 1st odd perfect
number
(that is arithmetic) or the even number that is NOT the sum of 2
primes, YOU DO NOT KNOW
whether it ever will or won't print out anything!!

> Is there a program outside the decider program limits?

Since THERE IS NO DECIDER PROGRAM, THIS IS A STUPID QUESTION.

>  So if you use Rice's theorem and you're already using all the
> computing resources then yeah there are programs intractable to you.

And if you don't use Rice's theorem, GUESS WHAT: YOU ARE STILL
USING RICE'S THEOREM ANYWAY, BECAUSE *IT'S*A*THEOREM*.
IT'S *PROVED*. IT'S PROVED *WHETHER*YOU*UNDERSTAND*
the proof OR NOT, and it's proved whether you BELIEVE it OR NOT.
It doesn't NEED your ASSENT to be PROVED!!
Like all the rest of science,
IT'S TRUE WHETHER YOU BELIEVE IN IT *OR*NOT*,
* D U M B A S S *.

[Peter Olcott]

On 3/28/2012 5:29 AM, Ben Bacarisse wrote:

>> Once the undecidable inputs are screened out there is nothing in
>> > computing theory that says that the remaining inputs can not always be
>> > correctly decided.
> Yes, once the wrong numbers are screened out from this function
>
> Bool is_this_one_of_next_weeks_lottery_numbers(int n)
>
> there is nothing stopping me from being very rich. Stating a condition
> is not the same as showing that anything can meet it.

Hypothesis:
1) For the set of possible input strings to the universal set of Turing
Machines there exists no way to show that decidability is undecidable.

2) Reduction of DecidabilityDecider(String tm, String input) to the
Halting Problem is not possible.

[George Greene]

On Mar 28, 7:00 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> You did not yet get to the reasoning,

The reasoning DOESN'T MATTER because you DON'T UNDERSTAND
the basic concepts. You DON'T KNOW what "decidable' MEANS!!

[Joshua Cranmer]

If there's confusion in what your premise is, what hope have you that
your reasoning or conclusion are clear and concise? To quote a book I
have, "an error in the premise leads to an error in the conclusion."

[Patricia Shanahan]

On 3/28/2012 3:57 PM, Peter Olcott wrote:
> On 3/27/2012 11:53 PM, Patricia Shanahan wrote:
>> On 3/27/2012 8:54 PM, Joshua Cranmer wrote:
>>> On 3/27/2012 9:41 PM, Peter Olcott wrote:
>>>> None of the theory of computation can show that a TM that has the
>>>> purpose of detecting halting can not always have exactly three actions:
>>>> (a) Correctly Halt in its accept state indicating that the input TM
>>>> will
>>>> halt on its input
>>>> (b) Correctly Halt in its reject state indicating that the input TM
>>>> will
>>>> not halt on its input
>>>> (c) Loop on undecidable cases.
>>>
>>> You seem to be attempting what is conventionally the "halts, doesn't
>>> halt, I can't tell" model of the halting problem.
>>
>> I've tried suggesting that. I believe there are three differences:
>>
>> 1. The three result model is useful.
>>
>> 2. The three result model can be implemented.
>>
>> 3. (and this may be the issue) The three result model does not in any
>> way contradict halting undecidability, Rice's Theorem, or any other
>> established result.
>>
>> Patricia
> Right you are still looking at the premises, and have not yet examined
> the reasoning or its tentative conclusion.

Grant me an incorrect or sufficiently confused premise, and I could
prove anything. If I don't understand and agree with the premise, I
don't care what conclusions can be drawn from it.

Patricia

[Ben Bacarisse]

Any comment? Are you changing the definition?

>>
>>>> >> If you mean "This function works correctly for all input cases that have
>>>> >> a correct true/false answer" then no such machine or function exists.
>>> > It you payed better attention you would have seen that I already
>>> > specified the third alternative of undecidable inputs.
>> Yes, but I am asking you to tell me the specification of Halts.
> You did not yet get to the reasoning, you are still on the premises.
> Premises are defined as true, and they are also self consistent.

That's not true. You need to add some reading in logic to your list.

--
Ben.

[Ben Bacarisse]

No, it is not the same at all. The question, "does TM t halt on input
i" has a correct true/false answer and entails no logical nonsense.
Nothing new here, of course, but since you keep making the same silly
analogy, the same reply is needed.

I am glad, though, that you agree with my term "wrong". Let's go ahead
and rename

Decidable(Halts, t, i)

as

GetsItWrong(Halts, t, i)

(with a corresponding flip of the condition, of course) when Halts(t,i)
either does not terminate or is otherwise incorrect. This is much less
confusing to people who know that all the cases are decidable, but that
certain machines (called Halts here) get some cases wrong.

--
Ben.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/28/2012 5:29 AM, Ben Bacarisse wrote:
>> If you don't define "bug-free" there are simple machines for which
>> neither T union F not its complement are decidable (and it's even easier
>> with you new definition).
> Bug free means that:
> 1) Whenever Halts() halts in its accept state its input tm would halt
> on its input.
> 2) Whenever Halts() halts in its reject state its input tm would not
> halt on its input.
> 3) The only cases that Halts() does not halt are those cases that are
> undecidable for it.
>
> Wasn't this entirely self-evidently logically entailed by the term
> "bug-free" ?

No, because the definition is based on another undefined term. When
pressed to define Invalid_Input, you came up with a definition that, you
insist, only applies to "bug-free" Halts machines. Now, when asked to
define these bug-free Halts machines, you make the definition depend on
an undefined concept of invalid input (now called undecidable cases). I
say that this concept of undecidable cases is undefined because you've
claimed that your old definition of it (Invalid_Input) applied only the
class of machine you are currently defining! You wouldn't push a
circular definition on us would you?

> Is there anything at all that "bug-free" could possibly correctly mean
> besides the above specification?

Yes, of course. The natural meaning is of a correct halting decider.
Yours is of a partially correct one with an unspecified number of cases
that it is permitted to get wrong. That's not the obvious meaning of
"bug-free".

--
Ben.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/28/2012 5:29 AM, Ben Bacarisse wrote:
>> Now, T union F is just the set of inputs
>> on which Halts halts. The "decidability decider" must just decide the
>> complement of that set. It is, in effect, a halt decider. Is this just
>> a mistake, or have you changed your mind?
> T <union> F is the inputs which Halts correctly decides.

Right. So it was just a mistake on your behalf. I note that you
snipped your incorrect definition:

| The set of elements of <sigma>* that Halts() halts in its accept state T
| The set of elements of <sigma>* that Halts() halts in its reject state F
| (T <union> F) derives the set named Decidable

It would help if you sometimes just said "yes, that was a slip".

<snip>
--
Ben.

[Ben Bacarisse]

No, it's just not what you said.

This is different to the old definition where the answer had to be
correct. It just looked wrong, and you've agreed elsewhere that it was
just a slip. I have to comment on what you write, not what I think you
meant to write.

--
Ben.

[Ross A. Finlayson]

Great, you should write IBM and tell them that they didn't really
solve the pi calculus in the late '90's, or there's no well-defined
virtual program model.

For each program size yes there is a de-compiler program that handles
that input. As well, for almost all purposeful programs that do
anything, eg in reversible results here where there's only one entry
to the function, there are small de-compilers that handle programs of
unbounded size in continually incrementing progress toward the answer
in basically co-execution of the deterministic algorithm.

Then there are either unbounded resources or unbounded resources, for
the de-compiler.

A point of static analysis is to, for example, keep loops in the
program model. Your program were it to halt is simply evaluated by
virtual evaluation where there has been a virtual machine implemented
in the de-compiler in the language of the instruction set that is the
Goedel coding. Then each of its loops is separately tractable, and a
simple program model normal form's allow the solution of trivial
nested and cascading loops in evaluation, and composition simply of
the program models' elements.

I think people have the impression that a simple "definition" of a
transcendental function is non-constructive. (How about in ZF?)
There's only one entry point to the function and with a well-defined
virtual machine: general purpose algorithms progress toward the
evaluation of Halts().

This is a function of the virtual machine's basic operations not the
program size, how much code it takes to implement a complete de-
compiler and for any program with a deterministic output the value of
Halts().

Its language size, as much and more than program size, is relevant as
to how big a program is to evaluate Halts(L, P). Then, where the
program can be written in a forward form's manner, if all the results
are constructive and well-defined, there's only ever a finite program.

Ross Finlayson

[Ross A. Finlayson]

On Mar 28, 10:11 pm, "Ross A. Finlayson" <ross.finlay...@gmail.com>

I understand that's a big sort but there's unlimited resources.

Basically in reducing backward for each step forward, there is
continually completing progress toward any algorithm, and, because
there are only finitely many total conditions to evaluate as a binary
product to evaluate Halts() for each program size, there are unlimited
resources of the de-compiler to use for each of those (in a bounded
program description, bounded complete to the virtual machine).

There are no machine limits.

Ross Finlayson

[Patricia Shanahan]

On 3/28/2012 4:12 PM, Peter Olcott wrote:
...

> 3) The only cases that Halts() does not halt are those cases that are
> undecidable for it.

So what exactly does "undecidable for it" mean in this context? Remember
there is exactly one possible outcome for a given TM with a given input.

Suppose I have a three result {true, false, "don't know"} TM, M1, that
returns true and false for a subset of inputs for which it can provably
correctly evaluate whether they represent a TM computation that halts,
and returns "don't know" for all other inputs. That is something that
can be proved to exist.

I now construct a new TM, M2, that does the following:

Pass its input to M1.

If M1 returns true, return true.

If M1 returns false, return false.

If M1 returns "don't know" go into an infinite loop.

Is M2 bug-free? If not, why not?

Patricia

[Peter Olcott]

On 3/28/2012 8:02 PM, Ben Bacarisse wrote:
>>>>>>> >>>> >> If you mean "This function works correctly for all input cases that have
>>>>>>> >>>> >> a correct true/false answer" then no such machine or function exists.
>>>>> >>> > It you payed better attention you would have seen that I already
>>>>> >>> > specified the third alternative of undecidable inputs.
>>> >> Yes, but I am asking you to tell me the specification of Halts.
>> > You did not yet get to the reasoning, you are still on the premises.
>> > Premises are defined as true, and they are also self consistent.
> That's not true. You need to add some reading in logic to your list.

If all boats are cats, then boats say meaow.

[Peter Olcott]

On 3/28/2012 8:02 PM, Ben Bacarisse wrote:

>>>>>>> >>>> >> If you mean "This function works correctly for all input cases that have
>>>>>>> >>>> >> a correct true/false answer" then no such machine or function exists.
>>>>> >>> > It you payed better attention you would have seen that I already
>>>>> >>> > specified the third alternative of undecidable inputs.
>>> >> Yes, but I am asking you to tell me the specification of Halts.
>> > You did not yet get to the reasoning, you are still on the premises.
>> > Premises are defined as true, and they are also self consistent.
> That's not true. You need to add some reading in logic to your list.

Within the scope of determining the validity of deductive logical
inference premises are defined as true, like a given in geometry.

[Peter Olcott]

On 3/28/2012 8:17 PM, Ben Bacarisse wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>
>> > On 3/28/2012 5:29 AM, Ben Bacarisse wrote:
>>> >> Because they are decidable. All halting cases are decidable. I see
>>> >> no problem with "wrong". A putative decider for some set that does not
>>> >> halt on some input is wrong.
>> > OK fine, then what time is it (yes or no) ?
>> > a) It must be in hours and minutes because it is time.
>> > b) It can't be in hours and minutes because a (yes or no) answer is
>> > specified.
>> > c) If you don't answer this counts as a wrong answer.
>> >
>> > This is the exact same situation as a Turing Machine that is provided
>> > input defined with Pathological Self-Reference.
> No, it is not the same at all. The question, "does TM t halt on input
> i" has a correct true/false answer and entails no logical nonsense.

So still do not comprehend Pathological Self-Reference?

[Peter Olcott]

On 3/28/2012 8:17 PM, Ben Bacarisse wrote:

> I am glad, though, that you agree with my term "wrong". Let's go ahead
> and rename
>
> Decidable(Halts, t, i)
>
> as
>
> GetsItWrong(Halts, t, i)

That would be backwards, that would be Undecidable().
GetsItCorrectly() would be more apt, yet I am going to stick with
Decidable() and DecidabilityDecider().

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:
<snip>
> Boolean HaltDecider(String tm, String input)
> {

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

> Print("The input is semantically incorrect!");
> }

Stepping back a bit...

If I understand your other posts, this construct only applies to
"bug-free" Halts machines, and these have the property that they are
correct except that they don't halt on exactly those inputs that
Decidable(Halts, tm, input) rejects. Assuming that all this can be
pinned down, and that the resulting objects exist, what will you have
achieved? HaltDecider is just as bad at deciding halting as Halts is.

--
Ben.

[Ben Bacarisse]

I was talking about your claim that "premises [...] are also self
consistent".

--
Ben.

[Ben Bacarisse]

No, of course I don't. You've never defined it. You, on the other
hand, don't seem to understand what a decision problem is. This is more
serious, because you've claimed to be taking talking about one from the
start.

--
Ben.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/28/2012 8:17 PM, Ben Bacarisse wrote:
>> I am glad, though, that you agree with my term "wrong". Let's go ahead
>> and rename
>>
>> Decidable(Halts, t, i)
>>
>> as
>>
>> GetsItWrong(Halts, t, i)
> That would be backwards, that would be Undecidable().

Why did you clip the part where I said I was inverting the condition?
Was that because you like to look as if you are scoring points rather
than having a debate?

> GetsItCorrectly() would be more apt, yet I am going to stick with
> Decidable() and DecidabilityDecider().

Of course. Despite being less than ideal, those terms carry the right
degree of obfuscation. They hint at what you want to be true.

--
Ben.

[Leif Roar Moldskred]

In comp.theory Peter Olcott <NoS...@ocr4screen.com> wrote:
>
> Within the scope of determining the validity of deductive logical
> inference premises are defined as true, like a given in geometry.

No, _axioms_ are defined to be true. _Premises_ can be true or
false.

The logical argument "Socrates is a man and all men are immortal, thus
Socrates is immortal" consists of a conclusion, "Socrates is
immortal", one true premise "Socrates is a man" and one false premise
"All men are immortal."

The conclusion above is valid, in that it follows logically from the
premises. It's not _true_ though, because it is based on a flawed
premise.

--
Leif Roar Moldskred

[Patricia Shanahan]

Whether I am interested in the results derived from a given set of
axioms depends on details such as whether the axioms appear reasonable
to me, and, in particular, whether they are likely to form a consistent
system.

Your earlier comments about a contradiction between your conclusions and
Rice's Theorem strongly suggests that adding your axioms to normal
set-theory axioms results in an inconsistent system.

I am glad to have the fact that your theories depend on adding your own
axioms made explicit.

Patricia

[Leif Roar Moldskred]

In comp.theory Patricia Shanahan <pa...@acm.org> wrote:
>
> Whether I am interested in the results derived from a given set of
> axioms depends on details such as whether the axioms appear reasonable
> to me, and, in particular, whether they are likely to form a consistent
> system.

More to the point, you can't choose your own axioms when discussing
the Halting problem. You have to use the same system of mathematics as
everybody else.

--
Leif Roar Moldskred

[George Greene]

On Mar 29, 6:09 am, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> Within the scope of determining the validity of deductive logical
> inference premises are defined as true, like a given in geometry.

Not *defined* as true, but *presumed* as true.
Yes, they are defined as presumed true, but that presumption,
like the presumption of innocence in an American courtroom,
is REBUTTABLE by PROOF.
Your premises are presumed true but they are not guaranteed
to be consistent. Your (and our) presumption that your premises
are true and consistent is NOT one that you get to maintain
AFTER a contradiction or inconsistency has been PROVEN FROM them!
Indeed, that proof constitutes a proof (regardless of ANY premises) of
the DENIAL of the conjunction of your pemises!

[Peter Olcott]

So we agree on this premise could you move past this now?

[Peter Olcott]

It does not get any cases wrong, all of these cases are screened out by
the DecidabilityDecider() before they reach the HaltDecider().

[Peter Olcott]

Feel free anytime. I made no mistake here.

1) The set of possible inputs to Halts() is defined as X;
2) The subset of X such that Halts(), halts in its accept state that
mathematically maps to the input tm halting on its input T.
3) The subset of X such that Halts(), halts in its reject state that
mathematically maps to the input tm not halting on its input F.
4) (T <union> F) The Decidable inputs to Halts() D.
5) X <minus> D the undecidable inputs to Halts() (no label needed
because this is not referred to).

[Peter Olcott]

I never made a mistake on this. I did not admit to a slip.

[Peter Olcott]

It only fails to decide those cases that were artificially contrived to
make it fail, (or are otherwise erroneous) and since those cases derive
incorrect input, they can be dismissed as incorrect input in the same
way that a HaltDecider would dismiss an English Poem as neither halting
nor failing to halt.

[Peter Olcott]

On 3/29/2012 4:24 AM, Patricia Shanahan wrote:
> On 3/28/2012 4:12 PM, Peter Olcott wrote:
> ...
>> 3) The only cases that Halts() does not halt are those cases that are
>> undecidable for it.
>
> So what exactly does "undecidable for it" mean in this context? Remember
> there is exactly one possible outcome for a given TM with a given input.
>
> Suppose I have a three result {true, false, "don't know"} TM, M1, that

That is not 100% precisely literally correctly true. There is no actual
logical entailment for a "don't know" case. You are getting sloppy with
meanings here. Pathological Self-Reference does not derive any "don't
know" cases, it derives "can't say" cases, big difference.

> returns true and false for a subset of inputs for which it can provably
> correctly evaluate whether they represent a TM computation that halts,
> and returns "don't know" for all other inputs. That is something that
> can be proved to exist.
>
> I now construct a new TM, M2, that does the following:
>
> Pass its input to M1.
>
> If M1 returns true, return true.
>
> If M1 returns false, return false.
>
> If M1 returns "don't know" go into an infinite loop.

That would always be rejected by the DecidabilityDecider() as incorrect
input. The DecidabilityDecider() can not be transformed into an
instance of the Halting Problem, it simply correctly rejects this input.

[Peter Olcott]

So how would you characterize the reason why the Halting Problem can not
be solved?
It is a perfectly valid problem and computer science is just too plain
stupid to solve it?

[Peter Olcott]

On 3/29/2012 7:09 AM, Ben Bacarisse wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>
>> > On 3/28/2012 8:17 PM, Ben Bacarisse wrote:
>>> >> I am glad, though, that you agree with my term "wrong". Let's go ahead
>>> >> and rename
>>> >>
>>> >> Decidable(Halts, t, i)
>>> >>
>>> >> as
>>> >>
>>> >> GetsItWrong(Halts, t, i)
>> > That would be backwards, that would be Undecidable().
> Why did you clip the part where I said I was inverting the condition?
> Was that because you like to look as if you are scoring points rather
> than having a debate?

I have very little time in the morning and simply missed this part.

>> > GetsItCorrectly() would be more apt, yet I am going to stick with
>> > Decidable() and DecidabilityDecider().
> Of course. Despite being less than ideal, those terms carry the right
> degree of obfuscation. They hint at what you want to be true.

I have defined these sets with complete precision many times, you are
just trying to be difficult.

[Peter Olcott]

On 3/29/2012 7:32 AM, Leif Roar Moldskred wrote:
> In comp.theory Peter Olcott<NoS...@ocr4screen.com> wrote:
>> >
>> > Within the scope of determining the validity of deductive logical
>> > inference premises are defined as true, like a given in geometry.

> No,_axioms_ are defined to be true._Premises_ can be true or
> false.
Only when one examines the soundness of reasoning are the truth of the
premises considered, when evaluating validity premises are always taken
to be true.

[Peter Olcott]

On 3/29/2012 9:00 AM, Patricia Shanahan wrote:
> Peter Olcott wrote:
>> On 3/28/2012 8:02 PM, Ben Bacarisse wrote:
>>>>>>>>> >>>> >> If you mean "This function works correctly for all
>>>>>>>>> input cases that have
>>>>>>>>> >>>> >> a correct true/false answer" then no such machine
>>>>>>>>> or function exists.
>>>>>>> >>> > It you payed better attention you would have seen that
>>>>>>> I already
>>>>>>> >>> > specified the third alternative of undecidable inputs.
>>>>> >> Yes, but I am asking you to tell me the specification of Halts.
>>>> > You did not yet get to the reasoning, you are still on the
>>>> premises.
>>>> > Premises are defined as true, and they are also self consistent.
>>> That's not true. You need to add some reading in logic to your list.
>> Within the scope of determining the validity of deductive logical
>> inference premises are defined as true, like a given in geometry.
>
> Whether I am interested in the results derived from a given set of
> axioms depends on details such as whether the axioms appear reasonable
> to me, and, in particular, whether they are likely to form a consistent
> system.

We already agreed on the main premise, the three value halt decider.
It always correctly determines halting or failing to halt except in
those cases where this is not possible.

The DecidabilityDecider() screens out these cases as incorrect input.

enum Boolean(true, false, neither);

Boolean HaltDecider(String tm, String input)
{
if (Decidable(Halts, tm, input))

if Halts(tm, input))

return true;
else
return false;
else

return neither; // meaning that the input is incorrect
}

[Peter Olcott]

Ultimately the entire set of all of the truth of mathematics has been
fully self-contained within tautologies that existed long before the
beginning of time.

[Patricia Shanahan]

On 3/29/2012 3:12 PM, Peter Olcott wrote:
> On 3/28/2012 9:28 PM, Patricia Shanahan wrote:

...

>> Grant me an incorrect or sufficiently confused premise, and I could
>> prove anything. If I don't understand and agree with the premise, I
>> don't care what conclusions can be drawn from it.
>>
>> Patricia
> So we agree on this premise could you move past this now?

In a sense. One of the few things keeping me in this thread was
curiosity as two whether the stated contradiction between your ideas and
Rice's Theorem was due to muddled thinking or extra axioms leading to an
inconsistent system.

Now I know that you are introducing your own axioms, I am reasonably
sure that inconsistent axioms are a factor.

Given inconsistent axioms, the quality of reasoning is irrelevant.

Bye,

Patricia

[Peter Olcott]

On 3/29/2012 6:10 PM, Patricia Shanahan wrote:
> On 3/29/2012 3:12 PM, Peter Olcott wrote:
>> On 3/28/2012 9:28 PM, Patricia Shanahan wrote:
> ...
>>> Grant me an incorrect or sufficiently confused premise, and I could
>>> prove anything. If I don't understand and agree with the premise, I
>>> don't care what conclusions can be drawn from it.
>>>
>>> Patricia
>> So we agree on this premise could you move past this now?
>
> In a sense. One of the few things keeping me in this thread was
> curiosity as two whether the stated contradiction between your ideas and
> Rice's Theorem was due to muddled thinking or extra axioms leading to an
> inconsistent system.

I am still working on better ways to express these ideas. To do this I
am more deeply grounding myself within the conventional terminology and
concepts of the theory of computation.

I think that I may have found a non-trivial property of a
recursively-enumerable set that is decidable.

Since Rice's Theorem states that:
Every nontrivial property of a recursively-enumerable set is
undecidable, my finding (if correct) would disprove Rice's Theorem.

[George Greene]

On Mar 29, 6:35 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> It is a perfectly valid problem and computer science is just too plain
> stupid to solve it?

Well, yes, basically, but this is not any cause for calling anything
"stupid".
And "computer science" is too broad a term. THE TM PARADIGM
is too stupid to solve it. But there are analogues. Peano Arithmetic
proves a lot of truths about natural numbers but it cannot prove the
statement about them that arguably encodes "Peano Arithmetic is
consistent".
ZFC provds a lot of truths about sets but it cannot prove "ZFC is
consistent".
Basically, there are only a countable number of TMs (and therefore
only a countably infinite number of sets that TMs could produce) but
there are UNcountably many 1st-order predicates (infinitely long bit-
strings).

[George Greene]

On Mar 29, 6:35 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:

> So how would you characterize the reason why the Halting Problem can not
> be solved?
> It is a perfectly valid problem and computer science is just too plain
> stupid to solve it?

EVERY problem-solving system is "too stupid" to solve certain
kinds of hard problems. Once an (infinite) system achieves
a certain level of complexity, it can only be analyzed by a MORE
complex system. Essentially, for EVERY program, there is a SMARTER
program (just as for every number, there is a bigger number).
You basically cannot analyze a program's halting behavior (IN GENERAL,
OVER ALL of its INFINITELY many possible inputs) unless you are
"smarter than" that program. Once you write a program, even if it
is a very smart halt-analyzer, there is clearly a more complex program
that it will not be able to analyze. The fact that the easiest
examples of
a harder program involve self-reference is not really important,
because
HERE is ANOTHER undecidable problem:
Same(m1,m2) : If m1 and m2 are strings describing 2 different TMs,
return true if these different TMs produce the same output for every
input, and fail to produce any output (i.e. loop) on the same set of
inputs.
Since you cannot write a TM that does this, you also
canNOT write a TM that "Recognizes" self-reference, because
there are TWO DIFFERENT WAYS (actually infinitely many different ways)
of string-encoding the SAME TM behavior, and a TM that does NOT have
the identical string-code of its caller, callee, or analyzee, and will
therefore NOT be recognized as referring to "itself", will STILL run
into ALL THE SAME PROBLEMS PRODUCED BY "referring to itself" IF it is
referring to some DIFFERENT tm that HAS THE SAME input/output/halting
behavior.

[Joshua Cranmer]

On 3/29/2012 5:22 PM, Peter Olcott wrote:
> On 3/28/2012 9:41 PM, Ben Bacarisse wrote:
>> Peter Olcott<NoS...@OCR4Screen.com> writes:
>>
>>> On 3/28/2012 5:29 AM, Ben Bacarisse wrote:
>>>> Now, T union F is just the set of inputs
>>>> on which Halts halts. The "decidability decider" must just decide the
>>>> complement of that set. It is, in effect, a halt decider. Is this just
>>>> a mistake, or have you changed your mind?
>>> T<union> F is the inputs which Halts correctly decides.
>> Right. So it was just a mistake on your behalf. I note that you
>> snipped your incorrect definition:
>>
>> | The set of elements of<sigma>* that Halts() halts in its accept state T
>> | The set of elements of<sigma>* that Halts() halts in its reject state F
>> | (T<union> F) derives the set named Decidable
>>
>> It would help if you sometimes just said "yes, that was a slip".
>>
>> <snip>
>
> Feel free anytime. I made no mistake here.

You seem to treat the two definitions in this post as exactly
equivalent, but they are not. One definition is the set which of inputs
for which a given Turing machine returns the same answer as the halting
function, while the other is the set of inputs for which a given Turing
machine halts on.

If you still don't believe that these two definitions are different,
here's an easy test case. Suppose we implement Halts like so:
Halts(M, w) -> unconditionally accept.

Which of the following sets would you call "Decidable"?
A. All input pairs {M, w}
B. All input pairs {M, w} such that M halts when input with w fed as input.

Set A would correspond to the definition of T union F, while set B
corresponds to the definition of the inputs that Halts correctly
decides. These two sets are clearly not equivalent, so you are clearly
giving two contradictory definitions here. Assuming that you did not
intend a contradiction in your premise [1], you made a mistake.

[1] It's always possible that this is what you intended, but since a
contradiction proves anything, it's completely tautological nonsense.

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

[Joshua Cranmer]

On 3/29/2012 5:35 PM, Peter Olcott wrote:
> So how would you characterize the reason why the Halting Problem can not
> be solved?
> It is a perfectly valid problem and computer science is just too plain
> stupid to solve it?

Mathematics is simply not complete. That's one way. Another way is (this
is very informal) to note that any sufficiently complex structure is
ultimately finite, while general techniques are infinite in complexity,
so it is impossible to build a structure which is totally
impregnable--the fact that you can build a machine implies that you must
be able to defeat it somehow. A better explanation of this can be found
in the chapter on the record player in the book Godel, Escher, Bach.

[Joshua Cranmer]

On 3/29/2012 5:26 PM, Peter Olcott wrote:
> It only fails to decide those cases that were artificially contrived to
> make it fail, (or are otherwise erroneous) and since those cases derive
> incorrect input, they can be dismissed as incorrect input in the same
> way that a HaltDecider would dismiss an English Poem as neither halting
> nor failing to halt.

What defines an "artificially contrived" case? I'm guessing you intend
to mean "unrealistic input", but, in many cases, artificially-crafted
inputs are just as important to worry about as typical input. Note that
nearly every security problem in modern computers arises from failures
in artificially crafted cases: SQL injections, buffer overflows, etc. In
a more practical sense, the fact that it is possible to craft instances
that force quicksort to regress to O(n^2) time make it an unacceptable
algorithm in many places.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/28/2012 9:34 PM, Ben Bacarisse wrote:
>> Peter Olcott<NoS...@OCR4Screen.com> writes:

<snip>

>>> Bug free means that:
>>> 1) Whenever Halts() halts in its accept state its input tm would halt
>>> on its input.
>>> 2) Whenever Halts() halts in its reject state its input tm would not
>>> halt on its input.
>>> 3) The only cases that Halts() does not halt are those cases that are
>>> undecidable for it.

<snip>

>>> Is there anything at all that "bug-free" could possibly correctly mean
>>> besides the above specification?
>> Yes, of course. The natural meaning is of a correct halting decider.
>> Yours is of a partially correct one with an unspecified number of cases
>> that it is permitted to get wrong. That's not the obvious meaning of
>> "bug-free".
>>
> It does not get any cases wrong, all of these cases are screened out
> by the DecidabilityDecider() before they reach the HaltDecider().

This is becoming absurd. You can't even keep track of your own
definitions. Your "bug-free" requirement was made of the machine whose
inputs are to be "screened out".

--
Ben.

[Ben Bacarisse]

You don't see that difference? Of course you do. You must do, because
you've added the crucial parts back using new words.

--
Ben.

[Ben Bacarisse]

<sigh> It's not the same at all. Those "contrived" inputs represent
machine and input pairs that have correct true/false answers to the
question that a halting decider must answer.

--
Ben.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/29/2012 4:24 AM, Patricia Shanahan wrote:
>> On 3/28/2012 4:12 PM, Peter Olcott wrote:
>> ...
>>> 3) The only cases that Halts() does not halt are those cases that are
>>> undecidable for it.
>>
>> So what exactly does "undecidable for it" mean in this context? Remember
>> there is exactly one possible outcome for a given TM with a given input.
>>
>> Suppose I have a three result {true, false, "don't know"} TM, M1, that
>
> That is not 100% precisely literally correctly true. There is no
> actual logical entailment for a "don't know" case. You are getting
> sloppy with meanings here. Pathological Self-Reference does not derive
> any "don't know" cases, it derives "can't say" cases, big difference.

You must allow other people to state *their* premises. In this case it
is perfectly fine to suppose such a machines exist -- they clearly do.
If you don't like the term "don't know", just assume that M1 returns
result from the set {true, false, banana}.

>> returns true and false for a subset of inputs for which it can provably
>> correctly evaluate whether they represent a TM computation that halts,
>> and returns "don't know" for all other inputs. That is something that
>> can be proved to exist.

"...and returns 'banana' for all other inputs."

>> I now construct a new TM, M2, that does the following:
>>
>> Pass its input to M1.
>>
>> If M1 returns true, return true.
>>
>> If M1 returns false, return false.
>>
>> If M1 returns "don't know" go into an infinite loop.

"If M1 returns 'banana' go into an infinite loop."

> That would always be rejected by the DecidabilityDecider() as
> incorrect input. The DecidabilityDecider() can not be transformed
> into an instance of the Halting Problem, it simply correctly rejects
> this input.

Total nonsense. There is no attempt here to reduce anything to halting,
and there is no "DecidabilityDecider" in sight here. The question is
about whether a machine is or is not "bug-free". It is just an attempt
to clarify this term that you've introduced.

>> Is M2 bug-free? If not, why not?

As with so many of Patricia's questions, it's a good one and I urge you
not to ignore it.

--
Ben.

[Ben Bacarisse]

There are several way to look at it. It is natural that there must be
many functions that can't be computed by any Turing machine simply
because there are only countably many Turing machines, but there are
uncountably many functions from input strings to {true, false} (to pick
just an interesting subset of functions).

Why is halting, specifically, one of these? The argument that proves
that halting is not decidable is also a diagonalisation argument,
exactly like Cantor's argument about the power set of N. Because you've
stripped out the details of the encoding from all your arguments (and
because you've decided the result before you start) you haven't absorbed
the nature of the proof. There aren't enough natural numbers to encode
a single machine that can decide halting.

> It is a perfectly valid problem and computer science is just too plain
> stupid to solve it?

Computer science has solved it, in that it is now a settled question.
It's only unsolved for people who want a different answer.


--
Ben.

[George Greene]

On Mar 29, 9:10 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> It's not the same at all.  Those "contrived" inputs represent
> machine and input pairs that have correct true/false answers to the
> question that a halting decider must answer.

Not necessarily, at least not according to Peter.
This is why YOU HAVE TO STOP using Peter's terms for things.
THE PEDAGOGICALLY CORRECT response to Peter's EVERY use
of a private definition is to whack him with "you're STILL IGNORANT
of the CORRECT definition of that term". By the correct definition of
"decider", a halting decider DOES NOT EXIST, so claims about what it
"must do" are sort of precluded. Peter has been talking ALL ALONG
about a PUTATIVE halt decider, about a program that comes, BUILT IN,
WITH
an INTENDED PURPOSE that it achieves AT LEAST A MODICUM of the time.

The fact that such a beast has nothing whatsoever in common with TMs
(even when it "is" one) is the thing he is having trouble seeing.
You have
to force him to talk about EXISTING TMs AS OPPOSED to SPECIFICATIONS
of TMs.

Essentially we have crafted a language for describing first-order
predicates that
can describe predicates that TMs can't compute. But because there
are a great
many predicates that TMs CAN computer, P.O. has no idea, just from
looking at
a predicate, WHICH KIND IT IS. He thinks that "a TM whose goal/
mission/purpose specification is to compute predicate P(.)"
IS A VALID DESCRIPTION/CONSTRAINT FOR A TM, in ALL cases -- possibly
even the Russellian one of
"a TM that halts on all and only those TMs that don't halt on
themselves".
Precisely as you have already said, he thinks he can "define a TM to
do whatever he wants it to",
AND DOESN'T EVEN NOTICE THE IRONY in this. Seriously, he did not even
perceive that
you were accusing him of overreaching when you said this.

[Peter Olcott]

You are back to striving to be disagreeable again, I see.

[Peter Olcott]

There is no significant difference, what was not stated before was
logically entailed, thus equivalent to being stated.

[Peter Olcott]

You still did not answer my similar question:
What time is it (yes or no) ???

[Peter Olcott]

These are the three possible cases, they are all inclusive.
1) The halt decider halts in its accept state only when the input tm

would halt on its input.

2) The halt decider halts in its reject state only when the input tm

would not halt on its input.

3) The halt decider loops on its input in the all of the cases where it
can not correctly halt in either its accept state or its reject state.
It does not loop in any other cases.

[George Greene]

On Mar 29, 6:26 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> It only fails to decide those cases that were artificially contrived to
> make it fail, (or are otherwise erroneous) and since those cases derive
> incorrect input,

There IS NO SUCH THING as "incorrect input", once the input is a TM.
All TMs are correctly classed as TMs. They can't be incorrect as JUST
BEING TMs.

> they can be dismissed as incorrect input in the same
> way that a HaltDecider would dismiss an English Poem as neither halting
> nor failing to halt.

No, it's NOT in the SAME way, because it REALLY IS TRUE that an
English poem
"neither halts nor fails to halt on most inputs" -- what could the
input to an English
poem EVEN BE -- but it is NOT true, for ANY tm, that it neither halts
nor fails to
halt on an input. THERE ARE NO "undecidable" INDIVIDUAL cases of
halts(m,i).
There are cases of PO's_lame_ATTEMPT_at_halt_analyzer(m,i) where the
analyzer
GETS IT WRONG, but there ARE NO cases where m neither halts nor fails
to halt on i.
If m is a TM -- ANY tm -- then IT ALWAYS either halts or fails to
halt ON EVERY input,
whether any OTHER tm can see this OR NOT.

[Peter Olcott]

On 3/29/2012 8:29 PM, Joshua Cranmer wrote:
> On 3/29/2012 5:35 PM, Peter Olcott wrote:
>> So how would you characterize the reason why the Halting Problem can not
>> be solved?
>> It is a perfectly valid problem and computer science is just too plain
>> stupid to solve it?
>
> Mathematics is simply not complete.

Yeah that is what Godel incorrectly proposed.

[George Greene]

> > Mathematics is simply not complete.

On Mar 29, 11:31 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> Yeah that is what Godel incorrectly proposed.

??

Are we being trolled?

[George Greene]

On Mar 29, 9:49 pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> What defines an "artificially contrived" case? I'm guessing you intend
> to mean "unrealistic input"

All the paradoxical cases we have presented him so far involve self-
reference that
is "transparent",that is inspectible in the code-string we are
presenting
as the machine-identifying argument.

What he doesn't understand is that we could pass, as the machine,
ANOTHER TM that had THE SAME input/output/halting BEHAVIOR.
This would cause all the same problems as the blatant self-reference
(that he thinks he can "see" and therefore exclude), BUT IT WOULD BE
"OPAQUE".
He wouldn't be ABLE TO TELL that self-reference, let alone
pathological self-
reference, was happening at all. He would just be unable to analyze.
This would
be a case that was "undecidable for" his putative halt-analyzer (it
would loop on this case,
or possibly even get it wrong), because he wouldn't be able to
recognize it as needing to
be excluded.

[George Greene]

On Mar 29, 9:24 pm, Joshua Cranmer <Pidgeo...@verizon.invalid> wrote:
> B. All input pairs {M, w} such that M halts when input with w fed as input.
>
> Set A would correspond to the definition of T union F, while set B
> corresponds to the definition of the inputs that Halts correctly
> decides. These two sets are clearly not equivalent, so you are clearly
> giving two contradictory definitions here. Assuming that you did not
> intend a contradiction in your premise [1], you made a mistake.

The mistake he made is one that people make all the time in stating
these
definitions, namely, the mistake of saying "when"(or "whenever", or
"if")
instead of "if AND ONLY if".
He just needs the other direction as well in order to mean something
that
would make sense. Assuming he meant B., I gave the example of the
machine that halts/accept on the pair {H,w} where H is the machine
that always halts
(and w is anything), and halts/reject on the pair {L,w} where L is the
machine that
always loops. This machine fails to decide (i.e. loops on) ALL other
m,i pairs.
But it NEVER answers WRONGLY so it is/was "bug-free" by P.O.'s
criteria as
originally stated. There are many simple confirmable halting and non-
halting cases
where this machine would be obligated to halt if it were going to be a
GOOD "halt-
analyzer". But since he already conceded that you can't be perfect
anyway, how
is anyone, even he(P.O.)himself, going to say how bad it has to get
before it's TOO bad?
As long as you don't get one WRONG(when you DO halt), I mean.

[Joshua Cranmer]

On 3/29/2012 10:25 PM, Peter Olcott wrote:
> On 3/29/2012 8:24 PM, Joshua Cranmer wrote:
>> You seem to treat the two definitions in this post as exactly
>> equivalent, but they are not. One definition is the set which of
>> inputs for which a given Turing machine returns the same answer as the
>> halting function, while the other is the set of inputs for which a
>> given Turing machine halts on.
>
> These are the three possible cases, they are all inclusive.

Could you answer my question? You're still being stubbornly unclear in
your responses. Here it is again:

> Suppose we implement Halts like so:
> Halts(M, w) -> unconditionally accept.
>
> Which of the following sets would you call "Decidable"?
> A. All input pairs {M, w}
> B. All input pairs {M, w} such that M halts when input with w fed as input.

[Joshua Cranmer]

Says the person who is giving multiple inconsistent definitions, has
explicitly stated that he ignores long posts, and instructs his
opponents to take his word on everything.

[Joshua Cranmer]

You don't even have to go so far as Godel: there must exist uncomputable
functions since there are 2^Aleph_0 functions but only Aleph_1 programs,
so it is not possible to construct a bijection between functions and
programs which compute them.

[Peter Olcott]

On 3/29/2012 11:48 PM, Joshua Cranmer wrote:
> On 3/29/2012 10:25 PM, Peter Olcott wrote:
>> On 3/29/2012 8:24 PM, Joshua Cranmer wrote:
>>> You seem to treat the two definitions in this post as exactly
>>> equivalent, but they are not. One definition is the set which of
>>> inputs for which a given Turing machine returns the same answer as the
>>> halting function, while the other is the set of inputs for which a
>>> given Turing machine halts on.
>>
>> These are the three possible cases, they are all inclusive.
>
> Could you answer my question? You're still being stubbornly unclear in
> your responses. Here it is again:
>
>> Suppose we implement Halts like so:
>> Halts(M, w) -> unconditionally accept.
>>
>> Which of the following sets would you call "Decidable"?
>> A. All input pairs {M, w}
>> B. All input pairs {M, w} such that M halts when input with w fed as
>> input.
>

1) In the case where Halts() halts in its accept state, where M would
halt on its input w, this would be decidable.
2) In the case where Halts() halts in its reject state, where M would
not halt on its input w, this would be decidable.
3) In the case where Halts() can not correctly halt in either its accept
state or its reject state this would be undecidable.

I think that 1) corresponds to B.

[Peter Olcott]

On 3/29/2012 11:52 PM, Joshua Cranmer wrote:
> On 3/29/2012 10:16 PM, Peter Olcott wrote:
>> On 3/29/2012 7:43 PM, Ben Bacarisse wrote:
>>> This is becoming absurd. You can't even keep track of your own
>>> definitions. Your "bug-free" requirement was made of the machine whose
>>> inputs are to be "screened out".
>>>
>> You are back to striving to be disagreeable again, I see.
>
> Says the person who is giving multiple inconsistent definitions, has
> explicitly stated that he ignores long posts, and instructs his
> opponents to take his word on everything.

See you just proved it by using the term opponent. None of my
definitions have been inconsistent at all, and I can't see why the first
versions of these definitions are not obviously clear.

[Peter Olcott]

On 3/29/2012 11:55 PM, Joshua Cranmer wrote:
> On 3/29/2012 10:31 PM, Peter Olcott wrote:
>> On 3/29/2012 8:29 PM, Joshua Cranmer wrote:
>>> On 3/29/2012 5:35 PM, Peter Olcott wrote:
>>>> So how would you characterize the reason why the Halting Problem
>>>> can not
>>>> be solved?
>>>> It is a perfectly valid problem and computer science is just too plain
>>>> stupid to solve it?
>>>
>>> Mathematics is simply not complete.
>> Yeah that is what Godel incorrectly proposed.
>
> You don't even have to go so far as Godel: there must exist
> uncomputable functions since there are 2^Aleph_0 functions but only
> Aleph_1 programs, so it is not possible to construct a bijection
> between functions and programs which compute them.

I have to learn more math to understand that.

[Ben Bacarisse]

Peter Olcott <NoS...@OCR4Screen.com> writes:

> On 3/29/2012 8:29 PM, Joshua Cranmer wrote:

<snip>

>> Mathematics is simply not complete.
> Yeah that is what Godel incorrectly proposed.

Ah. It's getting clearer... Rice, Turing, Gödel... I'll bet Cantor
either is, or will soon be, on your list of mathematicians who've made
big mistakes.

--
Ben.

[Peter Olcott]

No only the cases that depend upon Pathological Self-Reference.

[Peter Olcott]

On 3/29/2012 8:29 PM, Joshua Cranmer wrote:

> On 3/29/2012 5:35 PM, Peter Olcott wrote:
>> So how would you characterize the reason why the Halting Problem can not
>> be solved?
>> It is a perfectly valid problem and computer science is just too plain
>> stupid to solve it?
>
> Mathematics is simply not complete.

That answer is far too vague. Exactly what is not complete about
mathematics it within the specific instance of the halting problem?

[Peter Olcott]

So I will have to explain Pathological Self-Reference in terms of the
diagonalization.
I will get back to you on this.

[Ben Bacarisse]

We are at an impasse and I am not sure there is any way to move forward.
When pressed, you refused to say whether you agree that all questions of
the form "does machine t halt on input i" have correct yes/no answers.
That's telling. I suspect that you are, by now, too committed to the
idea that there are "invalid halting questions" to accept this plain
fact. Questions like "what time is it, yes or no?" don't have correct
yes/no answers, so to call it a "similar" question seems disingenuous,
at best.

I am curious to know what you think about other non-computable
functions. For example, the Busy Beaver function[1] has been shown not
to be computable without using a reduction to halting, and I can't see
any way you could imagine that some inputs to it are invalid. Is it
*only* halting that bothers you so much?

[1] BB(n) is a function from the natural numbers to the natural numbers.
It's the maximum number of 1s that an n-state TM can leave on it's tape
when (and if) it halts. Some values are know: BB(1) = 1, BB(2) = 4,
BB(3) = 6 and BB(4) = 13, but that's it so far.

--
Ben.

[Ben Bacarisse]

You've made being "bug-free" a crucial criterion for the existence of
what you call a "DecidabilityDecider". The only definition you've given
so far relies on the definition of cases that are "undecidable". By
choosing to be offended you've avoided clearing up this ambiguity. By
all means, continue to be offended, but you won't make any headway
unless you answer these points.

--
Ben.

[Joshua Cranmer]

Did you not read the following sentences I wrote?