Re: InvalidInput Decider 2012-05-02

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

Peter Olcott <OCR4Screen> writes:

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

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

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.

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

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

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

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

[Peter Olcott]

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

[Joshua Cranmer]

On 5/6/2012 9:24 AM, Peter Olcott wrote:
> 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.

What you are doing, as I read it, amounts to solving a variant of the
Halting problem which divides the set of <TM, input> pairs not into
"halts" and "does not halt" but rather "halts", "does not halt", and
"dunno." The three-valued input is indeed possible, but note that there
are strong constraints on what gets put in the "dunno" set. In
particular, for most TMs in the "halts" bucket, there exists another TM
that is semantically equivalent that is in the "dunno" set.

[Ralph Hartley]

On 05/04/2012 03:29 PM, Peter Olcott 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?

All the other posters are on target. If you don't tell me what SRFHP is
supposed to *be*, how am I supposed to give a counter example.

Your clearest attempted definition was quickly proven (twice) to be an
uncomputable function, so instead of asking for a precise definition, I
will just try to narrow down the possibilities.

You give one example:

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

(Notation -- I will write M(H) for M with the first input filled in, so
that M(H)(input) = M(H,input), and avoid your tendency to drop the
argument.)

Presumably:
(1) SRFHP(H,M(H),M(H)) = true.

Meaning that (M(H),M(H)) is a "bad" input for H.

Correct?

There are other TMs that would work just as well in the halting proof as
M does. SRFHP won't help much if it doesn't include those cases as well.

So I'm guessing that you also want at least:

(2) if Halts(M'(H,M'(H))) = Halts(M(H,M(H))
then SRFHP(H,M'(H),M'(H)) = true.

Meaning that (M'(H),M'(H)) is also a "bad" input for H.

Correct?

I'm a lot more shaky on when SRFHP is *false*, you don't give *any* such
cases.

All my guesses are either useless

Example:
(3a) SRFHP is never false.

or not computable

Example:
(3b) If (2) does not apply, then SRFHP is false.

Can you at least put a bound on it? By a bound, I mean can you say
something of the form:

(3x) If x, then SRFHP is false.

That may not define SRFHP completely, but it would be a start.

Ralph Hartley

[Antti Valmari]

On 05/04/12 14:51, Peter Olcott wrote in another thread:
> On 5/4/2012 5:35 AM, Antti Valmari wrote:
...
>> 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.

What "mathematical mapping" and "incorrect" in what sense?

I am curious to see if and what you reply to the following. Let Stop
denote the Turing machine that has one state, no transitions, and the
state is an accept state. You have "Valid(tm)" in many of your
descriptions of Turing machines, such as

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

What prevents you from writing

Halting(h, tm, input):
if !Valid(tm) then
Halts(Stop, input) && Not(SRFHP(h, Stop, input))
else

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

? In the input language of the tm parameter of the new version of
Halting, every string represents a valid TM --- even the empty string.

--- Antti Valmari ---

[Antti Valmari]

On 05/07/12 13:19, Peter Olcott wrote:
> 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.

Not just a pair of deciders, but many pairs. Infinitely many. Therefore,
this line of thinking does not yield a reasonable definition for
"Invalid Input". It yields infinitely many different arbitrary
definitions for "Invalid Input". Like I and others have explained.

This holds even if you fix the TM and only let the input vary. This is
because of the notion of the universal Turing machine. (It seems to me
that at some point you suggested fixing the TM.)

--- Antti Valmari ---

[Peter Olcott]

Two TMs that have different outputs for the same input AND are
semantically equivalent?

[Peter Olcott]

On 5/7/2012 11:12 AM, Ralph Hartley wrote:
> On 05/04/2012 03:29 PM, Peter Olcott 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?
>
> All the other posters are on target. If you don't tell me what SRFHP
> is supposed to *be*, how am I supposed to give a counter example.
>
> Your clearest attempted definition was quickly proven (twice) to be an
> uncomputable function, so instead of asking for a precise definition,
> I will just try to narrow down the possibilities.
>
> You give one example:
>> M(String H, String input):
>> if H(input, input) loop
>> else halt
>
> (Notation -- I will write M(H) for M with the first input filled in,
> so that M(H)(input) = M(H,input), and avoid your tendency to drop the
> argument.)
>
> Presumably:
> (1) SRFHP(H,M(H),M(H)) = true.
>
> Meaning that (M(H),M(H)) is a "bad" input for H.
>
> Correct?
>

Yes

> There are other TMs that would work just as well in the halting proof
> as M does. SRFHP won't help much if it doesn't include those cases as
> well.
>
> So I'm guessing that you also want at least:
>
> (2) if Halts(M'(H,M'(H))) = Halts(M(H,M(H))
> then SRFHP(H,M'(H),M'(H)) = true.
>
> Meaning that (M'(H),M'(H)) is also a "bad" input for H.
>
> Correct?

The details of M' are not specified so I can not tell what you mean by M'.

Actually in this case I probably want to start with just M. After
we can agree on this single concrete instance it will be referred
to as M0 and then I will specify concrete instance M1.

The aspect of my intelligence that was measured to be about ten-fold
less frequently occurring than my overall Average M.D. IQ has to do
with my ability to form mappings between the concrete and the abstract.

If we start with one concrete instance and then add another concrete
instance to this, and repeat this process a few times we might come up
with something that is interesting.

>
> I'm a lot more shaky on when SRFHP is *false*, you don't give *any*
> such cases.
>

This is simply the entire set of *all* TMs that simply either halt or fail
to halt, but, don't ever try to muck with the output of the invocation of
any other TM.

void X(void):
return false;

void X2(void):
loop;

[Peter Olcott]

On 5/7/2012 12:01 PM, Antti Valmari wrote:
> On 05/04/12 14:51, Peter Olcott wrote in another thread:
>> On 5/4/2012 5:35 AM, Antti Valmari wrote:
> ...
>>> 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.
> What "mathematical mapping" and "incorrect" in what sense?

If I wrote a "C" function:

int PlusFive(int n)
{
return n + 5;
}

and it was translated into the semantic meaning of:
printf("Hell Oh Whirled!");

it would be an incorrect mathematical mapping from the specification to
the behavior.

Likewise with an empty string being translated into any functionality at
all. If it does anything at all, it is *not* doing exactly and precisely
what it was told to do.

> I am curious to see if and what you reply to the following. Let Stop
> denote the Turing machine that has one state, no transitions, and the
> state is an accept state. You have "Valid(tm)" in many of your
> descriptions of Turing machines, such as
>
>> Halting(h, tm, input):

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

> What prevents you from writing
>
> Halting(h, tm, input):
> if !Valid(tm) then

> Halts(Stop, input)&& Not(SRFHP(h, Stop, input))

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

It looks like you are invoking the purely mathematical (not a TM)
function Halts() so I have no idea what you are saying.

[Peter Olcott]

On 5/7/2012 12:02 PM, Antti Valmari wrote:
> On 05/07/12 13:19, Peter Olcott wrote:
>> 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.
> Not just a pair of deciders, but many pairs. Infinitely many. Therefore,

The function named M is a single instance, so I think
that there would only be a single pair of Halting() and NotHalting().

If we succeed with M, we will proceed to M1...
and generalize somewhere along the line.

[Bryan]

Peter Olcott wrote:
> Joshua Cranmer wrote:

> > What you are doing, as I read it, amounts to solving a variant of the
> > Halting problem which divides the set of <TM, input> pairs not into
> > "halts" and "does not halt" but rather "halts", "does not halt", and
> > "dunno." The three-valued input is indeed possible, but note that
> > there are strong constraints on what gets put in the "dunno" set.
> > In particular, for most TMs in the "halts" bucket, there exists
> > another TM that is semantically equivalent that is in the "dunno" set.
>
> Two TMs that have different outputs for the same input AND are
> semantically equivalent?

No. Notations vary, but two TM's are semantically equivalent if they
halt for the same inputs, hang for the same inputs, and for all inputs
for which they halt they, return the same result. If we define halting
states to be accept/reject states, that's part of the result.

Two semantically equivalent TM's may arrive at the final result by
radically different paths. For all inputs it has to be the same, but
the path to get there is irrelevant to semantically equivalence.

Peter, you seem to have the idea of working around certain proofs of
the halting theorem by constructing TM's that detect when their input
data contains their own specification. One reason such attempts are
doomed is that for any TM the set of semantically equivalent TM's is
undecidable. You can probably find that result in at least one of your
theory textbooks, and it's an obvious implication of Rice's theorem.

-Bryan

[Ralph Hartley]

> Actually in this case I probably want to start with just M. After
> we can agree on this single concrete instance it will be referred
> to as M0 and then I will specify concrete instance M1.

M is not the only TM for which H fails. If you wish to claim that H
decides all inputs without SRFHP, you have to include them *all*.

There are infinitely many. You want to specify them one at a time? I
have been patient, but I am not *that* patient.

>> I'm a lot more shaky on when SRFHP is *false*, you don't give *any*
>> such cases.
>
> This is simply the entire set of *all* TMs that simply either halt or fail
> to halt

All TMs either halt or fail to halt.

This seems to be a sense (or two senses?) of the word "simply" with
which I am unfamiliar.

> but, don't ever try to muck with the output of the invocation of
> any other TM.

You are attributing intentions to TMs again. All TMs just follow their
state transition table, they never "try to" do anything.

Ralph Hartley

[Joshua Cranmer]

What I mean is that given a TM M1 that a classifier puts in the halt
bucket, it is generally possible to construct another TM M2 such that
M1(x) = M2(x) for all x and the classifier sticks M2 into the "dunno"
bucket.

[Peter Olcott]

On 5/8/2012 6:27 AM, Bryan wrote:
> Peter Olcott wrote:
>> Joshua Cranmer wrote:
>>> What you are doing, as I read it, amounts to solving a variant of the
>>> Halting problem which divides the set of<TM, input> pairs not into
>>> "halts" and "does not halt" but rather "halts", "does not halt", and
>>> "dunno." The three-valued input is indeed possible, but note that
>>> there are strong constraints on what gets put in the "dunno" set.
>>> In particular, for most TMs in the "halts" bucket, there exists
>>> another TM that is semantically equivalent that is in the "dunno" set.
>> Two TMs that have different outputs for the same input AND are
>> semantically equivalent?
> No. Notations vary, but two TM's are semantically equivalent if they
> halt for the same inputs, hang for the same inputs, and for all inputs
> for which they halt they, return the same result. If we define halting
> states to be accept/reject states, that's part of the result.
>
> Two semantically equivalent TM's may arrive at the final result by
> radically different paths. For all inputs it has to be the same, but
> the path to get there is irrelevant to semantically equivalence.
>
> Peter, you seem to have the idea of working around certain proofs of
> the halting theorem by constructing TM's that detect when their input
> data contains their own specification. One reason such attempts are

I do not think that is my approach.

My concept is to detect whenever the input data has no correct return
value from the set of {true, false} that the invocation of a potential
halt decider could provide indicating whether or not the input data
represents a TM that would halt on its input.

Since the representational model that I have selected does not allow any
assumptions to be made (only what is explicitly specified may be
represented) the input of the empty string is not considered to be a
valid TM.

[Peter Olcott]

OK then erase the phrase "try to". You know what I meant, you are being
too picky.

[Peter Olcott]

On 5/8/2012 10:54 AM, Joshua Cranmer wrote:
> On 5/7/2012 6:35 PM, Peter Olcott wrote:
>> On 5/7/2012 8:30 AM, Joshua Cranmer wrote:
>>> In particular, for most TMs in the "halts" bucket, there exists
>>> another TM that is semantically equivalent that is in the "dunno" set.
>>>
>> Two TMs that have different outputs for the same input AND are
>> semantically equivalent?
>
> What I mean is that given a TM M1 that a classifier puts in the halt
> bucket, it is generally possible to construct another TM M2 such that
> M1(x) = M2(x) for all x and the classifier sticks M2 into the "dunno"
> bucket.
>

Let me make a slight correction, I had envisioned the "dunno" bucket to
be the can't say bucket. There are cases such as M, where H knows, but
can't say.

[Peter Olcott]

On 5/8/2012 7:24 AM, Ralph Hartley wrote:
>

>> Actually in this case I probably want to start with just M. After
>> we can agree on this single concrete instance it will be referred
>> to as M0 and then I will specify concrete instance M1.
>
> M is not the only TM for which H fails. If you wish to claim that H
> decides all inputs without SRFHP, you have to include them *all*.
>
> There are infinitely many. You want to specify them one at a time? I
> have been patient, but I am not *that* patient.
>

I have had such a difficult time getting anyone to agree with anything
that I am breaking down my presentation into smaller increments to avoid
anyone leaping to any conclusions.

Can you see that for the single instance of M, that both Halting() and
NotHalting() could halt in their respective reject states?

[Joshua Cranmer]

It doesn't matter what you call the bucket as long as they have the same
definition. The end result is still the same.

[Peter Olcott]

I am still not yet convinced that a TM could not know within an internal
state, the halt value of an input TM. Thus "dunno" and "can't say" would
diverge.

[Ralph Hartley]

> OK then erase the phrase "try to". You know what I meant

Do *you* know what you mean?

"muck with the output of the invocation of any other TM" still does not
describe a property of TMs.

You can *design* a TM by saying "simulate an invocation of another TM
and muck with its output", but a given TM just reads and writes its tape
according to its state table.

"Does this TM muck with the output of the invocation of any other TM?"
is not a question with an objective answer, independent of where the TM
came from.

It isn't defined even as a pure function, to say nothing of being
computable.

Ralph Hartley

[Antti Valmari]

On 05/08/12 02:55, Peter Olcott wrote:
> If I wrote a "C" function:
>
> int PlusFive(int n)
> {
> return n + 5;
> }
>
> and it was translated into the semantic meaning of:
> printf("Hell Oh Whirled!");
>
> it would be an incorrect mathematical mapping from the specification to
> the behavior.

Incorrect according to the rules of C, but we were not discussing C and
are thus not restricted by the rules of C.

> Likewise with an empty string being translated into any functionality at
> all. If it does anything at all, it is *not* doing exactly and precisely
> what it was told to do.

If, according to the rules of the language in question, the meaning of
the empty string is "do xxx", then the only way to faithfully process
the empty string is to do xxx.

Use of the empty string to denote something else than "nothing" or "do
nothing" is common in programming and computer science. For instance,
the following passage is from the description of the set command of the
csh shell in the Unix world:

With no arguments, set displays the values of all shell
variables. Multiword values are displayed as a parenthesized
list. With the var argument alone, set assigns an empty
(null) value to the variable var. With arguments of the
form var = value set assigns value to var, where value is
one of: ...

Thus the meaning of "set <empty string>" is not "do nothing" but
"display the values of all shell variables".

Similar thing occurs in communication between humans, without computers
involved. Of all possible sheets or flags or posters, the one that is
totally white (that is, blank) carries no information, right? If in a
war situation the opponent raises a white flag, does that have any
meaning in your opinion?

In the light of the evidence, the idea that the empty string could not
denote some Turing machine is crazy. You are apparently unable to
communicate to me why it is not crazy, and I am apparently unable to
communicate to you why it is. As a result, I do not any more believe in
the possibility of constructive discussion between you and me on your
non-standard ideas.

--- Antti Valmari ---

[Ralph Hartley]

On 05/08/2012 07:01 PM, Peter Olcott wrote:
> On 5/8/2012 7:24 AM, Ralph Hartley wrote:
>>
>>> Actually in this case I probably want to start with just M. After
>>> we can agree on this single concrete instance it will be referred
>>> to as M0 and then I will specify concrete instance M1.
>>
>> M is not the only TM for which H fails. If you wish to claim that H
>> decides all inputs without SRFHP, you have to include them *all*.
>>
>> There are infinitely many. You want to specify them one at a time? I
>> have been patient, but I am not *that* patient.
>
> I have had such a difficult time getting anyone to agree with anything
> that I am breaking down my presentation into smaller increments to avoid
> anyone leaping to any conclusions.

I have been *very* careful to make no more than one point/message, since
you always ignore all but one, and usually not the important one.

> Can you see that for the single instance of M, that both Halting() and
> NotHalting() could halt in their respective reject states?

I will go further. I will grant that for any *finite* set of Ms.

All finite sets are decidable.

Ralph Hartley

[Ralph Hartley]

On 05/08/2012 08:53 PM, Peter Olcott wrote:
>> On 5/8/2012 5:44 PM, Peter Olcott wrote:
>>> Let me make a slight correction, I had envisioned the "dunno" bucket to
>>> be the can't say bucket. There are cases such as M, where H knows, but
>>> can't say.

...

> I am still not yet convinced that a TM could not know within an internal
> state, the halt value of an input TM. Thus "dunno" and "can't say" would
> diverge.

Aaarrg! (Bangs head on desk.)

You aren't convinced because you ignored the proof, even though it is a
one liner. Let me give it to you again:

Given a TM that always "knows" the correct answer, one can construct a
TM that always returns the correct answer. No TM always returns the
correct answer. Therefore no TM always "knows" the correct answer.

The proof works for any definition of "knows" that is more than
metaphysical. By which I mean excluding TMs in which the answer is
encoded so obscurely that it is impossible to extract.

Ralph Hartley

[Joshua Cranmer]

Let me step back and say first off: "IT DOESN'T MATTER."

If you define a three-bucket system, such that a TM never incorrectly
classifies the items in the "halts" and "does not halt" buckets and
stuffs the rest of the space into a third bucket, the contrapositive of
Rice's Theorem clearly implies [1] that there exists machines with the
same language one of which is in the third bucket and one of which is not.

If you think about how to actually implement one of these things, you'd
be able to go further and assert that it happens for most machines in
the "halts" bucket.

This isn't rocket science, it's elementary logic being applied to
standard definitions.

[1] Assuming that not everyone goes into the third bucket.

[Bryan]

Peter Olcott wrote:
> Bryan wrote:
> > Peter Olcott wrote:
> >> Joshua Cranmer wrote:
> >>> What you are doing, as I read it, amounts to solving a variant of the
> >>> Halting problem which divides the set of<TM, input>  pairs not into
> >>> "halts" and "does not halt" but rather "halts", "does not halt", and
> >>> "dunno." The three-valued input is indeed possible, but note that
> >>> there are strong constraints on what gets put in the "dunno" set.
> >>> In particular, for most TMs in the "halts" bucket, there exists
> >>> another TM that is semantically equivalent that is in the "dunno" set.
> >> Two TMs that have different outputs for the same input AND are
> >> semantically equivalent?
> > No. Notations vary, but two TM's are semantically equivalent if they
> > halt for the same inputs, hang for the same inputs, and for all inputs
> > for which they halt they, return the same result. If we define halting
> > states to be accept/reject states, that's part of the result.
>
> > Two semantically equivalent TM's may arrive at the final result by
> > radically different paths. For all inputs it has to be the same, but
> > the path to get there is irrelevant to semantically equivalence.
>
> > Peter, you seem to have the idea of working around certain proofs of
> > the halting theorem by constructing TM's that detect when their input
> > data contains their own specification. One reason such attempts are
>
> I do not think that is my approach.

You were writing about somebody else's approach?

> My concept is to detect whenever the input data has no correct return
> value from the set of {true, false} that the invocation of a potential
> halt decider could provide indicating whether or not the input data
> represents a TM that would halt on its input.

That nonsense again? Surely at least one of your theory books defines
halting instances as a language, a set of strings over a given
alphabet. A string over the alphabet is either in the language or not
in the language.

> Since the representational model that I have selected does not allow any
> assumptions to be made (only what is explicitly specified may be
> represented) the input of the empty string is not considered to be a
> valid TM.

You have four theory books and yet you can't even get past
representation? Given a straightforward syntax to "explicitly"
represent TM's, we can construct Turing-computable one-to-one
functions from Sigma* to all TM representations. Now you never again
have to bother with the trivia of syntactically incorrect strings that
fail to represent TM's.

-Bryan

[Peter Olcott]

It is theoretically possible to create a TM that completely understands
the sum total of all knowledge, and also has an artificial personality.
Because of this extrapolation to the logical extreme, the terms that I
used seem apt.

[Peter Olcott]

On 5/9/2012 7:31 AM, Antti Valmari wrote:
> On 05/08/12 02:55, Peter Olcott wrote:
>> If I wrote a "C" function:
>>
>> int PlusFive(int n)
>> {
>> return n + 5;
>> }
>>
>> and it was translated into the semantic meaning of:
>> printf("Hell Oh Whirled!");
>>
>> it would be an incorrect mathematical mapping from the specification to
>> the behavior.
> Incorrect according to the rules of C, but we were not discussing C and
> are thus not restricted by the rules of C.
>
>
>> Likewise with an empty string being translated into any functionality at
>> all. If it does anything at all, it is *not* doing exactly and precisely
>> what it was told to do.
> If, according to the rules of the language in question, the meaning of
> the empty string is "do xxx", then the only way to faithfully process
> the empty string is to do xxx.

You are not being literal enough.

> Use of the empty string to denote something else than "nothing" or "do
> nothing" is common in programming and computer science. For instance,
> the following passage is from the description of the set command of the
> csh shell in the Unix world:
>
> With no arguments, set displays the values of all shell
> variables. Multiword values are displayed as a parenthesized
> list. With the var argument alone, set assigns an empty
> (null) value to the variable var. With arguments of the
> form var = value set assigns value to var, where value is
> one of: ...
>
> Thus the meaning of "set<empty string>" is not "do nothing" but
> "display the values of all shell variables".

You are again not being literal enough, that is *not* the empty string
that is a command with no specified parameters.

If on the UNIX shall command line you literal specify the empty string
that would be just you sitting there doing nothing and typing nothing.

[Peter Olcott]

I thought that Rice's showed that this was not true.

[Peter Olcott]

That does not seem to be a proof to me, that seems to be an assertion.

(1) Given a TM that always "knows" the correct answer,
(2) one can construct a TM that always returns the correct answer.
(3) No TM always returns the correct answer.
(4) Therefore no TM always "knows" the correct answer.

I do not think that (2) logically follows from (1).

[Joshua Cranmer]

There are an infinite number of distinct TMs that have the same
language. Therefore, no finite language (save the empty one) can decide
a property of a language, so Rice's theorem does not apply.

Remember, Rice's theorem discusses languages, not Turing machines: if
two Turing machines decide the same language, but one is in a language
and the other is not, then Rice's theorem does not apply.

[Peter Olcott]

// Only when true is impossible for both
// !Halting() && !NotHalting()
InvalidInput:
!Halting() && !NotHalting()

This certainly works for the single instance of the previously specified M.

I can not imagine another specific concrete instance that it would not
work for within the context of the self-reference form of the Halting
Problem.