InvalidInput Decider 2012-05-02

[Peter Olcott]

Halts(tm, input) // The semantic meaning that tm actually halts on input
<ProperSubset> mathematical symbol indicating proper subset

Boolean Halting(String tm, String input)
The domain of Halting (for the value of tm) is based on
(a) Sigma*
(b) <ProperSubset> (a) That represent valid Turing Machines.
(c) <ProperSubset> (b) That halt on input
(d) <ProperSubset> (c) That Halting() returns true.
Halting() returns true on set (d) and returns false on everything else.

If Halting(tm, input) returning true would not make Halts(tm, input)
false, then Halting(tm, input) must return true.

Boolean NotHalting(String tm, String input)
The domain of NotHalting (for the value of tm) is based on
(a) Sigma*
(b) <ProperSubset> (a) That represent valid Turing Machines.
(c) <ProperSubset> (b) That do not halt on input.
(d) <ProperSubset> (c) That NotHalting() returns true.
NotHalting() returns true on set (d) and returns false on everything else.
If NotHalting(tm, input) returning true would not make !Halts(tm, input)
false, then NotHalting(tm, input) must return true.

Boolean InvalidInput(String tm String input)
{
if (!Halting(tm, input) && !NotHalting(tm, input))
return true;
else
return false;
}

The InvalidInput Decider correctly decides the property of InvalidInput
for the set of all Strings.

This would seem to exactly refute what Dexter Kozen provides as the
specification of Rice's Theorem: "Every nontrivial property of the r.e.
sets is undecidable". (page 245, 1997 edition of Automata and
Computability).

[Ben Bacarisse]

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

> Halts(tm, input) // The semantic meaning that tm actually halts on input
> <ProperSubset> mathematical symbol indicating proper subset

I suggest you lower-case for functions and keep initial upper-case for
sets and machines. Too late now, but you've used Halts to mean other
things before, and it's very similar to other names you've used for
machines. Maybe next time round?

> Boolean Halting(String tm, String input)
> The domain of Halting (for the value of tm) is based on

What's the point of taking a term that has an agreed meaning (domain)
and inventing a new meaning for it? You don't need the term at all (you
don't refer to it again) -- all you need is the set (d).

> (a) Sigma*
> (b) <ProperSubset> (a) That represent valid Turing Machines.
> (c) <ProperSubset> (b) That halt on input
> (d) <ProperSubset> (c) That Halting() returns true.
> Halting() returns true on set (d) and returns false on everything else.
>
> If Halting(tm, input) returning true would not make Halts(tm, input)
> false, then Halting(tm, input) must return true.

It was all going fine right up to "would not make". Nothing Halting(tm,
input) does can "make" Halts(tm, input) be anything other than it is.
Do you mean that Halting(tm, input) => Halts(tm, input)? Probably not.

Why not just tabulate the cases? For every element of (d) Halting
either must, or may, return either true or false. Halts is simpler. It
is either true or false for all elements of (d) (well, for the machine
computations that the elements of (d) represent) so you could specify
Halting using a table:

Halts(tm, input) Halting(tm, input) Allowed? Required?
true true yes ?
true false ? ?
false true ? ?
false false ? ?

This is not a quibble. It is exactly your inability to say what you mean
that keeps these threads going. As Daryl has said, once you say what
you mean, I think it will be clear that you are mistaken.

> Boolean NotHalting(String tm, String input)
> The domain of NotHalting (for the value of tm) is based on
> (a) Sigma*
> (b) <ProperSubset> (a) That represent valid Turing Machines.
> (c) <ProperSubset> (b) That do not halt on input.
> (d) <ProperSubset> (c) That NotHalting() returns true.
> NotHalting() returns true on set (d) and returns false on everything else.
> If NotHalting(tm, input) returning true would not make !Halts(tm,
> input) false, then NotHalting(tm, input) must return true.

Fixing the above will immediately fix this part.

<snip>
--
Ben.

[Joshua Cranmer]

On 5/2/2012 7:34 PM, Peter Olcott wrote:
> Halts(tm, input) // The semantic meaning that tm actually halts on input
> <ProperSubset> mathematical symbol indicating proper subset
>
> Boolean Halting(String tm, String input)
> The domain of Halting (for the value of tm) is based on
> (a) Sigma*
> (b) <ProperSubset> (a) That represent valid Turing Machines.
> (c) <ProperSubset> (b) That halt on input
> (d) <ProperSubset> (c) That Halting() returns true.
> Halting() returns true on set (d) and returns false on everything else.

This is an inherently circular definition: Halting returns true for
those values that it returns true.

> Boolean NotHalting(String tm, String input)
> The domain of NotHalting (for the value of tm) is based on
> (a) Sigma*
> (b) <ProperSubset> (a) That represent valid Turing Machines.
> (c) <ProperSubset> (b) That do not halt on input.
> (d) <ProperSubset> (c) That NotHalting() returns true.
> NotHalting() returns true on set (d) and returns false on everything else.

Similarly here.

> Boolean InvalidInput(String tm String input)
> {
> if (!Halting(tm, input) && !NotHalting(tm, input))
> return true;
> else
> return false;
> }
>
> The InvalidInput Decider correctly decides the property of InvalidInput
> for the set of all Strings.

Note that this is conditional on what the sets Halting and NotHalting
actually comprise. Since the latter sets are defined circularly, there
exist a large number of possible "instantiations" of this function.

> This would seem to exactly refute what Dexter Kozen provides as the
> specification of Rice's Theorem: "Every nontrivial property of the r.e.
> sets is undecidable". (page 245, 1997 edition of Automata and
> Computability).

Not so fast. You have several caveats that you have to make first:
1. You need to define Halting/NotHalting in a rigorous, non-circular manner.
2. You need to show that the above definition is actually decidable
3. You need to show that the resulting InvalidInput actually decides a
nontrivial property: i.e., that if L(M1) = L(M2), then InvalidInput(M1)
= InvalidInput(M2).

Note that all of my experience indicates that #3 will fail to hold. More
generally, any static halting analyzer necessarily finds that it is
possible to munge a machine that halts to become unanalyzable without
changing the result at all.

If you actually try to build any of the machines in question, you will
discover why your claims of refutation of Rice's Theorem are just plain
wrong.

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

[George Greene]

On May 2, 8:34 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:
> Halts(tm, input)  // The semantic meaning that tm actually halts on input
> <ProperSubset> mathematical symbol indicating proper subset
>
> Boolean Halting(String tm, String input)
> The domain of Halting (for the value of tm) is based on
> (a) Sigma*
> (b) <ProperSubset> (a) That represent valid Turing Machines.
> (c) <ProperSubset> (b) That halt on input
> (d) <ProperSubset> (c) That Halting() returns true.
> Halting() returns true on set (d) and returns false on everything else.

This means that Halting() is NOT "bug-free" according to your earlier
definition of THAT term: the fact that (d) is a proper subset of (c)
implies that there will be some elements of (c) that are strings
denoting valid tm,input pairs for which the tm DOES Halt on the input
but for which Halting() RETURNS FALSE.

> If Halting(tm, input) returning true would not make Halts(tm, input) false, then Halting(tm, input) must return true.

I'm sorry; that is incoherent; nothing ever MAKES tm's DO anything
EXCEPT *their own* code. The issue isn't what Halting() would "make
Halts" do.
The issue is whether the TM does or doesn't halt on the input. The
problematic program in question,
M(h,i) : If h(i,i) Then Loop Else Halt.
has the property that NO MATTER WHAT h is, h IS ALWAYS WRONG about
halting of THIS program. Even when h loops, it is STILL wrong because
Halts() would've returned FALSE in that case. This doesn't mean that h
is MAKING something happen, since EVEN IF IT WAS A COMPLETELY
DIFFERENT h, THE SAME THING would still be happening. The fact that h
disagrees with Halts() IS INdependent of h, because it happens FOR
EVERY h.

[George Greene]

On May 2, 8:34 pm, Peter Olcott <NoS...@OCR4Screen.com> wrote:

> If Halting(tm, input) returning true would not make Halts(tm, input)
> false, then Halting(tm, input) must return true.

Even though it is not always right, Halting() has the advantage that
it AT LEAST EXISTS; it IS a TM.

> Boolean NotHalting(String tm, String input)
> The domain of NotHalting (for the value of tm) is based on
> (a) Sigma*
> (b) <ProperSubset> (a) That represent valid Turing Machines.
> (c) <ProperSubset> (b) That do not halt on input.
> (d) <ProperSubset> (c) That NotHalting() returns true.

(d) here is the problematic subset. NotHalting() CANNOT ACTUALLY DO
this,
except in a SMALL number of cases (even if it is infinitely many, it
is still only
one narrow family of cases). This is something that TMs IN GENERAL
ARE NOT
smart enough to do. YOU DO NOT KNOW HOW to write a NotHalting() TM
that halts (and returns true) on M,I pairs where M does not halt on I.
But don't feel bad; NEITHER DOES ANYBODY ELSE, because such TMs for
the
most part DO NOT EXIST. The one that comes closest just returns true
on everything;
that way, it knows it gets all the truly NonHalting cases right. The
fact that it gets
everything else is wrong is sort of irrelevant since you Already Have
Halting() to check THAT case.

[Ben Bacarisse]

Ben Bacarisse <ben.u...@bsb.me.uk> writes:
<snip>

>> (d) <ProperSubset> (c) That Halting() returns true.
>> Halting() returns true on set (d) and returns false on everything else.
>>
>> If Halting(tm, input) returning true would not make Halts(tm, input)
>> false, then Halting(tm, input) must return true.
>
> It was all going fine right up to "would not make". Nothing Halting(tm,
> input) does can "make" Halts(tm, input) be anything other than it is.
> Do you mean that Halting(tm, input) => Halts(tm, input)? Probably not.
>
> Why not just tabulate the cases? For every element of (d) Halting
> either must, or may, return either true or false. Halts is simpler. It
> is either true or false for all elements of (d) (well, for the machine
> computations that the elements of (d) represent) so you could specify
> Halting using a table:

Sorry, I don't mean (d). Obviously I mean the set of inputs on which
Halting halts. I am not sure exactly what that set is, but it sounds
from this: "Halting() returns true on set (d) and returns false on
everything else" that it's Sigma*. Whatever it is, a table would clear
up what you mean.

> Halts(tm, input) Halting(tm, input) Allowed? Required?
> true true yes ?
> true false ? ?
> false true ? ?
> false false ? ?

<snip>
--
Ben.

[Ralph Hartley]

On 05/03/2012 07:18 AM, Ben Bacarisse wrote:
> Ben Bacarisse<ben.u...@bsb.me.uk> writes:
> <snip>
>>> (d)<ProperSubset> (c) That Halting() returns true.
>>> Halting() returns true on set (d) and returns false on everything else.
>

> Why not just tabulate the cases?

The above boils down to:

Halts(tm, input) Halting(tm, input) Allowed? Required?

true true yes (W)
true false (W) no
false true no n/a
false false yes yes

and (W) depends on something other than Halts(tm, input).

>>> (W) If Halting(tm, input) returning true would not make Halts(tm, input)

>>> false, then Halting(tm, input) must return true.

>> It was all going fine right up to "would not make". Nothing Halting(tm,
>> input) does can "make" Halts(tm, input) be anything other than it is.

Right. Nor can Halting(tm, input) do anything other than what *it* does,
so it can't "make" anything happen.

That is the point he is having trouble with. All else is distraction.

He wants to use a counter factual like

(C) if Halting(tm, input) were to return true, then Halts(tm, input)
would be false

and by (W) he means

(W') if not (if Halting(tm, input) were to return true, then Halts(tm,
input) would be false), then Halting(tm, input) must return true;

But (C) makes no sense, it is like saying "if 12345 were even then 12346
would be odd".

Ralph Hartley

[Ralph Hartley]

On 05/02/2012 10:34 PM, Joshua Cranmer wrote:
> On 5/2/2012 7:34 PM, Peter Olcott wrote:
>> The InvalidInput Decider correctly decides the property of InvalidInput
>> for the set of all Strings.
>

>> This would seem to exactly refute what Dexter Kozen provides as the
>> specification of Rice's Theorem: "Every nontrivial property of the r.e.
>> sets is undecidable". (page 245, 1997 edition of Automata and
>> Computability).
>
> Not so fast. You have several caveats that you have to make first:
> 1. You need to define Halting/NotHalting in a rigorous, non-circular
> manner.
> 2. You need to show that the above definition is actually decidable
> 3. You need to show that the resulting InvalidInput actually decides a
> nontrivial property: i.e., that if L(M1) = L(M2), then InvalidInput(M1)
> = InvalidInput(M2).
>
> Note that all of my experience indicates that #3 will fail to hold.

I don't think so. His previous attempts have failed #3, but only because
he had #1 wrong. I'm convinced that the function he *really* wants
either doesn't exist even as a function (making #1 impossible), or
actually *is* a non-trivial property, and it will be #2 that fails.

Hopefully that won't drive him back to the "What color is your age" stage.

I'm giving up if that happens.

Ralph Hartley

[Joshua Cranmer]

Well, let me rephrase. If you ever actually try to think about how
Halting/NotHalting could be implemented (which tends to imply
decidability), you would be very hard-pressed to come up with a possible
implementation that decides based on a property of the language instead
of the machine.

On further reflection, Rice's Theorem does imply that you can't base any
algorithm off of nontrivial language properties, so, in a way, Peter's
decision can be boiled down to "if you assume that Rice's Theorem does
not hold, your result refutes Rice's Theorem."

[Ben Bacarisse]

Ralph Hartley <har...@aic.nrl.navy.mil> writes:

> On 05/03/2012 07:18 AM, Ben Bacarisse wrote:
>> Ben Bacarisse<ben.u...@bsb.me.uk> writes:
>> <snip>
>>>> (d)<ProperSubset> (c) That Halting() returns true.
>>>> Halting() returns true on set (d) and returns false on everything else.
>>
>> Why not just tabulate the cases?
>
> The above boils down to:
>
> Halts(tm, input) Halting(tm, input) Allowed? Required?
> true true yes (W)
> true false (W) no
> false true no n/a
> false false yes yes
>
> and (W) depends on something other than Halts(tm, input).

Thanks. I saw that you had been carefully trying to extract the same
information from Peter in another sub-thread but I found his replies
less than clear there as well.

>>>> (W) If Halting(tm, input) returning true would not make Halts(tm, input)
>>>> false, then Halting(tm, input) must return true.
>
>>> It was all going fine right up to "would not make". Nothing Halting(tm,
>>> input) does can "make" Halts(tm, input) be anything other than it is.
>
> Right. Nor can Halting(tm, input) do anything other than what *it*
> does, so it can't "make" anything happen.
>
> That is the point he is having trouble with. All else is distraction.
>
> He wants to use a counter factual like
>
> (C) if Halting(tm, input) were to return true, then Halts(tm, input)
> would be false
>
> and by (W) he means
>
> (W') if not (if Halting(tm, input) were to return true, then Halts(tm,
> input) would be false), then Halting(tm, input) must return true;

Goodness. I'd never have extracted that from his wording. This W' has
no meaning as far as I can see. Presumably you find no meaning in it
either.

> But (C) makes no sense, it is like saying "if 12345 were even then
> 12346 would be odd".

I'm not sure I see this analogy. I can read "were" and "would" here as
if there were simple predicates to get a true statement:

Even(12345) -> Odd(12346)

but I can't do that with C (at least, if I do, I don't get the same sort
of true statement).

The "would", "were" and "must" in your C and W' must mean more than this
or you would not say that the (W) in the table depends on something
other than Halts(tm, input).

Anyway, I commend your effort to extract the exact form of nonsense
involved here. Thanks again.

<snip>
--
Ben.

[Antti Valmari]

On 05/03/12 03:34, Peter Olcott wrote:
> Halts(tm, input) // The semantic meaning that tm actually halts on input

Ok. In what I write below, Halts is a function in the mathematical sense
of the word (and not a Turing machine). It inputs a Turing machine and a
string, and returns either True or False, correctly answering "does tm
halt with input".

> <ProperSubset> mathematical symbol indicating proper subset
>
> Boolean Halting(String tm, String input)
> The domain of Halting (for the value of tm) is based on
> (a) Sigma*
> (b) <ProperSubset> (a) That represent valid Turing Machines.
> (c) <ProperSubset> (b) That halt on input
> (d) <ProperSubset> (c) That Halting() returns true.
> Halting() returns true on set (d) and returns false on everything else.

Ok up to this point.

(For the record: I, too, would remove "Proper" because to me (b) could
be the same as (a). It depends on the encoding of Turing machines. But
this detail is definitely unimportant for the discussion, so let
"Proper" stay.)

> If Halting(tm, input) returning true would not make Halts(tm, input)
> false, then Halting(tm, input) must return true.

You write as if the value of Halts(tm, input) depended on Halting(tm,
input). It seems to me that you are thinking about the standard proof,
where there indeed is such a dependency: tm predicts its own future by
calling the hypothetical halting decider, and, after obtaining the
answer, does precisely the opposite.

In reality, Halts is a mathematical Boolean-valued function of tm and
input (and nothing else). That is how we defined it towards the
beginning of this message (your text cited, me agreeing with it). So the
value of Halts(tm, input) *only* depends on tm and input. Do you agree
with this?

In the standard proof, the value of Halts(tm, input) --- that is,
whether tm actually halts on input --- depends on what the halting
decider replies, but that is in contradiction with reality. This unreal
behaviour is only possible because its construction uses an entity which
does not exist: the halting decider.

In proofs by contradiction, odd things happen. This is built into the
nature of proofs by contradiction. Odd things happening in a proof by
contradiction do not imply that the same things could happen in reality.

So I agree with Ben Bacarisse:

> It was all going fine right up to "would not make".

On the other hand, it would be perfectly okay to define the value of
Halting(tm, input) in terms of Halts(tm, input). (For the record: In my
opinion (-: and in reality :-), such a definition would not be a proof
that Halting exists as a Turing machine.)

But you will not be able to formulate a definition that does what you
want. Let's see:

There are interesting Turing machines Halting(T,I) that always halt
replying either true or false, so that if it replies "true" then T halts
on I, but if it replies "false" then T does or does not halt on I. There
also are interesting Turing machines NotHalting(T,I) that always halt
replying either true or false, so that if it replies "true" then T does
not halt on I, but if it replies "false" then T does or does not halt on
I. (I tried to get close to your Halting and NotHalting. I hope I did
not make typos.) Each such pair defines a set "InvalidInput" in the way
you showed. The membership of the set is decidable.

However, there is no _unique_ Turing machine that could be called _the_
Halting and _the_ NotHalting. The proof for this fact is simple: take
any alleged "Halting", take any input (T1,I1) for which it answers
"false" although T1 halts on I1, and let ImprovedHalting be

if T == T1 and I == I1 then reply true
else reply what Halting(T,I) replies.

So there is no well-defined unique set "InvalidInput" of the kind you
want. Each "InvalidInput" is arbitrary in the sense that it does not
tell about the halting problem, it only tells about the choice made
among all possible "Halting"s and "NotHalting"s.

The intersection of all "InvalidInput"s would be a natural choice as
_the_ "InvalidInput". But it is the empty set, so it does not correspond
to a non-trivial property.


--- Antti Valmari ---

[Joshua Cranmer]

On 5/3/2012 8:14 AM, Ralph Hartley wrote:
> He wants to use a counter factual like
>
> (C) if Halting(tm, input) were to return true, then Halts(tm, input)
> would be false
>
> and by (W) he means
>
> (W') if not (if Halting(tm, input) were to return true, then Halts(tm,
> input) would be false), then Halting(tm, input) must return true;
>
> But (C) makes no sense, it is like saying "if 12345 were even then 12346
> would be odd".

I suspect the notion he wants to get to is equivalent to the following:
"If the implementation of Halts contains an invocation to Halting such
that replacing all invocations of Halting(tm, input) with the fixed
output of Halting(tm, input) would modify the result of the function,
then...". If that is truly the notion he wants, then Rice's Theorem
never comes into play, since it's dependent on the implementation and
not any actual function he calls into play.

For example, let O1 and O2 be two functions. O1(x) := not Even(x-1)
while O2(x) := x % 2 == 1. The statement (C) analogously applies to O1
but not to O2, even though O1(x) == O2(x) for all x.

[Ben Bacarisse]

Joshua Cranmer <Pidg...@verizon.invalid> writes:

> On 5/3/2012 8:14 AM, Ralph Hartley wrote:
>> He wants to use a counter factual like
>>
>> (C) if Halting(tm, input) were to return true, then Halts(tm, input)
>> would be false
>>
>> and by (W) he means
>>
>> (W') if not (if Halting(tm, input) were to return true, then Halts(tm,
>> input) would be false), then Halting(tm, input) must return true;
>>
>> But (C) makes no sense, it is like saying "if 12345 were even then 12346
>> would be odd".
>
> I suspect the notion he wants to get to is equivalent to the following:
> "If the implementation of Halts contains an invocation to Halting such
> that replacing all invocations of Halting(tm, input) with the fixed
> output of Halting(tm, input) would modify the result of the function,
> then...".

It was my understanding that Halts is a mathematical predicate (or
function if that is the preferred view) and not something that has an
implementation. Are you saying that he views even such things as the
Halts predicate in operational terms?

> If that is truly the notion he wants, then Rice's Theorem
> never comes into play, since it's dependent on the implementation and
> not any actual function he calls into play.
>
> For example, let O1 and O2 be two functions. O1(x) := not Even(x-1)
> while O2(x) := x % 2 == 1. The statement (C) analogously applies to O1
> but not to O2, even though O1(x) == O2(x) for all x.

I think we've all been staring into the abyss for too long!

--
Ben.

[Peter Olcott]

On 5/2/2012 9:07 PM, Ben Bacarisse wrote:
> Peter Olcott<NoS...@OCR4Screen.com> writes:
>
>> Halts(tm, input) // The semantic meaning that tm actually halts on input
>> <ProperSubset> mathematical symbol indicating proper subset
> I suggest you lower-case for functions and keep initial upper-case for
> sets and machines. Too late now, but you've used Halts to mean other
> things before, and it's very similar to other names you've used for
> machines. Maybe next time round?
>
>> Boolean Halting(String tm, String input)
>> The domain of Halting (for the value of tm) is based on
> What's the point of taking a term that has an agreed meaning (domain)
> and inventing a new meaning for it? You don't need the term at all (you
> don't refer to it again) -- all you need is the set (d).

I was dividing up the domain into the inputs mapping to true, and those
mapping to false.

>
>> (a) Sigma*
>> (b)<ProperSubset> (a) That represent valid Turing Machines.
>> (c)<ProperSubset> (b) That halt on input
>> (d)<ProperSubset> (c) That Halting() returns true.
>> Halting() returns true on set (d) and returns false on everything else.
>>
>> If Halting(tm, input) returning true would not make Halts(tm, input)
>> false, then Halting(tm, input) must return true.
> It was all going fine right up to "would not make". Nothing Halting(tm,
> input) does can "make" Halts(tm, input) be anything other than it is.
> Do you mean that Halting(tm, input) => Halts(tm, input)? Probably not.
>
> Why not just tabulate the cases? For every element of (d) Halting
> either must, or may, return either true or false. Halts is simpler. It
> is either true or false for all elements of (d) (well, for the machine
> computations that the elements of (d) represent) so you could specify
> Halting using a table:
>
> Halts(tm, input) Halting(tm, input) Allowed? Required?
> true true yes ?
> true false ? ?
> false true ? ?
> false false ? ?
>
> This is not a quibble. It is exactly your inability to say what you mean
> that keeps these threads going. As Daryl has said, once you say what
> you mean, I think it will be clear that you are mistaken.

I thought about this today and thought that we might have to back up a
step to make sure that we are on the same page.

I have been studying my textbooks and other material to help me respond
using the conventional terminology of computing theory.

First of all let's back up to what it means that the can be no halt
decider for the self-reference form of the halting problem.

It seems to me that this problem may be stated:
~<ThereExists> <ElementOfSet> Turing Machines h such that
h(tm, input) <LogicalEntailment> Halts(tm, input)

Let's stop there for now.
See if anyone can make this specification as formal as possible
such that everyone agrees that this is exactly what the self-reference
form of the Halting Problem is.

I am new at this degree of mathematical formalism so I need some coaching.
I am finding that learning and practicing this stuff is great fun.

[Peter Olcott]

Yes I am still not very adept at specifying mathematical formalisms,
but, it is quite fun.
Please see if you can improve on this specification of the
self-reference form of the Halting Problem: (future discussion will be
best using this as the foundation)

[Peter Olcott]

On 5/3/2012 8:14 AM, Ralph Hartley wrote:

Since you seem to be able to follow plain English, I will pose this more
difficult question to you.

It seems to me that the theory of computation conflates two different
common English terms into a single term:
(1) The Common English term {Decide} meaning essentially to select from
alternatives.
(2) The Common English term {Report} to provide a response.
It seems to me that a Decider(TheoryOfComputation) must
Decide(CommonEnglish) and Report(CommonEnglish).

So when it is said that there can be no Decider(TheoryOfComputation) for
the self-reference form of the Halting Problem, this does not logically
entail that a tm can not Decide(CommonEnglish) the self-reference form
of the Halting Problem.

It would seem to me that it would be possible for a TM to have as an
intermediate state within itself, and not within the interface to the
outside world (final states of {accept, reject}) a pair of states
representing the actual Decide(CommonEnglish) of the halting for any
possible input.

Can you provide a valid counter-example to this reasoning? Does this
make sense to you?

[Peter Olcott]

On 5/3/2012 8:29 AM, Ralph Hartley wrote:

You have been so helpful I really appreciate that. My prior post to you
may provide the prerequisite basis for addressing the issues that you
and Joshua raised above.

It will be far easier to address the points raised in this post because
all of these points can be directly addressed within the pre-existing
conceptual framework and terminology of the Theory of Computation.
Because of this I will focus on the subject of this post rather than the
other subject.

The other subject was that the Halting Problem is based on a very subtle
and profoundly brilliant fundamental error of reasoning. This topic will
be put on hold for now.

[Peter Olcott]

On 5/3/2012 2:30 PM, Antti Valmari wrote:
> On 05/03/12 03:34, Peter Olcott wrote:
>> Halts(tm, input) // The semantic meaning that tm actually halts on input
> Ok. In what I write below, Halts is a function in the mathematical sense
> of the word (and not a Turing machine). It inputs a Turing machine and a
> string, and returns either True or False, correctly answering "does tm
> halt with input".
>
>
>> <ProperSubset> mathematical symbol indicating proper subset
>>
>> Boolean Halting(String tm, String input)
>> The domain of Halting (for the value of tm) is based on
>> (a) Sigma*
>> (b)<ProperSubset> (a) That represent valid Turing Machines.
>> (c)<ProperSubset> (b) That halt on input
>> (d)<ProperSubset> (c) That Halting() returns true.
>> Halting() returns true on set (d) and returns false on everything else.
> Ok up to this point.
>
> (For the record: I, too, would remove "Proper" because to me (b) could
> be the same as (a). It depends on the encoding of Turing machines. But
> this detail is definitely unimportant for the discussion, so let
> "Proper" stay.)
>

I am thinking that any specification of a TM should not make any
assumptions and only do exactly what is specified and no more. In this
case there would be no default assumption that the empty string is any
sort of valid Turing Machine at all. If no accept state or reject state
is specified, then this entails that there are no final states, and thus
not a valid TM.

>> If Halting(tm, input) returning true would not make Halts(tm, input)
>> false, then Halting(tm, input) must return true.
> You write as if the value of Halts(tm, input) depended on Halting(tm,
> input). It seems to me that you are thinking about the standard proof,
> where there indeed is such a dependency: tm predicts its own future by
> calling the hypothetical halting decider, and, after obtaining the
> answer, does precisely the opposite.
>
> In reality, Halts is a mathematical Boolean-valued function of tm and
> input (and nothing else). That is how we defined it towards the
> beginning of this message (your text cited, me agreeing with it). So the
> value of Halts(tm, input) *only* depends on tm and input. Do you agree
> with this?
>
> In the standard proof, the value of Halts(tm, input) --- that is,
> whether tm actually halts on input --- depends on what the halting
> decider replies, but that is in contradiction with reality. This unreal
> behaviour is only possible because its construction uses an entity which
> does not exist: the halting decider.
>
> In proofs by contradiction, odd things happen. This is built into the
> nature of proofs by contradiction. Odd things happening in a proof by
> contradiction do not imply that the same things could happen in reality.
>
> So I agree with Ben Bacarisse:
>
>> It was all going fine right up to "would not make".

What I am saying (in plain English) is that it seems that there can not
be anything that could prevent a TM from determining that it can not
transition to a final state that corresponds to Halts(tm, input). Also
it could simply transition to its reject state in these cases.

I am striving to formalize this in other responses.

[Ben Bacarisse]

You were very close to actually saying what you mean. Only one
statement was at all confusing. I wonder why you want to back up just
as you get close to being clear. Could you really not complete this
table? (If you want to add some more rows, that would be fine.) Or is
Ralph correct that what Halting is allowed and/or required to return
does not depend solely on its inputs and the Halts predicate?

<snip>
--
Ben.

[Peter Olcott]

On 5/3/2012 2:30 PM, Antti Valmari wrote:

Great I think that you have got it.

The InvalidInput Decider correctly decides the property of InvalidInput

for Sigma*

This would seem to exactly refute what Dexter Kozen provides as the
specification of Rice's Theorem: "Every nontrivial property of the r.e.
sets is undecidable". (page 245, 1997 edition of Automata and
Computability).

(1) Its decidable
(2) Its a non trivial property
(3) If its (a non trivial property) of a r.e set then it
would seem to refute Rice's Theorem

> However, there is no _unique_ Turing machine that could be called _the_
> Halting and _the_ NotHalting. The proof for this fact is simple: take
> any alleged "Halting", take any input (T1,I1) for which it answers
> "false" although T1 halts on I1, and let ImprovedHalting be
>
> if T == T1 and I == I1 then reply true
> else reply what Halting(T,I) replies.
>
> So there is no well-defined unique set "InvalidInput" of the kind you
> want. Each "InvalidInput" is arbitrary in the sense that it does not
> tell about the halting problem, it only tells about the choice made
> among all possible "Halting"s and "NotHalting"s.
>
> The intersection of all "InvalidInput"s would be a natural choice as
> _the_ "InvalidInput". But it is the empty set, so it does not correspond
> to a non-trivial property.
>
>
> --- Antti Valmari ---

Boolean InvalidInput(String tm String input)
{
if (!Halting(tm, input) && !NotHalting(tm, input))
return true;
else
return false;
}

The above would seem to be able to decide the non trivial property of
InvalidInput for Sigma*

This would mean that:
(a) Self-reference form of HP, (relative to itself) return true.
(b) Syntactically invalid TM return true.
(c) Neither (a) nor (b) and Halts(tm, input) return false.
(d) Neither (a) nor (b) and !Halts(tm, input) return false.

[Peter Olcott]

Antti Valmari seems to have got it.

[Peter Olcott]

On 5/3/2012 6:49 PM, Ben Bacarisse wrote:

Boolean InvalidInput(String tm String input)
{
if (!Halting(tm, input) && !NotHalting(tm, input))
return true;
else
return false;
}

The above would seem to be able to decide the non trivial property of
InvalidInput for Sigma*

This would mean that:
(a) Self-reference form of HP, (relative to itself) return true.
(b) Syntactically invalid TM return true.
(c) Neither (a) nor (b) and Halts(tm, input) return false.
(d) Neither (a) nor (b) and !Halts(tm, input) return false.

Antti Valmari seems to have got it, go read this post.
I won't assume male female for names that I can't tell the sex of.

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/3/2012 2:30 PM, Antti Valmari wrote:

<snip>

>> There are interesting Turing machines Halting(T,I) that always halt
>> replying either true or false, so that if it replies "true" then T halts
>> on I, but if it replies "false" then T does or does not halt on I. There
>> also are interesting Turing machines NotHalting(T,I) that always halt
>> replying either true or false, so that if it replies "true" then T does
>> not halt on I, but if it replies "false" then T does or does not halt on
>> I. (I tried to get close to your Halting and NotHalting. I hope I did
>> not make typos.) Each such pair defines a set "InvalidInput" in the way
>> you showed. The membership of the set is decidable.
> Great I think that you have got it.

It's a shame you either ignored or disagreed with the rest of what he
said.

> The InvalidInput Decider correctly decides the property of
> InvalidInput for Sigma*
>
> This would seem to exactly refute what Dexter Kozen provides as the
> specification of Rice's Theorem: "Every nontrivial property of the
> r.e. sets is undecidable". (page 245, 1997 edition of Automata and
> Computability).
>
> (1) Its decidable
> (2) Its a non trivial property
> (3) If its (a non trivial property) of a r.e set then it
> would seem to refute Rice's Theorem

You don't understand Rice's theorem. It is about non-trivial properties
of the languages recognized by machines (note the plural). You simply
don't have an applicable case here. Here you seem to be talking about a
set of strings, decided by a single machine.

You would have an applicable case if you were to factor in some putative
halting decider. H. For example, the property that the machine passed
to H behaves in the same way as the "tricksy" M used in the standard
proof, is a non-trivial property of a class of machines. Rice's theorem
says you can't detect all these M-like machines -- the set of machines
that behave like M is undecidable.

<snip>
--
Ben.

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:
<snip>

> Antti Valmari seems to have got it.

Including the bit where he says:

| So there is no well-defined unique set "InvalidInput" of the kind you
| want. Each "InvalidInput" is arbitrary in the sense that it does not
| tell about the halting problem, it only tells about the choice made
| among all possible "Halting"s and "NotHalting"s.
|
| The intersection of all "InvalidInput"s would be a natural choice as
| _the_ "InvalidInput". But it is the empty set, so it does not correspond
| to a non-trivial property.

You have an interesting strategy. To make it look like someone agrees
with you, you say they "get it". But the more people "get it" the more
they disagree. People only hold back while they try to pin down your
confused definitions. As soon as they start to understand, they all
seem to disagree.

--
Ben.

[Ben Bacarisse]

So, please confirm that you can't (or won't) tabulate exactly when and
what Halting must return.

>> <snip>
> Boolean InvalidInput(String tm String input)
> {
> if (!Halting(tm, input) && !NotHalting(tm, input))
> return true;
> else
> return false;
> }
>
> The above would seem to be able to decide the non trivial property of
> InvalidInput for Sigma*
>
> This would mean that:
> (a) Self-reference form of HP, (relative to itself) return true.
> (b) Syntactically invalid TM return true.
> (c) Neither (a) nor (b) and Halts(tm, input) return false.
> (d) Neither (a) nor (b) and !Halts(tm, input) return false.
>
> Antti Valmari seems to have got it, go read this post.

I did. It's good. He thinks you're wrong. Highlights include "I agree
with Ben Bacarisse" and "So there is no well-defined unique set

"InvalidInput" of the kind you want".

Unfortunately he had to guess what on earth you were talking about.
That will allow to say he got that bit wrong if you choose to read it
yourself.

> I won't assume male female for names that I can't tell the sex of.

All the (few) Antti's I know of are male. I think it's not an uncommon
name in Finland. I apologize if I've guessed wrong.

--
Ben.

[Peter Olcott]

On 5/3/2012 8:54 PM, Ben Bacarisse wrote:
> Peter Olcott<OCR4Screen> writes:
>
>> On 5/3/2012 2:30 PM, Antti Valmari wrote:
> <snip>
>>> There are interesting Turing machines Halting(T,I) that always halt
>>> replying either true or false, so that if it replies "true" then T halts
>>> on I, but if it replies "false" then T does or does not halt on I. There
>>> also are interesting Turing machines NotHalting(T,I) that always halt
>>> replying either true or false, so that if it replies "true" then T does
>>> not halt on I, but if it replies "false" then T does or does not halt on
>>> I. (I tried to get close to your Halting and NotHalting. I hope I did
>>> not make typos.) Each such pair defines a set "InvalidInput" in the way
>>> you showed. The membership of the set is decidable.
>> Great I think that you have got it.
> It's a shame you either ignored or disagreed with the rest of what he
> said.

I responded to his single post with two different replies.

>> The InvalidInput Decider correctly decides the property of
>> InvalidInput for Sigma*
>>
>> This would seem to exactly refute what Dexter Kozen provides as the
>> specification of Rice's Theorem: "Every nontrivial property of the
>> r.e. sets is undecidable". (page 245, 1997 edition of Automata and
>> Computability).
>>
>> (1) Its decidable
>> (2) Its a non trivial property
>> (3) If its (a non trivial property) of a r.e set then it
>> would seem to refute Rice's Theorem
> You don't understand Rice's theorem. It is about non-trivial properties
> of the languages recognized by machines (note the plural). You simply
> don't have an applicable case here. Here you seem to be talking about a
> set of strings, decided by a single machine.

It is a set of machines.

[Peter Olcott]

Your table does not break down into the correct categories, and it
combines elements in an inappropriate way.

>>> <snip>
>> Boolean InvalidInput(String tm String input)
>> {

>> if (!Halting(tm, input)&& !NotHalting(tm, input))

>> return true;
>> else
>> return false;
>> }
>>
>> The above would seem to be able to decide the non trivial property of
>> InvalidInput for Sigma*
>>
>> This would mean that:
>> (a) Self-reference form of HP, (relative to itself) return true.
>> (b) Syntactically invalid TM return true.
>> (c) Neither (a) nor (b) and Halts(tm, input) return false.
>> (d) Neither (a) nor (b) and !Halts(tm, input) return false.
>>
>> Antti Valmari seems to have got it, go read this post.
> I did. It's good. He thinks you're wrong. Highlights include "I agree
> with Ben Bacarisse" and "So there is no well-defined unique set
> "InvalidInput" of the kind you want".
>

The aspect that you think that he is saying that I am wrong on is not an
aspect that I have claimed.

> Unfortunately he had to guess what on earth you were talking about.
> That will allow to say he got that bit wrong if you choose to read it
> yourself.

No, he simply tried to understand what I was saying.

It seems to me (and I could be wrong) that your goal was to refute what
I was saying, rather than understand what I was saying.

[Antti Valmari]

On 05/04/12 03:53, Peter Olcott wrote:
> On 5/3/2012 2:30 PM, Antti Valmari wrote:
>> There are interesting Turing machines Halting(T,I) that always halt
>> replying either true or false, so that if it replies "true" then T halts
>> on I, but if it replies "false" then T does or does not halt on I. There
>> also are interesting Turing machines NotHalting(T,I) that always halt
>> replying either true or false, so that if it replies "true" then T does
>> not halt on I, but if it replies "false" then T does or does not halt on
>> I. (I tried to get close to your Halting and NotHalting. I hope I did
>> not make typos.) Each such pair defines a set "InvalidInput" in the way
>> you showed. The membership of the set is decidable.
> Great I think that you have got it.

Great I guessed close what you aimed at.

> The InvalidInput Decider correctly decides the property of InvalidInput
> for Sigma*

"InvalidInput" is not a property of Sigma*. I wrote so in the same
message, immediately after the lines you cited. Others have found that
piece of information from there, and wondered why you ignored that part
of my message.

So Rice's Theorem is not in danger.

On 05/04/12 02:22, Peter Olcott wrote:
> I am thinking that any specification of a TM should not make any
> assumptions and only do exactly what is specified and no more. In
> this case there would be no default assumption that the empty string
> is any sort of valid Turing Machine at all. If no accept state or
> reject state is specified, then this entails that there are no final
> states, and thus not a valid TM.

You seem to think that the encoding must be somehow logical or
straightforward. For instance, the bigger is the TM, the longer must the
encoding be. This is not necessary. Let me define a new programming
language Blank_C. The compiler for Blank_C works as follows:

if the input file is empty
then return the compiled version of the Solitaire game
else deliver the input file to a C compiler and return its result.

For Blank_C, the empty file is a perfectly ok program. When compiled, it
yields the Solitaire game. In the same manner, the empty string could be
the code for any particular Turing machine with accept and reject states
and so on.

On 05/04/12 05:20, Ben Bacarisse wrote:
> All the (few) Antti's I know of are male. I think it's not an uncommon
> name in Finland. I apologize if I've guessed wrong.

Correct gender, correct nationality. Also all of the Antti's I know are
male. The name has never been very popular but has always been somewhat
popular, so, although in many cases a Finnish name gives a strong
indication of the person's age, the name Antti does not. Thank you for
spelling it right! Anglosaxons tend to mis-spell it Antii.

On 05/04/12 06:05, Peter Olcott wrote:
> No, he simply tried to understand what I was saying.

I am trying to understand how you think, but I do not agree with your
ideas. Instead, I am trying to locate the exact place where your ideas
go wrong, and then explain to you where and why they are wrong. I, too
am "prejudiced" in the sense that I have gone through the established
reasoning and found it correct, while your reasoning seems fuzzy to me.
Fortunately, your writings have recently become more clear, making it
possible to discuss them constructively.

One message that I am now trying to get through is that although there
is no halting decider TM, there is an infinite set of more and more
precise approximate halting deciders. If they could be put together to
one huge combined halting decider, it would always decide correctly, but
putting them together is not possible, because that would yield an
infinite thing and, by definition, Turing machines are finite. (If
infinite objects were allowed, we could have a halting decider simply as
an infinite phone book who has every possible string on a line of its
own and then "yes" or "no" after each string.)

So there is no non-trivial ultimate "InvalidInput" set, because whatever
input you believe would be there, is correctly classified by some more
advanced Halting or NotHalting, as I pointed out in my earlier message.
Instead, there are infinitely many different "InvalidInput" sets, each
approximating but none meeting your goal.

--- Antti Valmari ---

[Ben Bacarisse]

Then please correct it. Add or remove rows and columns as needed. Then
it will be clear exactly what Halting is required to do. What other
properties of the (tm, input) pair does it require? What other
distinctions about the categories does it need to make?

I think you can't do this without introducing a new column (essentially
Ralph's 'W') that will be either ill-defined or not computable.

<snip>
--
Ben.

[Peter Olcott]

On 5/4/2012 5:35 AM, Antti Valmari wrote:
> On 05/04/12 03:53, Peter Olcott wrote:
>> On 5/3/2012 2:30 PM, Antti Valmari wrote:
>>> There are interesting Turing machines Halting(T,I) that always halt
>>> replying either true or false, so that if it replies "true" then T halts
>>> on I, but if it replies "false" then T does or does not halt on I. There
>>> also are interesting Turing machines NotHalting(T,I) that always halt
>>> replying either true or false, so that if it replies "true" then T does
>>> not halt on I, but if it replies "false" then T does or does not halt on
>>> I. (I tried to get close to your Halting and NotHalting. I hope I did
>>> not make typos.) Each such pair defines a set "InvalidInput" in the way
>>> you showed. The membership of the set is decidable.
>> Great I think that you have got it.
> Great I guessed close what you aimed at.
>
>
>> The InvalidInput Decider correctly decides the property of InvalidInput
>> for Sigma*
> "InvalidInput" is not a property of Sigma*. I wrote so in the same
> message, immediately after the lines you cited. Others have found that
> piece of information from there, and wondered why you ignored that part
> of my message.
>
> So Rice's Theorem is not in danger.

It is a property of the combination of Sigma* and the TM?

>
> On 05/04/12 02:22, Peter Olcott wrote:
>> I am thinking that any specification of a TM should not make any
>> assumptions and only do exactly what is specified and no more. In
>> this case there would be no default assumption that the empty string
>> is any sort of valid Turing Machine at all. If no accept state or
>> reject state is specified, then this entails that there are no final
>> states, and thus not a valid TM.
> You seem to think that the encoding must be somehow logical or
> straightforward. For instance, the bigger is the TM, the longer must the
> encoding be. This is not necessary. Let me define a new programming
> language Blank_C. The compiler for Blank_C works as follows:
>
> if the input file is empty
> then return the compiled version of the Solitaire game
> else deliver the input file to a C compiler and return its result.
>
> For Blank_C, the empty file is a perfectly ok program. When compiled, it
> yields the Solitaire game. In the same manner, the empty string could be
> the code for any particular Turing machine with accept and reject states
> and so on.

Yes, but this mathematical mapping would then be incorrect.

>
> On 05/04/12 05:20, Ben Bacarisse wrote:
>> All the (few) Antti's I know of are male. I think it's not an uncommon
>> name in Finland. I apologize if I've guessed wrong.
> Correct gender, correct nationality. Also all of the Antti's I know are
> male. The name has never been very popular but has always been somewhat
> popular, so, although in many cases a Finnish name gives a strong
> indication of the person's age, the name Antti does not. Thank you for
> spelling it right! Anglosaxons tend to mis-spell it Antii.
>
>
> On 05/04/12 06:05, Peter Olcott wrote:
>> No, he simply tried to understand what I was saying.
> I am trying to understand how you think, but I do not agree with your
> ideas.

You certainly seem to agree that InvalidInput(tm, input) can be derived.

> Instead, I am trying to locate the exact place where your ideas
> go wrong, and then explain to you where and why they are wrong. I, too
> am "prejudiced" in the sense that I have gone through the established
> reasoning and found it correct, while your reasoning seems fuzzy to me.
> Fortunately, your writings have recently become more clear, making it
> possible to discuss them constructively.

I have been working on that.

> One message that I am now trying to get through is that although there
> is no halting decider TM, there is an infinite set of more and more
> precise approximate halting deciders. If they could be put together to

I don't see this. This would seem to be impossible.

It seems to me that the whole self-reference form of the Halting Problem
(SRFHP) boils down to whether or not SRFHP applies to a particular (tm,
input) pair.

That is why I specified the infinite set of TMs that SRFHP does apply to.

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

<ForAll> H <ElementOfSet> Turing Machines
<ForAll> tm, input <ElementOfSet> Sigma*
~<ThereExists> H(M, M) <LogicalEntailment> Halts(tm, input)

M might be specified as M(n) in the above because each M is different.
I had been simply saying M is a template.
H(M, M) means the return value for the invocation of H(M, M).

> one huge combined halting decider, it would always decide correctly, but
> putting them together is not possible, because that would yield an
> infinite thing and, by definition, Turing machines are finite. (If
> infinite objects were allowed, we could have a halting decider simply as
> an infinite phone book who has every possible string on a line of its
> own and then "yes" or "no" after each string.)
>
> So there is no non-trivial ultimate "InvalidInput" set, because whatever
> input you believe would be there, is correctly classified by some more
> advanced Halting or NotHalting, as I pointed out in my earlier message.
> Instead, there are infinitely many different "InvalidInput" sets, each
> approximating but none meeting your goal.
>
> --- Antti Valmari ---

Although there may be no InvalidInput decider for the input to all TMs,
it would seem that there could be one for *all* the input of any
particular TM. How hard could it be to check and see if something mucks
with its own final state?

Also it would seem to be possible that a TM could have an intermediate
state that does correctly represent whether or not its input would halt
or loop.** It seems that the only limitation is that this TM can not
represent the halting behavior of its input as its own final state.

Within the context of the self-reference form of the Halting Problem.

[Peter Olcott]

I think that Antti Valmari may already understand what I mean, maybe not.

This whole thread is focused *only* on the
Self-Reference Form of the Halting Problem (SRFHP)

Halting() returns true when:
Halts(tm, input) && Not(SRFHP) && Valid(tm, input)

NotHalting() returns true when:
!Halts(tm, input) && Not(SRFHP) && Valid(tm, input)

Both return false otherwise.

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/4/2012 6:47 AM, Ben Bacarisse wrote:
>> Peter Olcott<OCR4Screen> writes:

<snip>

>>> Your table does not break down into the correct categories, and it
>>> combines elements in an inappropriate way.
>> Then please correct it. Add or remove rows and columns as needed. Then
>> it will be clear exactly what Halting is required to do. What other
>> properties of the (tm, input) pair does it require? What other
>> distinctions about the categories does it need to make?
>>
>> I think you can't do this without introducing a new column (essentially
>> Ralph's 'W') that will be either ill-defined or not computable.
>>
>> <snip>
> I think that Antti Valmari may already understand what I mean, maybe
> not.

I think he has.

> This whole thread is focused *only* on the
> Self-Reference Form of the Halting Problem (SRFHP)
>
> Halting() returns true when:
> Halts(tm, input) && Not(SRFHP) && Valid(tm, input)
>
> NotHalting() returns true when:
> !Halts(tm, input) && Not(SRFHP) && Valid(tm, input)
>
> Both return false otherwise.

That wasn't hard. Shame you managed to obscure it for so long in this
thread. The table just needs a new column for the function SRFHP. This
is exactly what you've been saying for months now. There's nothing new.

I've lost track of how many people have told you to avoid implied
dependencies. However you end up defining it, SRFHP is a function not
only of the (tm, input) pair, but also of some putative halting decider.
What is SRFHP to one machine is not to another, so you should show this
functional dependency: SRFHP(H, tm, input). There is no useful
universal SRFHP predicate. (I say "useful" because, as has also been
said many times before, you can define it sufficiently broadly to make
InvalidInput both computable and independent of any H, but you have,
quite correctly, rejected that as not being what you mean).

You like what Antti writes so read his message about this. He explains
very well why InvalidInput does not decide a single, universal set of
invalid computations, but rather a family of them. He had to express it
in terms of the multiple possible implementations of "Halting" because
you'd carefully hidden the fact that "Halting" is predicated on the same
old notion of an SRFHP test.

Also, as I wrote in my comments about Rice's theorem, you do have an
instance of it because InvalidInput(H) has to decide if a given TM
behaves like the M(H) machine. Of course, since you can't show that
it's computable, you don't have a counter-example.

--
Ben.

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/4/2012 5:35 AM, Antti Valmari wrote:

<snip>

>> One message that I am now trying to get through is that although there
>> is no halting decider TM, there is an infinite set of more and more
>> precise approximate halting deciders. If they could be put together to
>
> I don't see this. This would seem to be impossible.

It been demonstrated several times. I think Daryl's demonstration is
the clearest. What's more, your argument is exactly what's needed to
show that it's true!

> It seems to me that the whole self-reference form of the Halting
> Problem (SRFHP) boils down to whether or not SRFHP applies to a
> particular (tm, input) pair.
>
> That is why I specified the infinite set of TMs that SRFHP does apply to.
>
> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> <ForAll> H <ElementOfSet> Turing Machines
> <ForAll> tm, input <ElementOfSet> Sigma*
> ~<ThereExists> H(M, M) <LogicalEntailment> Halts(tm, input)
>
> M might be specified as M(n) in the above because each M is different.
> I had been simply saying M is a template.
> H(M, M) means the return value for the invocation of H(M, M).

Right. Please start doing that. Write:

M(H, i):
if H(i, i) loop
else halt

to show that M is a function of H. The key computation is then H(M(H),
M(H)). (This partial application of M only one argument confuses some
people, but it's perfectly well-defined. If you prefer, think of H as a
subscript: M_H(i).)

<snip>

> Although there may be no InvalidInput decider for the input to all
> TMs, it would seem that there could be one for *all* the input of any
> particular TM. How hard could it be to check and see if something
> mucks with its own final state?

As hard a Rice's theorem says it is. What you are calling (elsewhere)
SRFHP is not a property of the input machine itself, but a property of
its behaviour. For every M(H) there is whole set of M2(H), M3(H),
... that behave in exactly the same way but don't "look like" M(H).

There's an irony here. Your desire to detect M(H) and "deal with it" is
exactly the way Daryl showed that is a chain of ever better putative
halting deciders. Why, given this similarity, do you reject his proof?

> Also it would seem to be possible that a TM could have an intermediate
> state that does correctly represent whether or not its input would
> halt or loop.** It seems that the only limitation is that this TM can
> not represent the halting behavior of its input as its own final
> state.

Ah, a TM with a soul that knows the truth. You should switch to poetry.

> Within the context of the self-reference form of the Halting Problem.

--
Ben.

[Peter Olcott]

On 5/4/2012 8:00 AM, Ben Bacarisse wrote:
> Peter Olcott<OCR4Screen> writes:
>
>> On 5/4/2012 6:47 AM, Ben Bacarisse wrote:
>>> Peter Olcott<OCR4Screen> writes:
> <snip>
>>>> Your table does not break down into the correct categories, and it
>>>> combines elements in an inappropriate way.
>>> Then please correct it. Add or remove rows and columns as needed. Then
>>> it will be clear exactly what Halting is required to do. What other
>>> properties of the (tm, input) pair does it require? What other
>>> distinctions about the categories does it need to make?
>>>
>>> I think you can't do this without introducing a new column (essentially
>>> Ralph's 'W') that will be either ill-defined or not computable.
>>>
>>> <snip>
>> I think that Antti Valmari may already understand what I mean, maybe
>> not.
> I think he has.
>
>> This whole thread is focused *only* on the
>> Self-Reference Form of the Halting Problem (SRFHP)
>>
>> Halting() returns true when:

>> Halts(tm, input)&& Not(SRFHP)&& Valid(tm, input)
>>
>> NotHalting() returns true when:
>> !Halts(tm, input)&& Not(SRFHP)&& Valid(tm, input)

>>
>> Both return false otherwise.
> That wasn't hard. Shame you managed to obscure it for so long in this
> thread. The table just needs a new column for the function SRFHP. This
> is exactly what you've been saying for months now. There's nothing new.
>
> I've lost track of how many people have told you to avoid implied
> dependencies. However you end up defining it, SRFHP is a function not
> only of the (tm, input) pair, but also of some putative halting decider.

Yes

> What is SRFHP to one machine is not to another, so you should show this

Yes

> functional dependency: SRFHP(H, tm, input). There is no useful

I don't understand what this means.

> universal SRFHP predicate. (I say "useful" because, as has also been

Yes.

> said many times before, you can define it sufficiently broadly to make
> InvalidInput both computable and independent of any H, but you have,
> quite correctly, rejected that as not being what you mean).

Although it does universally apply to all input pairs(t, input)
it does not universally apply to every possible Halting() and
NotHalting() decider.
It only applies to a single pair of these two TMs and also to the
infinite set of their semantic equivalents.

>
> You like what Antti writes so read his message about this. He explains
> very well why InvalidInput does not decide a single, universal set of
> invalid computations, but rather a family of them.

Three different infinite sets:
It is a decider for all inputs to a specific TM. (and semantic equivalents)
It is not a decider for all inputs to all TMs.
It is not ever a decider for some inputs to all TMs.

> He had to express it
> in terms of the multiple possible implementations of "Halting" because
> you'd carefully hidden the fact that "Halting" is predicated on the same
> old notion of an SRFHP test.

Every time that I bring this up you keep saying that it is impossible to
make a TM that decides SRFHP, when what you really meant was that it is
impossible to make a universal TM that decides SRFHP for all inputs to
all TMs.

I say that X it true and you keep saying, no Y is false.

> Also, as I wrote in my comments about Rice's theorem, you do have an
> instance of it because InvalidInput(H) has to decide if a given TM
> behaves like the M(H) machine. Of course, since you can't show that
> it's computable, you don't have a counter-example.
>

It seems to me that InvalidInput(tm, input) can correctly decide all
possible InvalidInput to itself and its constituents. Antti Valmari said
that this was decidable:
(see the last line, I provided the rest for context)

[Peter Olcott]

M(TM h, String input):
if h(input, input) loop
else halt

What about the rest of this syntax?

<ForAll> tm, input <ElementOfSet> Sigma*

<ForAll> h <ElementOfSet> Turing Machines
~<ThereExists> h(M, M) <LogicalEntailment> Halts(tm, input)

h(M, M) means the return value for the invocation of h(M, M).

> <snip>
>> Although there may be no InvalidInput decider for the input to all
>> TMs, it would seem that there could be one for *all* the input of any
>> particular TM. How hard could it be to check and see if something
>> mucks with its own final state?
> As hard a Rice's theorem says it is. What you are calling (elsewhere)
> SRFHP is not a property of the input machine itself, but a property of
> its behaviour. For every M(H) there is whole set of M2(H), M3(H),
> ... that behave in exactly the same way but don't "look like" M(H).
>
> There's an irony here. Your desire to detect M(H) and "deal with it" is
> exactly the way Daryl showed that is a chain of ever better putative
> halting deciders. Why, given this similarity, do you reject his proof?

Either SRFHP exists for a (TM, tm, input) triple or it does not, thus no
improvement is possible, one can merely define another (TM2, tm, input)
triple where SRFHP does not apply, for the same (tm, input) pair.

>> Also it would seem to be possible that a TM could have an intermediate
>> state that does correctly represent whether or not its input would
>> halt or loop.** It seems that the only limitation is that this TM can
>> not represent the halting behavior of its input as its own final
>> state.
> Ah, a TM with a soul that knows the truth. You should switch to poetry.

Merely an intermediate state that knows the truth.
Try and show a valid counter-example how this would not be possible
within SRFHP.

[Ross A. Finlayson]

On May 4, 4:51 am, Peter Olcott <OCR4Screen> wrote:
> On 5/4/2012 5:35 AM, Antti Valmari wrote:
>
>
> > One message that I am now trying to get through is that although there
> > is no halting decider TM, there is an infinite set of more and more
> > precise approximate halting deciders. If they could be put together to

> > one huge combined halting decider, it would always decide correctly, but
> > putting them together is not possible, because that would yield an
> > infinite thing and, by definition, Turing machines are finite. (If
> > infinite objects were allowed, we could have a halting decider simply as
> > an infinite phone book who has every possible string on a line of its
> > own and then "yes" or "no" after each string.)
>
> > So there is no non-trivial ultimate "InvalidInput" set, because whatever
> > input you believe would be there, is correctly classified by some more
> > advanced Halting or NotHalting, as I pointed out in my earlier message.
> > Instead, there are infinitely many different "InvalidInput" sets, each
> > approximating but none meeting your goal.
>
> > --- Antti Valmari ---
>
> Although there may be no InvalidInput decider for the input to all TMs,
> it would seem that there could be one for *all* the input of any
> particular TM. How hard could it be to check and see if something mucks
> with its own final state?
>
> Also it would seem to be possible that a TM could have an intermediate
> state that does correctly represent whether or not its input would halt
> or loop.** It seems that the only limitation is that this TM can not
> represent the halting behavior of its input as its own final state.
>
> Within the context of the self-reference form of the Halting Problem.

Build Halts() from a trivial machine.

With the trivial machine as described, these are underdefined:

1) to see that an infinite combination of program and data completes
or doesn't,

Loop removing: here it does with just having all the data, for each
output.

2) how to encode the program language?

One way is to have a program code:

data first <-> program first
data is normal <-> programs enumerate
data ends with a code <-> data follows

Then, using the half the tape, here there is already a use of the
folding of the tape to make room on the empty tape, this again is to
take the original input, and it's possible to remove the data, from
the program and data, before the program evaluation, then just setting
the coordinates in data. (i.e., the rest of the tape is blank for the
program or the data.)

If there are program codes to have that:

0/1: program ends
0/1: program erases rest of data

Then, to have recursion, here I'm thinking to show Halts() builds for
that the recursion halts or not. Then, the functions are designed as
checkers rather than computers.

Here, I just write data only for Sigma* and then those are the
readouts for the decoder in the all 1s that are the blanks. Then it
seems that would be the combined output space, basically where the
langauge space is Sigma* , or here L(oo)* the language space over an
infinite alphabet.

Then, basically the encoder can be writing the program as key then
both input and output data for all data combinations, each as a
different program to the decoder, that treats them all as one program
(for evaluating if and when they halt in cases).

Then where we do have completeness theorems, then yes theoretically if
not tractably, all the constructive programs are defined with their
data. And, the non-constructive infinite-program-and-data programs of
the Turing machine, don't halt. (And there are constructive infinite
program-and-data programs, and they do or don't.)

Then Pete says there obviously is a program intractable to static
analysis and what is it, or to a static analysis and what is it, then
I basically would have that is probably some ideal (or in as to rather
it's a reflexive dual in a space, ideal).

Yet, it's fair to limit the entire space, say to two. Then it's much
easier to find Pete's function, simply all the rest of them.

Then for it you can pretty easily build Halts(): flip a coin, fair,
as it were.

Then something like Chaitin's Omega seems more built to a language, in
as to, across the static runtimes for languages, working up cases over
the 85 variables or what it is. That's toward tractability.

Here the point is that, yes, the framework of the halting problem does
have the infinite tapes and infinite programs (and an infinite time
resource).

Ross Finlayson

[Peter Olcott]

On 5/4/2012 8:31 AM, Ben Bacarisse wrote:
> Peter Olcott<OCR4Screen> writes:
>

>> Also it would seem to be possible that a TM could have an intermediate
>> state that does correctly represent whether or not its input would
>> halt or loop.** It seems that the only limitation is that this TM can
>> not represent the halting behavior of its input as its own final
>> state.
> Ah, a TM with a soul that knows the truth. You should switch to poetry.

(a) Decide(CommonEnglish): Select from alternatives.
(b) Report(CommonEnglish): Provide a result.
(c) Decide(TheoryOfComputation): (a) && (b) conflated together.

(1) The SRFHP concludes that no TM can Decide(TheoryOfComputation), HP.
It is a fallacy of equivocation to take this to mean:
(2) The SRFHP concludes that no TM can Decide(CommonEnglish), HP.

Thus (1) does not entail (2) therefore it does not entail that an
intermediate state could not correctly represent the actual halting
behavior of its input pair (tm, input) as an internal state.

[Peter Olcott]

We never build Halts() it is a mathematical function indicating the
semantic meaning that the (tm, input) pair actually does halt. Since
your reasoning started with a false premise, I will leave up to you to
re-edit your response before I reply.

[Ben Bacarisse]

When you wrote

Boolean IllFormedQuestion(String tm, String input)
{
if (Not(Halting(tm, input)) && Not(NotHalting(tm, input)))
return true;
else // (Halting || NotHalting)
return false;
}

there was no hint that IllFormedQuestion was anything but a single TM
that decided a single set of TM computations (that's (tm, input)
pairs). But of course (and yes, I should have guessed) it isn't. What
Halting has to do depends, largely, on a property you call SRFHP. As
you agree above, a machine to compute SRFHP needs to know tm, input and
H -- the putative halting decider. The clearest way to show that is to
write SRFHP(H, tm, input).

You say:

| Halting() returns true when:
| Halts(tm, input)&& Not(SRFHP)&& Valid(tm, input)

| and false otherwise

A clearer way to say this will shows what each machine needs to be given
to make its decision:

Halting(H, tm, input) returns true when:
Halts(tm, input) && Not(SRFHP(H, tm, input)) && Valid(tm, input)

Finally, IllFormedQuestion is now clearly dependent on some presumed H:

Boolean IllFormedQuestion(H, String tm, String input)
{
if (Not(Halting(H, tm, input)) && Not(NotHalting(H, tm, input)))
return true;
else // (Halting || NotHalting)
return false;
}

However (big however) now that we have all the ducks lined up we can see
what's really going on. What does

Not(Halting) && Not(NotHalting)

mean with

Halting = Halts && Not(SRFHP) && Valid
NotHalting = Not(Halts) && Not(SRFHP) && Valid

The potential for typos is huge, so lets have WolframAlpha do the
simplification for us:

http://www.wolframalpha.com/input/?i=not%28H+and+not%28S%29+and+V%29+and+not%28not%28H%29+and+not%28S%29+and+V%29

It tells us that you've written

Boolean IllFormedQuestion(H, String tm, String input)
{
if (SRFHP(H, tm, input) || Not(Valid))
return true;
else // (Halting || NotHalting)
return false;
}

I.e. apart for the syntactic validity check (which you can get rid of if
you choose an encoding that covers Sigma*) everything that matters about
this machine is in the mysterious SRFHP check. There were a lot of
smoke and mirrors involved, but InvalidInput is whatever SRFHP is.

<snip>

>> He had to express it
>> in terms of the multiple possible implementations of "Halting" because
>> you'd carefully hidden the fact that "Halting" is predicated on the same
>> old notion of an SRFHP test.
> Every time that I bring this up you keep saying that it is impossible
> to make a TM that decides SRFHP, when what you really meant was that
> it is impossible to make a universal TM that decides SRFHP for all
> inputs to all TMs.
>
> I say that X it true and you keep saying, no Y is false.

No, that's not what I am saying. Unfortunately, anything I say about
SRFHP has been a guess (because you have not defined it) and you'll say
I've guessed wrong whatever I say.

I am very happy to leave it here. All the magic happens in a predicate
call SRFHP. If you say enough about what that is, maybe you will get
some more comments.

>> Also, as I wrote in my comments about Rice's theorem, you do have an
>> instance of it because InvalidInput(H) has to decide if a given TM
>> behaves like the M(H) machine. Of course, since you can't show that
>> it's computable, you don't have a counter-example.
>>
> It seems to me that InvalidInput(tm, input) can correctly decide all
> possible InvalidInput to itself and its constituents. Antti Valmari
> said that this was decidable:
> (see the last line, I provided the rest for context)

You have no idea what it can decide because you don't know how to define
SRFHP(H, tm, i). If you did, surely you'd have defined it. That's why
you say only that "it seems" to you that it can decide something useful.

It can't correctly decide invalid input (English meaning) because there
is none, but given some definition of a computable SRFHP(H, tm, i) then,
of course, InvalidInput(H, tm , i) will be a decider for some set (the
same set as SRFHP minus syntactically invalid encodings).

> There are interesting Turing machines Halting(T,I) that always halt
> replying either true or false, so that if it replies "true" then T halts
> on I, but if it replies "false" then T does or does not halt on I. There
> also are interesting Turing machines NotHalting(T,I) that always halt
> replying either true or false, so that if it replies "true" then T does
> not halt on I, but if it replies "false" then T does or does not halt on
> I. (I tried to get close to your Halting and NotHalting. I hope I did
> not make typos.)
>
> Each such pair defines a set "InvalidInput" in the way you showed.
> The membership of the set is decidable.

The Halting and NotHalting machines are, as I've show, irrelevant. All
that matters is what exactly you mean by SRFHP.

--
Ben.

[Ross A. Finlayson]

Here, Halts() or Halts-Hat the estimation of Halts, is an intrinsic
feature of the language and encoding.

^
H() = estimated halting probability

For the single event, if it doesn't end the program each time, it goes
on, and if it keeps going, then that new program also keeps going, so
where it's different and a routine it defines its own range. When the
first and longest ends each of the terminal segments ends. Then, in
that the program space defines a population of programs, there are
statistical methods on them.

Then with these trivial machines with the blank tapes on write-once
media, there's actually nothing on a blank tape. Blank tapes start
all set to 1s.

In case this isn't enough definition in terms then I wrote some ten
posts to the recent thread on Rice's theorem, and there you would be
able to find these definitions, or I'll be happy to repeat them if you
ask, "trivial machine" here, "Halting Problem encoder/decoder
convention for estimating Halts()".

That is what it is.

The language, and the program model, and the data, defines Halts().

Sure, thanks,

Ross Finlayson

[Peter Olcott]

> if (Not(Halting(tm, input))&& Not(NotHalting(tm, input)))

> return true;
> else // (Halting || NotHalting)
> return false;
> }
>
> there was no hint that IllFormedQuestion was anything but a single TM
> that decided a single set of TM computations (that's (tm, input)
> pairs). But of course (and yes, I should have guessed) it isn't. What
> Halting has to do depends, largely, on a property you call SRFHP. As
> you agree above, a machine to compute SRFHP needs to know tm, input and
> H -- the putative halting decider. The clearest way to show that is to
> write SRFHP(H, tm, input).
>
> You say:
>
> | Halting() returns true when:
> | Halts(tm, input)&& Not(SRFHP)&& Valid(tm, input)
> | and false otherwise
>
> A clearer way to say this will shows what each machine needs to be given
> to make its decision:
>
> Halting(H, tm, input) returns true when:

> Halts(tm, input)&& Not(SRFHP(H, tm, input))&& Valid(tm, input)

>
> Finally, IllFormedQuestion is now clearly dependent on some presumed H:
>
> Boolean IllFormedQuestion(H, String tm, String input)
> {

> if (Not(Halting(H, tm, input))&& Not(NotHalting(H, tm, input)))

> return true;
> else // (Halting || NotHalting)
> return false;
> }
>
> However (big however) now that we have all the ducks lined up we can see
> what's really going on. What does
>

> Not(Halting)&& Not(NotHalting)

>
> mean with
>
> Halting = Halts&& Not(SRFHP)&& Valid

> NotHalting = Not(Halts)&& Not(SRFHP)&& Valid

>
> The potential for typos is huge, so lets have WolframAlpha do the
> simplification for us:
>
> http://www.wolframalpha.com/input/?i=not%28H+and+not%28S%29+and+V%29+and+not%28not%28H%29+and+not%28S%29+and+V%29
>
> It tells us that you've written
>
> Boolean IllFormedQuestion(H, String tm, String input)
> {
> if (SRFHP(H, tm, input) || Not(Valid))
> return true;
> else // (Halting || NotHalting)
> return false;
> }

Boolean IllFormedQuestion(H, String tm, String input)
{

if (SRFHP(H, tm, input) || Not(Valid(tm)))
return true;
else // (Halting(tm, input) || NotHalting(tm, input))
return false;
}


Yes this is it. Your way of showing the dependency seems ideal.

Semantically invalid input (English meaning)
It does not bother with Syntactically Invalid Input
(English meaning) because it has Valid(tm, input) for that.

> is none, but given some definition of a computable SRFHP(H, tm, i) then,
> of course, InvalidInput(H, tm , i) will be a decider for some set (the
> same set as SRFHP minus syntactically invalid encodings).
>
>> There are interesting Turing machines Halting(T,I) that always halt
>> replying either true or false, so that if it replies "true" then T halts
>> on I, but if it replies "false" then T does or does not halt on I. There
>> also are interesting Turing machines NotHalting(T,I) that always halt
>> replying either true or false, so that if it replies "true" then T does
>> not halt on I, but if it replies "false" then T does or does not halt on
>> I. (I tried to get close to your Halting and NotHalting. I hope I did
>> not make typos.)
>>
>> Each such pair defines a set "InvalidInput" in the way you showed.
>> The membership of the set is decidable.
> The Halting and NotHalting machines are, as I've show, irrelevant. All
> that matters is what exactly you mean by SRFHP.
>

Yes. And the specification of this depends upon the mutually agreed
conception that a TM can Decide(CommonEnglish) the SRFHP, even if it can
not Decide(TheoryOfComputation)the SRFHP.

It can do this by representing Decide(CommonEnglish)as an internal state.

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/4/2012 8:31 AM, Ben Bacarisse wrote:

<snip>

>> Right. Please start doing that. Write:
>>
>> M(H, i):
>> if H(i, i) loop
>> else halt
>>
>> to show that M is a function of H. The key computation is then H(M(H),
>> M(H)). (This partial application of M only one argument confuses some
>> people, but it's perfectly well-defined. If you prefer, think of H as a
>> subscript: M_H(i).)
>
> M(TM h, String input):
> if h(input, input) loop
> else halt

Exactly. Much clearer.

> What about the rest of this syntax?
>
> <ForAll> tm, input <ElementOfSet> Sigma*
> <ForAll> h <ElementOfSet> Turing Machines
> ~<ThereExists> h(M, M) <LogicalEntailment> Halts(tm, input)

I can't ascribe any meaning to this so I can't help. Did you mean to
write h(M(h), M(h))? What does it even mean to write a TM computation
on the left of |=? Which of the many possible M "templates" do you
mean? Etc. I find this completely unhelpful.

> h(M, M) means the return value for the invocation of h(M, M).
>
>> <snip>
>>> Although there may be no InvalidInput decider for the input to all
>>> TMs, it would seem that there could be one for *all* the input of any
>>> particular TM. How hard could it be to check and see if something
>>> mucks with its own final state?
>> As hard a Rice's theorem says it is. What you are calling (elsewhere)
>> SRFHP is not a property of the input machine itself, but a property of
>> its behaviour. For every M(H) there is whole set of M2(H), M3(H),
>> ... that behave in exactly the same way but don't "look like" M(H).
>>
>> There's an irony here. Your desire to detect M(H) and "deal with it" is
>> exactly the way Daryl showed that is a chain of ever better putative
>> halting deciders. Why, given this similarity, do you reject his proof?

> Either SRFHP exists for a (TM, tm, input) triple or it does not, thus
> no improvement is possible, one can merely define another (TM2, tm,
> input) triple where SRFHP does not apply, for the same (tm, input)
> pair.

Ah, his argument does not apply by definition. You've defined SRFHP to be
the perfect invalidity checker, so no improvement is possible, but that
won't wash because Daryl's argument shows that there is no perfect
SRFHP. If there is one at all, there is always a better one, just as
there is no largest prime. Defining p as the largest prime does not
get round the problem -- it just means the definition is nonsense.

>>> Also it would seem to be possible that a TM could have an intermediate
>>> state that does correctly represent whether or not its input would
>>> halt or loop.** It seems that the only limitation is that this TM can
>>> not represent the halting behavior of its input as its own final
>>> state.
>> Ah, a TM with a soul that knows the truth. You should switch to poetry.
> Merely an intermediate state that knows the truth.
> Try and show a valid counter-example how this would not be possible
> within SRFHP.

Such a machine would permit another in which this internal state was
actually an accept or reject state. We know no such machine is
possible.

--
Ben.

[Ben Bacarisse]

Internal states that don't result in a "report" can be thought of as
representing anything you like. I really don't mind. I have a TM right
here with a set of internal states that represent next week winning
lottery numbers.

--
Ben.

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/4/2012 10:47 AM, Ben Bacarisse wrote:

<snip>

The comment is wrong. It still refers to a machine that is not
relevant. The else branch is Not(SRFHP(H, tm, input)) && Valid(tm).
(Except of course, you tell us below that SRFHP is not a TM at all!)

> Yes this is it. Your way of showing the dependency seems ideal.

But now pointless because of what follows.

<snip>

>> The Halting and NotHalting machines are, as I've show, irrelevant. All
>> that matters is what exactly you mean by SRFHP.
>>
> Yes. And the specification of this depends upon the mutually agreed
> conception that a TM can Decide(CommonEnglish) the SRFHP, even if it
> can not Decide(TheoryOfComputation)the SRFHP.

Who agreed? Right up the this point I, at least, though you meant that
SRFHP was a conventional TM that decided(TheoryOfComputation) a set.
Apparently it is one that just knows things it can't report. That makes
it interesting to theologians, but irrelevant to (most) mathematicians.

> It can do this by representing Decide(CommonEnglish)as an internal
> state.

None of this sophistry has any impact on the theorems of computer
science. I take it you are withdrawing the idea that you have a
counter-example to Rice's theorem since that uses the CS meaning of
decide?

This would seem to close the discussion. You have some other notion of
"decide" which permits a TM to "know" things it can't decide in the CS
meaning of the term. That seems silly, but by all means stick with it.
It has no impact on the topics of comp.theory or sci.logic.

--
Ben.

[Ralph Hartley]

On 05/03/2012 06:47 PM, Peter Olcott wrote:
> Since you seem to be able to follow plain English, I will pose this more
> difficult question to you.
>
> It seems to me that the theory of computation conflates two different
> common English terms into a single term:
> (1) The Common English term {Decide} meaning essentially to select from
> alternatives.
> (2) The Common English term {Report} to provide a response.
> It seems to me that a Decider(TheoryOfComputation) must
> Decide(CommonEnglish) and Report(CommonEnglish).

Common English usage varies a lot. Let's call it Decide(Peter Olcott)
for now.

> So when it is said that there can be no Decider(TheoryOfComputation) for
> the self-reference form of the Halting Problem, this does not logically
> entail that a tm can not Decide(CommonEnglish) the self-reference form
> of the Halting Problem.
>
> It would seem to me that it would be possible for a TM to have as an
> intermediate state within itself, and not within the interface to the
> outside world (final states of {accept, reject}) a pair of states
> representing the actual Decide(CommonEnglish) of the halting for any
> possible input.

Do you mean that the TM always "knows" the answer, but sometimes reports
something else?

No. That is not possible.

Given a TM that can Decide(Peter Olcott) something, it is fairly easy to
construct a new TM that Reports(Peter Olcott) what the old one decides,
and therefore Decides(TheoryOfComputation).

Since the latter can't exist, neither can the former.

Many uncomputability proofs have the same form. If we were given a TM
that performs task A, we could construct a TM that
Decides(TheoryOfComputation) the halting problem. Therefor no TM can
perform task A.

Ralph Hartley

[Ralph Hartley]

On 05/04/2012 07:51 AM, Peter Olcott wrote:
> Although there may be no InvalidInput decider for the input to all TMs,
> it would seem that there could be one for *all* the input of any
> particular TM. How hard could it be to check and see if something mucks
> with its own final state?

Did you really say "How hard could it be"?

If there were a mathematics version of the "Darwin Awards", that phrase
would appear at least as often as "Watch this!", in the physical version.

Depending on exactly what you mean, it could be impossible. That's how hard.

Ralph Hartley

[Peter Olcott]

~<ThereExists> h(M(h, input), M(h, input)) <LogicalEntailment> Halts(tm,
input)

The last line indicates that there does not exist a return value
from the invocation of h(M(h, input), M(h, input))
that corresponds to Halts(tm, input) // The actual behavior of tm on input

>> h(M, M) means the return value for the invocation of h(M, M).
>>
>>> <snip>
>>>> Although there may be no InvalidInput decider for the input to all
>>>> TMs, it would seem that there could be one for *all* the input of any
>>>> particular TM. How hard could it be to check and see if something
>>>> mucks with its own final state?
>>> As hard a Rice's theorem says it is. What you are calling (elsewhere)
>>> SRFHP is not a property of the input machine itself, but a property of
>>> its behaviour. For every M(H) there is whole set of M2(H), M3(H),
>>> ... that behave in exactly the same way but don't "look like" M(H).
>>>
>>> There's an irony here. Your desire to detect M(H) and "deal with it" is
>>> exactly the way Daryl showed that is a chain of ever better putative
>>> halting deciders. Why, given this similarity, do you reject his proof?
>> Either SRFHP exists for a (TM, tm, input) triple or it does not, thus
>> no improvement is possible, one can merely define another (TM2, tm,
>> input) triple where SRFHP does not apply, for the same (tm, input)
>> pair.
> Ah, his argument does not apply by definition. You've defined SRFHP to be
> the perfect invalidity checker, so no improvement is possible, but that
> won't wash because Daryl's argument shows that there is no perfect
> SRFHP.

For any single element of the set of Turing Machines, h it would seem
that h.SFGHP(tm, input) could exist. // member function of object notation
Also this h.SRFHP(tm, input) could perfectly decide all (tm, input) pairs.

> If there is one at all, there is always a better one, just as
> there is no largest prime. Defining p as the largest prime does not
> get round the problem -- it just means the definition is nonsense.

I really don't think so.
For any specific h, there is a well-defined immutable set of h.SRFHP(tm,
input).

>>>> Also it would seem to be possible that a TM could have an intermediate
>>>> state that does correctly represent whether or not its input would
>>>> halt or loop.** It seems that the only limitation is that this TM can
>>>> not represent the halting behavior of its input as its own final
>>>> state.
>>> Ah, a TM with a soul that knows the truth. You should switch to poetry.
>> Merely an intermediate state that knows the truth.
>> Try and show a valid counter-example how this would not be possible
>> within SRFHP.
> Such a machine would permit another in which this internal state was
> actually an accept or reject state. We know no such machine is
> possible.
>

I will have to think about that one.

Merely strip off the transition to the final state such that we now have
a machine that is semantically equivalent to the first machine except
with two fewer states chopped off the end?

[Peter Olcott]

Depending on how one defines one's terms. It could simply toggle its
final Boolean output such that this final output is always the opposite
of the correct value determined in the preceding step.

> Given a TM that can Decide(Peter Olcott) something, it is fairly easy
> to construct a new TM that Reports(Peter Olcott) what the old one
> decides, and therefore Decides(TheoryOfComputation).
>
> Since the latter can't exist, neither can the former.

Just chop off the last two states. Ben pointed this out.

[Peter Olcott]

Are we back again to Rice's Theorem?

[Peter Olcott]

On 5/4/2012 1:11 PM, Ralph Hartley wrote:

This is the point where I think that I might have something new.
Do you have a valid counter-example of the SRFHP where a TM can
not determine that it can not determine the result?

[George Greene]

On May 3, 8:53 pm, Peter Olcott <OCR4Screen> wrote:
> The InvalidInput Decider correctly decides the property of InvalidInput for Sigma*

THERE IS NO SUCH THING AS "Invalid Input" FOR Sigma* !!
AT BEST there is invalid input FOR SPECIFIC TMs that represent partial
functions,
LIKE DIVISION. You could reasonably flag a zero denominator as
invalid input.
You could also prove it was REALLY "invalid", however, BY FAILING TO
HALT ON IT.
Well, not really "prove" (proofs are supposed to be finite) but
"indicate" or do the
APPROPRIATE thing.

> This would seem to exactly refute what Dexter Kozen provides as the
> specification of Rice's Theorem: "Every nontrivial property of the r.e.
> sets is undecidable". (page 245, 1997 edition of Automata and
> Computability).

As I've told you 5 times already, YOU DO NOT KNOW HOW TO *PARSE* THIS
SENTENCE.

>
> (1) Its decidable

No, it isn't.

> (2) Its a non trivial property

IT IS NOT A PROPERTY *OF THE R.E. SETS* AT ALL, DUMBASS!!!!
IT IS A PROPERTY OF *SOME STRINGS* versus ONE r.e. set (wherefore IT
IS NECESSARILY decidable).

> (3) If its (a non trivial property) of a r.e set then it
>      would seem to refute Rice's Theorem

NO, dumbass, If it were a non-trivial property of THE r.e. setS,
PLURAL, TAKEN AS THE ENTIRE INFINITE *CLASS* of r.e. sets, THEN it
could be a counter-example to Rice's Theorem.

[George Greene]

On May 3, 7:22 pm, Peter Olcott <OCR4Screen> wrote:
> I am thinking that any specification of a TM should not

SHUT UP. You don't GET TO SAY ANYthing about what "any"
"specification of a TM" should do. In the first place, TMs DON'T HAVE
"specifications"! "Specification" MEANS SOMETHING ELSE!

TMs have CODE!

TMs are PROGRAMS!

A "specification" (if any) IS COMPLETELY SEPARATE FROM
the program or the TM and is something that the TM may OR MAY NOT
*meet*, "match", or "satisfy". Or "belong to" if you think of the
specification
as being satisfied by many different programs that all belong to the
SET of
programs matching the specification.

If you can't properly use the basic vocabulary then you have no hope.

[Ralph Hartley]

On 05/04/2012 03:17 PM, Peter Olcott wrote:
> On 5/4/2012 12:23 PM, Ralph Hartley wrote:

>> Do you mean that the TM always "knows" the answer, but sometimes
>> reports something else?
>>
>> No. That is not possible.
>>
> Depending on how one defines one's terms. It could simply toggle its
> final Boolean output such that this final output is always the opposite
> of the correct value determined in the preceding step.

Huh? Are you trying to convert a Decider(TheoryOfComputation) into
something that is only a Decider(Peter Olcott)? Why?

Since the former can't exist, how would that help?

The important point is that I can do the *reverse*. I can convert any
Decider(Peter Olcott) into a Decider(TheoryOfComputation). I can't build
a Decider(TheoryOfComputation) by any means at all. But if a
Decider(Peter Olcott) existed, then I could.

Therefor, no Decider(Peter Olcott) exists.

>> Given a TM that can Decide(Peter Olcott) something, it is fairly easy
>> to construct a new TM that Reports(Peter Olcott) what the old one
>> decides, and therefore Decides(TheoryOfComputation).
>>
>> Since the latter can't exist, neither can the former.
>
> Just chop off the last two states. Ben pointed this out.

Didn't he also make it clear that this proves no Decider(Peter Olcott)
exists? That's how I understood his post.

That kind of proof is so common, I might not have noticed if he left off
the final step.

Ralph Hartley

[Peter Olcott]

On 5/4/2012 3:24 PM, Ralph Hartley wrote:
> On 05/04/2012 03:17 PM, Peter Olcott wrote:
>> On 5/4/2012 12:23 PM, Ralph Hartley wrote:
>
>>> Do you mean that the TM always "knows" the answer, but sometimes
>>> reports something else?
>>>
>>> No. That is not possible.
>>>
>> Depending on how one defines one's terms. It could simply toggle its
>> final Boolean output such that this final output is always the opposite
>> of the correct value determined in the preceding step.
>
> Huh? Are you trying to convert a Decider(TheoryOfComputation) into
> something that is only a Decider(Peter Olcott)? Why?
>

If one considers a TM to be an actual device that is built then it is
possible to build such a device that gets the wrong answer because the
device fails to meet its original specifications.

[Ben Bacarisse]

Apart from the odd "<forall> h ~<exists> h..." that sounds pretty much
like a statement of the halting theorem. Actually, I don't think your
words correspond to your symbols because "entails" is not the same as
"corresponds" but I find it hard to care. I haven't a clue what you are
trying to say anymore since you left the world of mathematics.

Who knows? All you've said about SRFHP is that it is the same as
InvalidInput. The two are circularly defined by each other without any
reference to what they actually need to compute.

I'd say "define it" but you are obviously preparing an exit path by
talking (elsewhere) about how SRFHP can know things it can't decide.

Of course, you have defined it once, but that did not work out. All the
posts since you were going on about InvalidInput were for nothing,
because SRFHP is the same as InvalidInput as I showed in another post.

>> If there is one at all, there is always a better one, just as
>> there is no largest prime. Defining p as the largest prime does not
>> get round the problem -- it just means the definition is nonsense.
> I really don't think so.
> For any specific h, there is a well-defined immutable set of
> h.SRFHP(tm, input).

You don't know that because you don't know what SRFHP is. If you think
you do know what it is, tell us. I've guessed what you mean by it (and
that guess has the properties you are objecting to here) but I don't
think anyone (even you) knows what it actually means.

>>>>> Also it would seem to be possible that a TM could have an intermediate
>>>>> state that does correctly represent whether or not its input would
>>>>> halt or loop.** It seems that the only limitation is that this TM can
>>>>> not represent the halting behavior of its input as its own final
>>>>> state.
>>>> Ah, a TM with a soul that knows the truth. You should switch to poetry.
>>> Merely an intermediate state that knows the truth.
>>> Try and show a valid counter-example how this would not be possible
>>> within SRFHP.
>> Such a machine would permit another in which this internal state was
>> actually an accept or reject state. We know no such machine is
>> possible.
>>
> I will have to think about that one.
>
> Merely strip off the transition to the final state such that we now
> have a machine that is semantically equivalent to the first machine
> except with two fewer states chopped off the end?

I don't know what this means. But does it matter? I thought the whole
point of ascribing a soul to a machine is so that you can say it knows
things it can't report. A machine that is able to be true to its soul
can't exist (because it would be able to decide things that are not
decidable) and one that lies about what is knows in its soul
is indistinguishable from one that is just wrong -- and they are
ten-a-penny.

--
Ben.

[Ben Bacarisse]

Who cares what it does? It can do anything it likes since the one thing
we know about it is that it can't always, in all cases, get the right
answer. You've left mathematics and have entered the world of theology.
In that world, you a free to ascribe any knowledge you like to what you
call "internal" states of TMs. What matters in the world of mathematics
is what sets TMs can decide. (I'm not going to play the game of tagging
well-defined technical terms just so you can invent your own silly
versions -- you know what decides means in mathematics.)

>> Given a TM that can Decide(Peter Olcott) something, it is fairly
>> easy to construct a new TM that Reports(Peter Olcott) what the old
>> one decides, and therefore Decides(TheoryOfComputation).
>>
>> Since the latter can't exist, neither can the former.
>
> Just chop off the last two states. Ben pointed this out.

That's misleading. It sounds like I pointed something out that fixes
Ralph's refutation. I simply pointed out the same problem. You said
something (which I don't understand) about chopping off states.

<snip>
--
Ben.

[Peter Olcott]

by corresponds I mean a mathematical mapping. Is there a symbol for this?

No, you have seemed to have correctly refuted that one.

>
> Of course, you have defined it once, but that did not work out. All the
> posts since you were going on about InvalidInput were for nothing,
> because SRFHP is the same as InvalidInput as I showed in another post.

Sure.

>>> If there is one at all, there is always a better one, just as
>>> there is no largest prime. Defining p as the largest prime does not
>>> get round the problem -- it just means the definition is nonsense.
>> I really don't think so.
>> For any specific h, there is a well-defined immutable set of
>> h.SRFHP(tm, input).
> You don't know that because you don't know what SRFHP is. If you think
> you do know what it is, tell us. I've guessed what you mean by it (and
> that guess has the properties you are objecting to here) but I don't
> think anyone (even you) knows what it actually means.

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

I have provided this concrete example a thousand times at least.
Even a single instance conclusively proves that a conception is fulfilled.

You have been talking like because a thing has not
been neatly generalized into a concise package that
this entails that such a thing can not possibly exist at all.

That would be incorrect reasoning.

>>>>>> Also it would seem to be possible that a TM could have an intermediate
>>>>>> state that does correctly represent whether or not its input would
>>>>>> halt or loop.** It seems that the only limitation is that this TM can
>>>>>> not represent the halting behavior of its input as its own final
>>>>>> state.
>>>>> Ah, a TM with a soul that knows the truth. You should switch to poetry.
>>>> Merely an intermediate state that knows the truth.
>>>> Try and show a valid counter-example how this would not be possible
>>>> within SRFHP.
>>> Such a machine would permit another in which this internal state was
>>> actually an accept or reject state. We know no such machine is
>>> possible.
>>>
>> I will have to think about that one.
>>
>> Merely strip off the transition to the final state such that we now
>> have a machine that is semantically equivalent to the first machine
>> except with two fewer states chopped off the end?
> I don't know what this means. But does it matter? I thought the whole
> point of ascribing a soul to a machine is so that you can say it knows
> things it can't report.

You are the one with that screwy terminology,
I was only talking about an internal state.
It looks like you may have shown that this idea
will not work either, at least not the simplest
conception of it.

[Joshua Cranmer]

On 5/4/2012 6:05 PM, Peter Olcott wrote:
> On 5/4/2012 3:42 PM, Ben Bacarisse wrote:
>> You don't know that because you don't know what SRFHP is. If you think
>> you do know what it is, tell us. I've guessed what you mean by it (and
>> that guess has the properties you are objecting to here) but I don't
>> think anyone (even you) knows what it actually means.
>
> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }
>
> I have provided this concrete example a thousand times at least.
> Even a single instance conclusively proves that a conception is fulfilled.
>
> You have been talking like because a thing has not
> been neatly generalized into a concise package that
> this entails that such a thing can not possibly exist at all.
>
> That would be incorrect reasoning.

An example doesn't provide a definition. The essential problem--what you
are missing--is that it is generally impossible to talk about any
implications of SRFHP without any definition of what it is. What is
truly desired is a definition of SRFHP, as in "An example is in SRFHP if
_________." As long as the blank amounts to "Peter Olcott says it is,"
it is impossible to discuss the ramifications of SRFHP, in particular
some key issues like "membership in SRFHP is decidable."

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

[Peter Olcott]

SRFHP is common knowledge in many textbooks.
It is what is referred to whenever HP is discussed.

[Peter Olcott]

The simplest possible case of proving your point that a TM could not
internally represent the correct halting state as long as it does not
report this in its final states is to have two internal states that
immediately precede the final states. Now when we chop off the last two
states we have a semantically identical machine that can now be fooled
by Pathological Self-Reference.

[George Greene]

On May 4, 7:05 pm, Peter Olcott <OCR4Screen> wrote:
> M( String Input )
> {
> if ( H( Input, Input ) )
>    Loop Forever;
> else
>    Exit;
>
> }
>
> I have provided this concrete example a thousand times at least.

No you haven't. You've provided it at most a hundred. The first 900
times, you were calling it Halts(,) instead of H(,).
This is progress. Congratulations. Maybe eventually you will figure
out that the reason why it is called H is that it is
A VARIABLE and NOT any CONSTANT individual Turing Machine. H here
represents ANY Turing Machine, ANY ARBITRARY
Turing Machine.

> Even a single instance conclusively proves that a conception is fulfilled.

Uh, no, not exactly. H(,) is NOT an instance of anything. H is just
a HOLE in a TEMPLATE.
To get an actual TM, you have TO PICK A REAL H. You have to
INSTANTIATE H. *YOU* have to supply the TM
that is the instance of H. However, IF YOU DON'T DO THAT, if you just
prove something about H(,) WITHOUT CARING
what TM H(,) is -- and here, WE HAVE DONE THAT: we have proved that
the truth-value of H(i,i) IS ALWAYS THE OPPOSITE
of Halts(M,i) -- this is true FOR EVERY H. In fact, if you code 0 as
false and 1 as true, then you can code the denial of a
truth-value t as 1-t, and then you get the rather fascinating result
that you can code looping as a truth-value of 1/2, which
means that when H(i,i) loops, M(M,i) LOOPS TOO, so the result M(M,i) =
1-H(i,i) CONTINUES to hold.

[George Greene]

On May 4, 9:31 pm, Peter Olcott <OCR4Screen> wrote:
> The simplest possible case of proving your point that a TM could not
> internally represent the correct halting state as long as it does not
> report this in its final states is to have two internal states that
> immediately precede the final states. Now when we chop off the last two
> states we have a semantically identical machine that can now be fooled
> by Pathological Self-Reference.

This is incoherent. You really need to shut up about states and
return values.
The returned value is a string and it is whatever string is left on
the tape when
the machine halts. If the machine DOESN'T halt then it DOESN'T return
a value.
This is NOT the ONLY way to do it but it IS the only way that allows
us to focus
on what the real issues are instead of you continually bringing up
irrelevant bullshit.

Once again: a TM represents a [partial] function from finite strings
to finite strings.
For any given [finite] input-string as an argument, the value that the
string-function-being-implemented-by-the-TM
associates with that argument is the [necessarily also finite] string
left printed on the tape when the machine halts.
Questions about "invalid" input are irrelevant -- even when the
machine fails to halt, that is a normal behavior for TMs
(many useful TMs, like a division TM, fail to halt on some inputs).
While, normally, the fact that the function doesn't
return a value for some supplied argument would imply that the
argument was not in its domain, here, we are viewing
all of sigma* as the domain and simply insisting that the function IS
PARTIAL, i.e., for some supplied arguments, no
value is defined, or the value is defined AS undefined (NO, that is
NOT a paradox).

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/4/2012 3:42 PM, Ben Bacarisse wrote:
>> Peter Olcott<OCR4Screen> writes:

<snip>

>>> For any single element of the set of Turing Machines, h it would seem
>>> that h.SFGHP(tm, input) could exist. // member function of object notation
>>> Also this h.SRFHP(tm, input) could perfectly decide all (tm, input)
>>> pairs.
>> Who knows? All you've said about SRFHP is that it is the same as
>> InvalidInput. The two are circularly defined by each other without any
>> reference to what they actually need to compute.
>>
>> I'd say "define it" but you are obviously preparing an exit path by
>> talking (elsewhere) about how SRFHP can know things it can't decide.
>
> No, you have seemed to have correctly refuted that one.

That's a shame. I though it was all over. So we are back to deciders
as we know them, and we have a computation

SFGHP(h, tm, input)

that must actually report something. You tell us a tiny bit below...

>> Of course, you have defined it once, but that did not work out. All the
>> posts since you were going on about InvalidInput were for nothing,
>> because SRFHP is the same as InvalidInput as I showed in another post.
> Sure.
>
>>>> If there is one at all, there is always a better one, just as
>>>> there is no largest prime. Defining p as the largest prime does not
>>>> get round the problem -- it just means the definition is nonsense.
>>> I really don't think so.
>>> For any specific h, there is a well-defined immutable set of
>>> h.SRFHP(tm, input).
>> You don't know that because you don't know what SRFHP is. If you think
>> you do know what it is, tell us. I've guessed what you mean by it (and
>> that guess has the properties you are objecting to here) but I don't
>> think anyone (even you) knows what it actually means.
>
> M( String Input )
> {
> if ( H( Input, Input ) )
> Loop Forever;
> else
> Exit;
> }

(We've lost the H parameter again. It's much clearer with it.)

> I have provided this concrete example a thousand times at least.
> Even a single instance conclusively proves that a conception is
> fulfilled.

A single instance gives a single instance. Of the infinity of possible
inputs to SRFHP, you've given us one -- just one -- data point.

Presumably this example means that SRFHP(H, M(H), H(M)) returns true,
yes? Well what about

M1(H, input)
{ if (H(input, input) && H(input, input)) loop;
else halt;
}

What should SRFHP(H, M(H), M1(H)) return? And, what about

M2(H, input)
{ while (Halts(input, input)) do nothing done;
halt;
}

and SRFHP(H, M1(H), M2(H)) or SRFHP(H, M2(H), M(h))? Do you see a
pattern? Do you see a problem?

This, by the way, is still a guess. You've simply not said what you want
SRFHP to do, let along how it might do it.

> You have been talking like because a thing has not
> been neatly generalized into a concise package that
> this entails that such a thing can not possibly exist at all.
>
> That would be incorrect reasoning.

It would be, but I'm not doing that. Not one of the people who have
been disagreeing with you have said that *some* sort of SRFHP can't
exit. The existence of *something* like that is not in doubt. But I
know that you don't want what your interlocutors define it to be. For
one thing, it leads to this idea you've rejected of a chain of better
and better putative halting deciders. You probably want one that jumps
to the end of the chain in a single leap -- that is what is in doubt.
Well, that's a bit mild. Such a thing does not exit. (The argument has
been presented before so I won't repeat it).

You can side-step this definition by defining SRFHP some other way. If
you do that properly, the consequences of the definition can be
examined. In particular, it may be possible to tell if a machine
matching the definition exists.

<snip>
--
Ben.

[Joshua Cranmer]

No, not quite. *An example* is what is present. It's not a definition,
nor is it the kind of in-depth treatment you would like us to believe.
Most presentations of the Halting problem just construct the
counterexample and say "QED"...

Take, say, the definition of the complexity class P: it is the class of
all languages that can be decided by a [deterministic] Turing machine in
polynomial time. Your "definitions" of SRFHP would be analogous to
defining P by saying "real linear programming is in P" [1]. It's not a
false statement, but nor is it one that gives you an idea of what SRFHP
is really like.

So I implore you: give a clear, concise definition of SRFHP.

[1] If you know your advanced complexity classes, I hope you get a laugh
out of this. If you don't... look up P-complete.

[Bryan]

Peter Olcott wrote:
> On 5/4/2012 3:24 PM, Ralph Hartley wrote:
>
> > On 05/04/2012 03:17 PM, Peter Olcott wrote:
> >> On 5/4/2012 12:23 PM, Ralph Hartley wrote:
>
> >>> Do you mean that the TM always "knows" the answer, but sometimes
> >>> reports something else?
>
> >>> No. That is not possible.
>
> >> Depending on how one defines one's terms. It could simply toggle its
> >> final Boolean output such that this final output is always the opposite
> >> of the correct value determined in the preceding step.
>
> > Huh? Are you trying to convert a Decider(TheoryOfComputation) into
> > something that is only a Decider(Peter Olcott)? Why?
>
> If one considers a TM to be an actual device that is built then it is
> possible to build such a device that gets the wrong answer because the
> device fails to meet its original specifications.

If your goal, Peter, was to show that you can build devices that fail
to meet their specifications, you could have saved an awful lot of
time and effort by just saying so out front. Why pollute the group
with nonsensical objections to the theorems of Turing and Rice when
all you have are bugs?

Now before you throw another of your e-tantrums about how no one is
taking your posts seriously, let me recommend you re-read what Ralph
has offered. You cannot have it both ways. He went to the heart of
your misunderstanding and you responded with trivia. He trounced your
trivia and you pretended that he failed to deal with your real issue.

Peter, even if you succeed in specifying your "InvalidInput Decider",
you'd still have the problem of showing it exists. Over and over
people on these groups have worked to clean up your specifications to
the point that we can reason from them, and then the result is either
that they don't support your claims or that the specified objects do
not exists.

-Bryan

[Peter Olcott]

On 5/5/2012 2:16 AM, Bryan wrote:
> Peter Olcott wrote:
>> On 5/4/2012 3:24 PM, Ralph Hartley wrote:
>>
>>> On 05/04/2012 03:17 PM, Peter Olcott wrote:
>>>> On 5/4/2012 12:23 PM, Ralph Hartley wrote:
>>>>> Do you mean that the TM always "knows" the answer, but sometimes
>>>>> reports something else?
>>>>> No. That is not possible.
>>>> Depending on how one defines one's terms. It could simply toggle its
>>>> final Boolean output such that this final output is always the opposite
>>>> of the correct value determined in the preceding step.
>>> Huh? Are you trying to convert a Decider(TheoryOfComputation) into
>>> something that is only a Decider(Peter Olcott)? Why?
>> If one considers a TM to be an actual device that is built then it is
>> possible to build such a device that gets the wrong answer because the
>> device fails to meet its original specifications.
> If your goal, Peter, was to show that you can build devices that fail

My goal here was to merely correctly refute the above statement:
That a TM can know the answer AND report something else.

[Peter Olcott]

Complexity only pertains to the amount of time or space that an
algorithm or machine will take right? If this is the case, then how is
this relevant, as long as the TM can provide an answer in less than
infinite time, then my point is made.

[Peter Olcott]

I could not claim that I have provided the other one more than a
thousand times.
The other one is clearer with the H parameter, yet it makes the next
lines of
the specification syntactically messy. I am working through that.

>> I have provided this concrete example a thousand times at least.
>> Even a single instance conclusively proves that a conception is
>> fulfilled.
> A single instance gives a single instance. Of the infinity of possible
> inputs to SRFHP, you've given us one -- just one -- data point.
>
> Presumably this example means that SRFHP(H, M(H), H(M)) returns true,
> yes? Well what about
>
> M1(H, input)

> { if (H(input, input)&& H(input, input)) loop;
> else halt;
> }
That answer is obvious.

> What should SRFHP(H, M(H), M1(H)) return? And, what about
>
> M2(H, input)
> { while (Halts(input, input)) do nothing done;
> halt;
> }

That question is vague.
"do nothing done" has no unambiguous map to {accept, reject, loop} or
{halt, loop}

You also incorrectly invoked a mathematical function that is not a TM.
This may have been what you meant:

M2(H, input)
{
while (H(input, input))
;
halt;
}

This is semantically identical to the original and only differs by syntax.

> and SRFHP(H, M1(H), M2(H)) or SRFHP(H, M2(H), M(h))? Do you see a
> pattern? Do you see a problem?

I see the pattern and see no problem, at least in terms of the
specification of the problem.
All of these precisely map to the semantic meaning of the specification
of the problem that I already provided. I only have to improve the
syntax of this problem statement.

> This, by the way, is still a guess. You've simply not said what you want
> SRFHP to do, let along how it might do it.

I have said this many times, and it is perfectly clear, you pretend that
you don't know only because my mere syntax is not yet 100% perfectly
correct.

When I explain it in clear English you pretend that you have no idea of
what I am talking about because you pretend that my English
specification has thousands of ambiguities.

If one begins with the restriction that <Lucid English> words are *only*
allowed to have their common meaning (typically the first one in the
dictionary) unless explicitly stated otherwise, this restriction
inherently reduces thousands of otherwise possible ambiguities into few
or none.

// Function Prototype
Boolean SRFHP(String tm, String input)
if Halting(tm, input) != Halts(tm, input) return true

I did not even need <Lucid English> to say this.

It looks like we are back to the requirement that H must have some
internal state somewhere that knows Halts(tm, input). So we are going to
have to examine this reasoning in more depth.

>> You have been talking like because a thing has not
>> been neatly generalized into a concise package that
>> this entails that such a thing can not possibly exist at all.
>>
>> That would be incorrect reasoning.
> It would be, but I'm not doing that. Not one of the people who have
> been disagreeing with you have said that *some* sort of SRFHP can't
> exit. The existence of *something* like that is not in doubt. But I
> know that you don't want what your interlocutors define it to be. For
> one thing, it leads to this idea you've rejected of a chain of better
> and better putative halting deciders. You probably want one that jumps
> to the end of the chain in a single leap -- that is what is in doubt.

I don't think that either of these conceptions are valid.
It seems to me like the whole idea is like incrementally
moving from false to a point that is closer and closer to true.

[Joshua Cranmer]

Your ability to completely miss the point of an argument astounds me.
The relationship to complexity was only an example to illustrate the
absurdity of your "definition" (or lack thereof, really).

So I implore you: Give us a clear, concise definition of SRFP.

[Peter Olcott]

[Joshua Cranmer]

Thank you for making it perfectly clear that SRFHP is undecidable.

[Peter Olcott]

On 5/5/2012 11:18 AM, Joshua Cranmer wrote:
> On 5/5/2012 11:12 AM, Peter Olcott wrote:
>> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
>>> So I implore you: Give us a clear, concise definition of SRFP.
>>>
>> Halting(tm, input) != Halts(tm, input)
>
> Thank you for making it perfectly clear that SRFHP is undecidable.
>

Not Quite.
I don't think that is logically entailed.

[Peter Olcott]

On 5/5/2012 11:18 AM, Joshua Cranmer wrote:

> On 5/5/2012 11:12 AM, Peter Olcott wrote:
>> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
>>> So I implore you: Give us a clear, concise definition of SRFP.
>>>
>> Halting(tm, input) != Halts(tm, input)
>
> Thank you for making it perfectly clear that SRFHP is undecidable.
>

Try and show this using a valid counter-example.

[Joshua Cranmer]

From the definition of SRFHP, I can write the following code
DecideHalts(tm, input):
claim = Halting(tm, input)
if SRFHP(Halting, tm, input)
return not claim // SRFHP = true -> Halting != Halts
return claim // SRFHP = false -> Halting == Halts

DecideHalts clearly solves the halting problem, which means that either
Halting is not decidable or SRFHP is not decidable. If we presume
Halting to be decidable, this implies that SRFHP is not.

This result has been brought to you by disjunctive syllogism.

[Bryan]

Peter Olcott wrote:
> Bryan wrote:
> > Peter Olcott wrote:
> >> On 5/4/2012 3:24 PM, Ralph Hartley wrote:
>
> >>> On 05/04/2012 03:17 PM, Peter Olcott wrote:
> >>>> On 5/4/2012 12:23 PM, Ralph Hartley wrote:
> >>>>> Do you mean that the TM always "knows" the answer, but sometimes
> >>>>> reports something else?
> >>>>> No. That is not possible.
> >>>> Depending on how one defines one's terms. It could simply toggle its
> >>>> final Boolean output such that this final output is always the opposite
> >>>> of the correct value determined in the preceding step.
> >>> Huh? Are you trying to convert a Decider(TheoryOfComputation) into
> >>> something that is only a Decider(Peter Olcott)? Why?
> >> If one considers a TM to be an actual device that is built then it is
> >> possible to build such a device that gets the wrong answer because the
> >> device fails to meet its original specifications.
> > If your goal, Peter, was to show that you can build devices that fail
>
> My goal here was to merely correctly refute the above statement:
> That a TM can know the answer AND report something else.

Which has typical problems in your posts of being poorly defined,
personifying Turing machines, and failing to comprehend the statement.
Ralph attempted to make sense of and reason from your definitions, and
you had the opportunity to learn something from that. His statement
was not what you have there.

Ralph wrote, "Do you mean that the TM always 'knows' the answer, but
sometimes reports something else No. That is not possible". The reason
it's not possible is because if some TM computation can always find
the right answer, which is as close to "know" as TM's get, then *some*
TM can always report the right answer. We know no TM does.

Now how about instead of trying to dumb-down the discussion with buggy
TM's you look at that argument?

-Bryan

[Ben Bacarisse]

So what is the answer? The question is below, of course.

>> What should SRFHP(H, M(H), M1(H)) return? And, what about
>>
>> M2(H, input)
>> { while (Halts(input, input)) do nothing done;
>> halt;
>> }
> That question is vague.
> "do nothing done" has no unambiguous map to {accept, reject, loop} or
> {halt, loop}
>
> You also incorrectly invoked a mathematical function that is not a TM.
> This may have been what you meant:
>
> M2(H, input)
> {
> while (H(input, input))
> ;
> halt;
> }

Yes, thanks for fixing it. That was sloppy.

> This is semantically identical to the original and only differs by
> syntax.

Yay! Exactly.

>> and SRFHP(H, M1(H), M2(H)) or SRFHP(H, M2(H), M(h))? Do you see a
>> pattern? Do you see a problem?
> I see the pattern and see no problem, at least in terms of the
> specification of the problem.
> All of these precisely map to the semantic meaning of the
> specification of the problem that I already provided. I only have to
> improve the syntax of this problem statement.

Can you just confirm that SRFHP has to be able to spot these variations
and return true? That way we will have a few data points rather than
just one.

>> This, by the way, is still a guess. You've simply not said what you want
>> SRFHP to do, let along how it might do it.
> I have said this many times, and it is perfectly clear, you pretend
> that you don't know only because my mere syntax is not yet 100%
> perfectly correct.

But have I got it right now? SRFHP must detect every input that behaves
like M(H)? Does it need to detect anything else as "invalid"?

> When I explain it in clear English you pretend that you have no idea
> of what I am talking about because you pretend that my English
> specification has thousands of ambiguities.

If you want to think of it as pretending, I'm fine with that. If you
think you have explained everything perfectly well, you can stop
posting. There's no point in wasting time with someone who you think is
just pretending not to understand.

> If one begins with the restriction that <Lucid English> words are
> *only* allowed to have their common meaning (typically the first one
> in the dictionary) unless explicitly stated otherwise, this
> restriction inherently reduces thousands of otherwise possible
> ambiguities into few or none.
>
> // Function Prototype
> Boolean SRFHP(String tm, String input)
> if Halting(tm, input) != Halts(tm, input) return true

This is nonsense. See my reply to Joshua for the details.

> I did not even need <Lucid English> to say this.
>
> It looks like we are back to the requirement that H must have some
> internal state somewhere that knows Halts(tm, input). So we are going
> to have to examine this reasoning in more depth.

Soulful computing again. I thought this looked like the way out for
you. I would not have been so quick to abandon it. By the way, tell me
right away if your best understanding if SRFHP is as a machine that
"knows" things is can't report, because I'll stop asking for a proper
definition of it as something computable.

>>> You have been talking like because a thing has not
>>> been neatly generalized into a concise package that
>>> this entails that such a thing can not possibly exist at all.
>>>
>>> That would be incorrect reasoning.
>> It would be, but I'm not doing that. Not one of the people who have
>> been disagreeing with you have said that *some* sort of SRFHP can't
>> exit. The existence of *something* like that is not in doubt. But I
>> know that you don't want what your interlocutors define it to be. For
>> one thing, it leads to this idea you've rejected of a chain of better
>> and better putative halting deciders. You probably want one that jumps
>> to the end of the chain in a single leap -- that is what is in doubt.
>
> I don't think that either of these conceptions are valid.
> It seems to me like the whole idea is like incrementally
> moving from false to a point that is closer and closer to true.

Yes, it does seem like that doesn't it. I remember a colleague of mine
once telling a class not to be discouraged when a problem turns out to
be undecidable -- it just means there's no limit on how good a solution
you can have.

<snip>
--
Ben.

[Ben Bacarisse]

Joshua Cranmer <Pidg...@verizon.invalid> writes:

> On 5/5/2012 11:12 AM, Peter Olcott wrote:
>> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
>>> So I implore you: Give us a clear, concise definition of SRFP.
>>>
>> Halting(tm, input) != Halts(tm, input)
>
> Thank you for making it perfectly clear that SRFHP is undecidable.

I wrote the following before you posted your second reply, so just
consider this another way to look at it...

If we take Peter at his word (and, frankly, this response suggests we
probably can't) Halting is defined like this:

Halting(h, tm, input):
Halts(tm, input) && Not(SRFHP(h, tm, input)) && Valid(tm)

Now, if my algebra is correct, this latest stab in the dark means that
for some putative haling decider, h, SRFHP(h, tm, input) must be true if
the computation (tm, input) halts (assuming a valid tm). That sounds
screwy.

When the computation (tm, input) does not halt, the proffered equation
can't be solved (for valid tms). So, if you view his offering as at
least a partial definition, SRFHP must be true for halting computations
and must be undefined (looping) for non-halting ones.

This, of course, is a computable function (yay!) but it's not a decider
and it's got nothing to do with what Peter's been calling SRFHP up until
today.

As I suspect you know, he won't define SRFHP because even he has no idea
what it does (except for the specific instance he can cite --
repeatedly). He may throw a few things at the wall to see if any are
vague enough to keep the discussion going, but that's it. After months
of exchanges, all we know is what we knew on day one -- the "invalid
input" is a single instance of a computation, specific to every putative
halting decider.

--
Ben.

[Peter Olcott]

You must be much more specific about your objections without resorting
to mere unsupported assertions before I continue to even look at the
rest of your post.

[Peter Olcott]

On 5/5/2012 1:09 PM, Ben Bacarisse wrote:
> Joshua Cranmer<Pidg...@verizon.invalid> writes:
>
>> On 5/5/2012 11:12 AM, Peter Olcott wrote:
>>> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
>>>> So I implore you: Give us a clear, concise definition of SRFP.
>>>>
>>> Halting(tm, input) != Halts(tm, input)
>> Thank you for making it perfectly clear that SRFHP is undecidable.
> I wrote the following before you posted your second reply, so just
> consider this another way to look at it...
>
> If we take Peter at his word (and, frankly, this response suggests we
> probably can't) Halting is defined like this:
>
> Halting(h, tm, input):

> Halts(tm, input)&& Not(SRFHP(h, tm, input))&& Valid(tm)

>
> Now, if my algebra is correct, this latest stab in the dark means that
> for some putative haling decider, h, SRFHP(h, tm, input) must be true if
> the computation (tm, input) halts (assuming a valid tm). That sounds
> screwy.
>
> When the computation (tm, input) does not halt, the proffered equation
> can't be solved (for valid tms). So, if you view his offering as at
> least a partial definition, SRFHP must be true for halting computations
> and must be undefined (looping) for non-halting ones.
>
> This, of course, is a computable function (yay!) but it's not a decider
> and it's got nothing to do with what Peter's been calling SRFHP up until
> today.
>
> As I suspect you know, he won't define SRFHP because even he has no idea
> what it does (except for the specific instance he can cite --

What I provided was the exact mathematical specification of SRFHP:

Halting(tm, input) != Halts(tm, input)

Translating this into a TM will take additional steps.

If we agree on this point then we can proceed.

[Ben Bacarisse]

No, if I got the above right, its simple. Pointless but simple.

> If we agree on this point then we can proceed.

Did you read what I wrote? Does a partial definition count as an exact
specification? If so, sure, I can agree on that, but I'd have thought
you'd want SRFHP to compute a total function (give or take the value of
Valid(tm)).

<snip>
--
Ben.

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/5/2012 12:55 PM, Ben Bacarisse wrote:

<snip>

>> This is nonsense. See my reply to Joshua for the details.
> You must be much more specific about your objections without resorting
> to mere unsupported assertions before I continue to even look at the
> rest of your post.

If you are going to ignore your critics, you should at least snip the
parts you won't answer, so there is less for other people to wade
through. (OK, that may be no one by now, but it's still a good habit to
get into.)

--
Ben.

[Peter Olcott]

The specification is semantic it is NOT a Turing Machine.
You can't point out any gaps in this specification because there aren't
any.

[Peter Olcott]

People use the term {never} to mean infrequently and {always}
to mean often, you used the term nonsense with this same degree
of semantic imprecision.

Nonsense == the exactly same degree of semantic meaning as
the static hiss on the radio, just the hiss itself and not
the garbled words in-between.

[Ben Bacarisse]

It take it you still don't want to address any of the points you ignored?

--
Ben.

[Ben Bacarisse]

No, and it's not a banana either. Who said it was?

> You can't point out any gaps in this specification because there
> aren't any.

Eh? You don't bother to read replies any more do you? I may have got
it wrong, but I certainly did point out the gap.

--
Ben.

[Peter Olcott]

I will look at it again, it seemed that you were starting with a false
premise.

[Peter Olcott]

On 5/5/2012 1:09 PM, Ben Bacarisse wrote:

> Joshua Cranmer<Pidg...@verizon.invalid> writes:
>
>> On 5/5/2012 11:12 AM, Peter Olcott wrote:
>>> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
>>>> So I implore you: Give us a clear, concise definition of SRFP.
>>>>
>>> Halting(tm, input) != Halts(tm, input)
>> Thank you for making it perfectly clear that SRFHP is undecidable.
> I wrote the following before you posted your second reply, so just
> consider this another way to look at it...
>
> If we take Peter at his word (and, frankly, this response suggests we
> probably can't) Halting is defined like this:
>
> Halting(h, tm, input):

> Halts(tm, input)&& Not(SRFHP(h, tm, input))&& Valid(tm)

>
> Now, if my algebra is correct, this latest stab in the dark means that
> for some putative haling decider, h, SRFHP(h, tm, input) must be true if
> the computation (tm, input) halts (assuming a valid tm). That sounds
> screwy.

Exactly which formal error of reasoning is "sounds screwy" ?

> When the computation (tm, input) does not halt,

Do you mean !Halts(tm, input) ?

> the proffered equation
> can't be solved (for valid tms).

Do you mean can't be solved for Valid(tm) ?

Halting() has already been defined as a total TM, therefore
Halting() returns false when SRFHP, therefore
!Halts(tm, input) == Halting(tm, input) indicates SRFHP

So we are back to my original specification:

Halting(h, tm, input):
Halts(tm, input) && Not(SRFHP(h, tm, input)) && Valid(tm)

NotHalting(h, tm, input):
!Halts(tm, input) && Not(SRFHP(h, tm, input)) && Valid(tm)

SRFHP(tm, input):
!Halting(tm, input) && !NotHalting(tm, input)

The apparent infinite recursion of this specification should be factored
out.
It is way past my bedtime.

[George Greene]

On May 5, 6:55 pm, Peter Olcott <OCR4Screen> wrote:
> The specification is semantic it is NOT a Turing Machine.
> You can't point out any gaps in this specification because there aren't
> any.

Then why should anybody CARE about it?? When you CAN write a TM, GET
BACK TO US.

[Bryan]

Peter Olcott wrote:
> On 5/5/2012 11:18 AM, Joshua Cranmer wrote:> On 5/5/2012 11:12 AM, Peter Olcott wrote:
> >> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
> >>> So I implore you: Give us a clear, concise definition of SRFP.
>
> >> Halting(tm, input) != Halts(tm, input)
>
> > Thank you for making it perfectly clear that SRFHP is undecidable.
>
> Try and show this using a valid counter-example.

Peter, really? At this point you still can't do even that simple
example yourself? How long do you expect everyone to go on spoon-
feeding you?

You, Peter, stated that Halting() is a total TM. It always answers yes
or no, accept or reject. So assume that you are right about that, and
that SRFHP() is Turing-decidable.

I construct TM "PeterIsWrong" to invoke both Halting(input) and a TM
that decides SRFHP(input). Here it is:

PeterIsWrong(input):
x = Halting(input)
if SRFHP(input):
return !x
else:
return x

If Halting() is a total TM, as you, Peter, defined it be, and if
SRFHP() is Turing-decidable, then there exists TM PeterIsWrong() that
decides Halts. There does not exist a TM that decides Halts, and thus
at least one of those assumptions is false.

Peter, the hour is late. When Joshua dismissed your vain notion by
noting that your SRFHP is undecidable, most everyone else writing here
quickly saw the proof. I say that have never personally met anyone
else posting here, to the best of my recollection. I can tell just
from their posts. Theory of computation is not exactly kindergarten
stuff, but the crowd here on c.t grasps that much. Many smart people
do not connect with this material, so they move on to other matters
where they they can make positive contributions.

-Bryan

[Peter Olcott]

I may be incorrect in this point. I have not yet seen categorically
exhaustive proof that I am wrong about this. This degree of proof may
require me to learn more about the Theory of Computation.

Is it your understanding that the Halting Problem has never been
formalized?

[Joshua Cranmer]

On 5/6/2012 7:24 AM, Peter Olcott wrote:
> On 5/6/2012 4:05 AM, Bryan wrote:
>> Peter, the hour is late. When Joshua dismissed your vain notion by
>> noting that your SRFHP is undecidable, most everyone else writing here
>> quickly saw the proof. I say that have never personally met anyone
>
> I may be incorrect in this point. I have not yet seen categorically
> exhaustive proof that I am wrong about this. This degree of proof may
> require me to learn more about the Theory of Computation.

Proof by reduction is one of the single most important proof techniques
in computability theory; it is extremely easy to show that if A can be
reduced to B, and A is undecidable, then B is necessarily undecidable as
well.

> Is it your understanding that the Halting Problem has never been
> formalized?

It has been formalized before. Indeed, I can think of at least four or
five proofs of the Halting problem's undecidability, one of which has
been formally verified using a tool like Coq.

[Peter Olcott]

On 5/5/2012 1:09 PM, Ben Bacarisse wrote:

> Joshua Cranmer<Pidg...@verizon.invalid> writes:
>
>> On 5/5/2012 11:12 AM, Peter Olcott wrote:
>>> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
>>>> So I implore you: Give us a clear, concise definition of SRFP.
>>>>
>>> Halting(tm, input) != Halts(tm, input)
>> Thank you for making it perfectly clear that SRFHP is undecidable.
> I wrote the following before you posted your second reply, so just
> consider this another way to look at it...
>
> If we take Peter at his word (and, frankly, this response suggests we
> probably can't) Halting is defined like this:
>
> Halting(h, tm, input):

> Halts(tm, input)&& Not(SRFHP(h, tm, input))&& Valid(tm)

>
> Now, if my algebra is correct, this latest stab in the dark means that
> for some putative haling decider, h, SRFHP(h, tm, input) must be true if
> the computation (tm, input) halts (assuming a valid tm). That sounds
> screwy.
>
> When the computation (tm, input) does not halt, the proffered equation
> can't be solved (for valid tms). So, if you view his offering as at
> least a partial definition, SRFHP must be true for halting computations
> and must be undefined (looping) for non-halting ones.
>
> This, of course, is a computable function (yay!) but it's not a decider
> and it's got nothing to do with what Peter's been calling SRFHP up until
> today.
>
> As I suspect you know, he won't define SRFHP because even he has no idea
> what it does (except for the specific instance he can cite --
> repeatedly). He may throw a few things at the wall to see if any are
> vague enough to keep the discussion going, but that's it. After months
> of exchanges, all we know is what we knew on day one -- the "invalid
> input" is a single instance of a computation, specific to every putative
> halting decider.
>

M(String H, String input):
if H(input, input) loop
else halt

It would seem that a pair of Deciders could be defined for the above
single concrete example such that:
1) Halting() would return false indicating that true would not
correspond to Halts(tm, input)
2) NotHalting() would return false indicating that true would not
correspond to !Halts(tm, input)

thus !Halting() && !NotHalting() would indicate the semantic meaning of
Invalid Input, which includes but is not limited to SRFHP.

[Peter Olcott]

Try this one:

[Peter Olcott]

On 5/6/2012 8:28 AM, Joshua Cranmer wrote:

What is Coq? Do you have a link to one of these proofs?

[George Greene]

On May 6, 10:09 am, Peter Olcott <OCR4Screen> wrote:
> It would seem that a pair of Deciders could be defined for the above
> single concrete example

IT IS ALWAYS, ALWAYS, ALWAYS "possible" to write "a decider for" ANY
SINGLE concrete example. BOTH of these POSSIBLE deciders HAVE ALREADY
BEEN written!
There is 1 TM that ALWAYS DECIDES EVERYTHING *TRUE*. It just halts
accept/true IMMEDIATELY, WITHOUT EVEN CARING what its input is. THAT
TM DECIDES your single concrete example. There is 1 TM that ALWAYS
DECIDES EVERYTHING *FALSE*. It just reject-halts IMMEDIATELY, WITHOUT
EVEN CARING what its input is. THAT TM DECIDES your single concrete
example. Speaking of trying to "decide" ANY FINITE question is
speaking OUT OF YOUR ASS, DUMBASS.

[George Greene]

NO, this would NOT seem to be the case, at least not in the general
case.
I realize you were trying to talk about the single case, but that is
just meaningless, really.
It is easy to make Halting() return false, since YOU are writing it;
YOU just WRITE it to return false on ALL its inputs, WHETHER THEY
HALT OR NOT.
As for this single case, it is ALWAYS going to be the case for the
whole INFINITY of different H's, that they ALL return a truth-value
that is THE OPPOSITE
of the truth-value of "M halts on input-string H,M". No matter what H
you supply, the invocation M(H,M) will have a different halting
behavior from the one indicated by H(M,M). If H(M,M) returns true,
then M(H,M) will Loop (so H lied). If H(M,M) returns false then
M(H,M) will Halt (so H lied again). If H(M,M) loops and never returns
anything at all, then M(H,M) does NOT halt, so H *should've* returned
FALSE if it wanted to indicate M(H,M)'s halting behavior, BUT AGAIN IT
FAILS.
H's answer IS ALWAYS DIFFERENT from Halts(,)'s , NO MATTER WHAT H
says. But that does NOT make H's answer WRONG or incorrect, since H
was NEVER *TRYING* to be, was never OBLIGATED to be, never accepted
the MISSION of being, Halts(,) ANYWAY.

Analyzing the halting behavior of M if you are NOT H is not that hard;
you just have to be able to analyze the behavior of H first.
But if you are trying to be a halt-decider IN GENERAL then you will
eventually have to analyze YOUR OWN behavior. OOPS.

[Bryan]

Peter Olcott wrote:
> Joshua Cranmer wrote:

> > Peter Olcott wrote:
> >> Is it your understanding that the Halting Problem has never been
> >> formalized?
>
> > It has been formalized before. Indeed, I can think of at least four or
> > five proofs of the Halting problem's undecidability, one of which has
> > been formally verified using a tool like Coq.
>
> What is Coq? Do you have a link to one of these proofs?

GIYF and Joshua did that a couple weeks ago.
http://groups.google.com/group/sci.logic/msg/83b9fe987f7472ef

-Bryan

[Ben Bacarisse]

Peter Olcott <OCR4Screen> writes:

> On 5/5/2012 1:09 PM, Ben Bacarisse wrote:
>> Joshua Cranmer<Pidg...@verizon.invalid> writes:
>>
>>> On 5/5/2012 11:12 AM, Peter Olcott wrote:
>>>> On 5/5/2012 11:06 AM, Joshua Cranmer wrote:
>>>>> So I implore you: Give us a clear, concise definition of SRFP.
>>>>>
>>>> Halting(tm, input) != Halts(tm, input)
>>> Thank you for making it perfectly clear that SRFHP is undecidable.
>> I wrote the following before you posted your second reply, so just
>> consider this another way to look at it...
>>
>> If we take Peter at his word (and, frankly, this response suggests we
>> probably can't) Halting is defined like this:
>>
>> Halting(h, tm, input):
>> Halts(tm, input)&& Not(SRFHP(h, tm, input))&& Valid(tm)
>>
>> Now, if my algebra is correct, this latest stab in the dark means that
>> for some putative haling decider, h, SRFHP(h, tm, input) must be true if
>> the computation (tm, input) halts (assuming a valid tm). That sounds
>> screwy.
>
> Exactly which formal error of reasoning is "sounds screwy" ?

It might help if I explained why my response differed from Joshua's.
You should follow his sub-thread and ignore mine, because the argument
that SRFHP is undecidable is much more succinct. I don't disagree with
anything he's said.

I decided to take a different tack: what does the new definition,
combined with the old one, mean for the function that SRFHP should
compute? That produces a more complex result -- that SRFHP can only be
a partial function (and hence, like the other sub-thread, it shows that
it's not a decider) but also that what it would have to compute is
something that even you would consider "screwy". If you are
unpersuaded, just leave it to one side.

>> When the computation (tm, input) does not halt,
> Do you mean !Halts(tm, input) ?

Yes.

>> the proffered equation
>> can't be solved (for valid tms).
> Do you mean can't be solved for Valid(tm) ?

Yes. Because you've chosen to include the possibility of a string not
being an encoding of a tm, pretty much everything has to qualified with
"for Valid(tm)". This is particularly dangerous since you are using
"InvalidInput" to mean something else elsewhere. Everything would be
simpler if you stipulated an encoding in which all strings were valid
TMs.

> Halting() has already been defined as a total TM, therefore
> Halting() returns false when SRFHP,
> therefore
> !Halts(tm, input) == Halting(tm, input) indicates SRFHP
>
> So we are back to my original specification:
>
> Halting(h, tm, input):
> Halts(tm, input) && Not(SRFHP(h, tm, input)) && Valid(tm)
>
> NotHalting(h, tm, input):
> !Halts(tm, input) && Not(SRFHP(h, tm, input)) && Valid(tm)
>
> SRFHP(tm, input):
> !Halting(tm, input) && !NotHalting(tm, input)
>
> The apparent infinite recursion of this specification should be
> factored out.
> It is way past my bedtime.

Actually that's wrong, because you've now been tripped up by not
considering the Valid(tm) check. (You really should just get rid if
it.) If you take

!Halting(h, tm, input) && !NotHalting(h, tm, input)

(I've put the putative halting decider arguments back again) and
simplify the resulting expression, you get

SRFHP(h, tm, input) || Not(Valid(tm))

Thus SRFHP can't be defined as above. (I posted about this before).

<snip>
--
Ben.

[George Greene]

> > When the computation (tm, input) does not halt,

On May 5, 11:46 pm, Peter Olcott <OCR4Screen> wrote:
> Do you mean !Halts(tm, input) ?

NO, NObody, INCLUDING YOU, means THAT, because
Halts(,) doesn't exist.

You HAVE to say it in English instead. Or in SOME other language
that is NOT THE SAME language as the language in which you are writing
the TMs.
The class of functions that can be constructed WITH that programming
language
does NOT include an element that is a Halts(,) TM -- NO SUCH TM
EXISTS.

[George Greene]

On May 6, 7:04 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> Thus SRFHP can't be defined as above.  (I posted about this before).

You canNOT (well, obviously, you can, but you shouldn't) keep
indulging idiots' abuse of vocabulary.
THERE IS NO SUCH THING AS "the self-rerence form of the halting
problem".
There really are not ANY "forms" of it at all. THE ONLY KIND of
"problem" IN THIS CONTEXT
is a countably infinite family of yes/no questions. The questions
have a constant part and a variable
or parameterized part. If you have an adjective A as shorthand for
the family (for the constant part),
then "the A problem" is "does there exist a TM that accepts all&only
those inputs-that-could-go-in-the-variable-part,
those pegs that could go in the parameter-holes, for which the answer
to the individual instantiated question -- WITH THAT peg in the
parameter-hole -- is true".
That is THE ONLY form OF ALL of THIS ENTIRE CLASS of "problems".
Indulging his belief that there is some other form of something IS
COUNTER-productive.