Re: Why do theory of computation problems require pure functions? [ PSR error]

[olcott]

On 9/19/2021 11:11 AM, André G. Isaak wrote:
> On 2021-09-19 09:46, olcott wrote:
>> On 9/19/2021 10:40 AM, André G. Isaak wrote:
>>> On 2021-09-19 08:34, olcott wrote:
>>>> On 9/18/2021 11:19 PM, André G. Isaak wrote:
>>>>> On 2021-09-18 22:10, André G. Isaak wrote:
>>>>>
>>>>>> And note that Rice is talking about properties of Turing Machines
>>>>>> (or, more properly, of the language accepted by a TM), not
>>>>>> computations.
>>>>>
>>>>> I realized immediately after hitting 'send' that the above will no
>>>>> doubt confuse you since people have been telling you that Turing
>>>>> Machines can only express computations whereas C/x86 aren't thus
>>>>> constrained.
>>>>>
>>>>> A computation is a Turing Machine description PLUS an input string.
>>>>>
>>>>> Rice's theorem is concerned with the Turing Machine's themselves.
>>>>>
>>>>> The Linz proof shows that you cannot construct a halting decider,
>>>>> i.e. a decider which correctly determines for any given TM + input
>>>>> string pair, whether that pair represents a halting computation.
>>>>>
>>>>> Rice's theorem, on the other hand, would rule out the construction
>>>>> of something like a Decider Decider, i.e. a TM which takes as its
>>>>> input a TM description and determines whether that TM qualifies as
>>>>> a decider, i.e. is guaranteed to halt on *any* possible input.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> Here is where I referred to my code defining a
>>>> a decidability decider nine days before you did:
>>>
>>> Where did I define or even mention a 'decidability decider'? Above I
>>> discussed (but did not define) a DECIDER decider, i.e. a TM which
>>> determines whether another TM qualifies as a decider.
>>>
>>>> On 9/9/2021 10:25 AM, olcott wrote:
>>>>  > It is the case that H(P,P)==0 is correct
>>>>  > It is the case that H1((P,P)==1 is correct
>>>>  > It is the case the this is inconsistent.
>>>>  > It is the case that this inconsistency
>>>>
>>>>  > defines a decidability decider that correctly
>>>>  > defines a decidability decider that correctly
>>>>  > defines a decidability decider that correctly
>>>>
>>>>  > rejects P on the basis that P has the
>>>>  > pathological self-reference(Olcott 2004) error.
>>>
>>> So what exactly is it that the above is deciding? And how does this
>>> relate to Rice? If you want to claim this is somehow related to rice,
>>> you need to identify some semantic property that you claim to be able
>>> to decide.
>>>
>>> André
>>>
>>
>> It is deciding that either H/P or H1/P form the pathological
>> self-reference error(Olcott 2004). As I said in 2004 this is the same
>> error as the Liar Paradox. This means that either H/P or H1/P are not
>> correctly decidable.
>
> The post in which I mentioned a 'decider decider' which you somehow
> misread as 'decidability decider' was intended to clarify a single
> sentence from an earlier post which you entirely ignored. Why don't you
> go back and actually read that earlier post and address the points made
> therein.
>
> Your ill-defined notion of a 'pathological self-reference error' doesn't
> appear to be a property of a Turing Machine, which is what Rice's
> theorem is concerned with. To the extent that it is a property at all,
> it appears to be a property of specific computations, so this has
> absolutely no relevance to Rice.
>
> André
>

It is the property of H(P,P).

u32 PSR_Olcott_2004(u32 P)
{
return H1(P,P) != H(P,P);
}

Decides that H(P,P) cannot correctly decide the halt status of its
input, thus a semantic property of H relative to P.

The Liar Paradox works this same way.
"This sentence is not true."
When it refers to itself it has the pathological self-reference
error(Olcott 2004).

This is the same as H(P,P) where the input to H refers to H.

When we transform the Liar Paradox so that it does not refer to itself

This sentence is not true: "2 + 3 = 7" then the pathological
self-reference error(Olcott 2004) is eliminated.

The same thing occurs with H1(P,P).


--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein