Why do theory of computation problems require pure functions?

[olcott]

Why do theory of computation problems require pure functions?

I am trying to write C code that would be acceptable to computer
scientists in the field of the theory of computation.

In computer programming, a pure function is a function that has the
following properties:

(1) The function return values are identical for identical arguments (no
variation with local static variables, non-local variables, mutable
reference arguments or input streams).

(2) The function application has no side effects (no mutation of local
static variables, non-local variables, mutable reference arguments or
input/output streams).

https://en.wikipedia.org/wiki/Pure_function#Compiler_optimizations

--
Copyright 2021 Pete Olcott

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

[olcott]

On 9/17/2021 11:50 PM, André G. Isaak wrote:

> On 2021-09-17 20:40, olcott wrote:
>> Why do theory of computation problems require pure functions?
>

> Because the theory of computation isn't about C or x86. It isn't about
> computer programs at all, nor about modern computers. Just because
> 'computation' and 'computer' share the same root doesn't mean they deal
> with the same set of phenomena. Remember that the theory of computation
> developed before there even were digital computers or programming
> languages.
>
> Computational theory is concerned with describing *mathematical*
> functions, and all mathematical functions are pure functions. A
> computation is a method for determining the value of the mathematical
> function f(x) for a given x. A computable function is one for which it
> is possible to construct a TM which, given an input string representing
> x, will determine the value of f(x).
>
> You can write computer programs which perform computations, but the
> majority of computer programs don't.
>
> If you really want to learn about the theory of computation, I'd suggest
> that you forget about C or x86 assembly or any sort of computer language
> altogether and focus on Turing Machines.
>
> And don't try to mentally translate anything you read about Turing
> Machines into computer languages. Don't think about loop counters, or
> calls, or machine addresses, because all of these things pertain to
> computers and computer programming rather than computations and they
> will get in the way of you actually understanding either turing machines
> or the theory of computation more generally.
>
> André
>

I only need to know this for one reason.

When my halt decider is examining the behavior of its input and the
input calls this halt decider in infinite recursion it cannot keep track
of the behavior of this input without having a single pseudo static
variable that is directly embedded in its machine code.

This pseudo static variable stores the ongoing execution trace. When the
variable is an ordinary local variable it loses all of its data between
each recursive simulation.

It still seems to be a pure function of its input in that

(1) The function return values are identical for identical arguments

[olcott]

On 9/18/2021 10:44 AM, Richard Damon wrote:
> On 9/18/21 11:37 AM, olcott wrote:
>> On 9/18/2021 10:25 AM, Richard Damon wrote:
>>> On 9/18/21 11:19 AM, olcott wrote:
>>>> On 9/18/2021 10:13 AM, Richard Damon wrote:
>>>>> On 9/18/21 10:49 AM, olcott wrote:
>>>>>> On 9/18/2021 9:43 AM, Richard Damon wrote:

>>>>>>> I think the key issue is that if you want to talk about the plain
>>>>>>> behavior of C / x86 code, then you need to talk about the ACTUAL
>>>>>>> behavior of that code, which means that the call to H within the
>>>>>>> simulated machine needs to be seen as a call to H, and NOT some
>>>>>>> logical
>>>>>>> transformation.
>>>>>>>
>>>>>>> If you want to do the transformation, your need to actually PROVE
>>>>>>> that
>>>>>>> this transform is legitimate under the conditions you want to make
>>>>>>> it,
>>>>>>> and that needs a very FORMAL argument based on accepted truths and
>>>>>>> principles. Your 'argument' based on H not affecting P until after it
>>>>>>> makes its decision so it can ignore its effect, is one of those
>>>>>>> arguments that just seems 'obvious' but you haven't actually
>>>>>>> proved it.
>>>>>>> You don't seem to uhderstand that nature of how to prove something
>>>>>>> like
>>>>>>> this.
>>>>>>>
>>>>>>> 'Obvious' things can be wrong, like it seems obvious that the
>>>>>>> order you
>>>>>>> add up a series shouldn't affect the result, even if the number of
>>>>>>> terms
>>>>>>> in infinite, but there are simple proofs to show that for SOME
>>>>>>> infinite
>>>>>>> sums, the order you take the terms can make a difference, dispite it
>>>>>>> seeming contrary to the nature of addition (infinities break a lot of
>>>>>>> common sense).
>>>>>>>
>>>>>>>
>>>>>>> A key point about your 'static' variable problem.
>>>>>>
>>>>>> There is only a single question here, not the myriad of questions that
>>>>>> you refer to.
>>>>>>
>>>>>> Does my use of a single static variable that holds the ongoing
>>>>>> execution
>>>>>> trace by itself necessarily completely disqualify my system from
>>>>>> applying to the halting problem or not?
>>>>>>
>>>>>> a) Yes
>>>>>> b) No
>>>>>
>>>>> Error of the Complex Question, just like the question of "Have you
>>>>> stopped lying about your Halt Decider?".
>>>>>
>>>>> It isn't the existence of a static variable itself that might
>>>>> disqualify
>>>>> your system for applying to the halting problem,
>>>>
>>>> André disagrees so one of you must be wrong.
>>>
>>> Then take his answer and go away as you admit defeat.
>>>
>>
>> That is not how categorically exhaustive reasoning works. Categorically
>> exhaustive reasoning eliminates the possibility of the error of
>> omission. It results in limited subject domain omniscience.
>>
>> It only stops when
>> (1) A solution is found.
>> (2) No solution exist within omniscience.
>
> But your question, as I explained, was not categorically exhaustive.
>

Polar (yes/no) questions only have {yes, no} answers.
{yes,no} completely exhausts the entire category of answers to polar
(yes/no) questions.

> Have you stopped lying about your Halt Decider?

To the best of my knowledge I have only actually lied once in the last
ten years. I lied to a close friend about a very hurtful truth to
protect them from this very hurtful truth.

I do the best that I can to always tell the truth for two reasons:
(1) I have a very deep passion for mathematically formalizing the notion
of analytical truth and this is the sole reason why I pursue:
(a) The Halting Problem
(b) Gödel's 1931 incompleteness theorem
(c) The Tarski Undefinability theorem
(d) The Liar Paradox

(2) I honestly believe that people intentionally spreading dangerous
lies such as 2020 election fraud and covid-19 disinformation may be
eternally incinerated:

Revelation 21:8 KJV ...all liars, shall have their part in the lake
which burneth with fire and brimstone: which is the second death.

If we take that verse literally then to err on the safe side one should
refrain from all lies great and small.


>>>
>>>>
>>>>>   but does the existence
>>>>> of that variable, and the way that your program uses it mean that H is
>>>>> not an actual Computation. The existence of the variable opens the door
>>>>> to it being disqualified, but the actual disqualification needs more
>>>>> information.
>>>>>
>>>>> If EVERY call to H(P,I) for a given P and I returns the exact same
>>>>> answer every time, then H is still a computation.
>>>>>
>>>>> The key point here is that When H decides on the call H(P,P) and in
>>>>> that
>>>>> simulation of P(P) there is a call to H(P,P) then the 'correct' answer
>>>>> for H needs to take into account that this simulated WILL do exactly
>>>>> the
>>>>> same thing as the H that is doing the simulation, so if the
>>>>> simulating H
>>>>> is going to answer Non-Halting, the behavior of the simulated machine
>>>>> will be based on that simulated H also returning that same answer. Yes,
>>>>> H is not going to have simulated to that point of the simulated
>>>>> machines
>>>>> execution, so the simulating H will not be able to see that result, but
>>>>> that IS the behavior of the machine that it is simulating, and thus
>>>>> affect what is the 'Right' answer for H to give.
>>>>>
>>>>>>
>>>>>>> If H really WAS a real
>>>>>>> simulator, then there is no issue with the static variable as only
>>>>>>> one
>>>>>>> copy of H is actually execution, all the other copies are just
>>>>>>> simulation, so the one variable holding the execution trace hold the
>>>>>>> execution trace of the simulation that it is doing, and there is no
>>>>>>> issue.
>>>>>>>
>>>>>>> The only way that the issue you describe becomes a real issue is if H
>>>>>>> doesn't ACTUALLY simulate/debug step through copies of itself, but
>>>>>>> applies some sort of 'transform' to the execution, and you need to
>>>>>>> have
>>>>>>> some very good proof that this transform is actually valid, and that
>>>>>>> the
>>>>>>> resulting H, which passes data to embedded copies of itself, and thus
>>>>>>> knows of stuff of its environment beyond what it is supposed to
>>>>>>> know is
>>>>>>> actually the equivalent of the decider that doesn't do any of that
>>>>>>> 'illegal' operations. My guess is that your H is actually NOT the
>>>>>>> equivalent of such an actual computation and does actually behave
>>>>>>> differently depending on execution environment, and thus fails to
>>>>>>> meet
>>>>>>> the basic requirements.
>>>>>>>
>>>>>>> Remember, if the H inside H^ doesn't behave exactly identical to
>>>>>>> the H
>>>>>>> that is deciding on that H^, then you aren't working on the right
>>>>>>> definitions of the system.
>>>>>>>
>>>>>>> This seems to be one of your fundamental tripping point, and is
>>>>>>> one of
>>>>>>> the issues with doing proofs like this in non-Turing Machine
>>>>>>> environment
>>>>>>> (like C/x86 or even RASP) that 'code fragments' can be
>>>>>>> non-computations
>>>>>>> and thus not the equivalent of a Turing Machine.

[olcott]

On 9/18/2021 5:08 PM, André G. Isaak wrote:
> On 2021-09-18 14:55, olcott wrote:
>> On 9/18/2021 3:45 PM, Richard Damon wrote:
>>> On 9/18/21 4:17 PM, olcott wrote:
>>>> On 9/18/2021 2:57 PM, Richard Damon wrote:
>>>>> On 9/18/21 3:39 PM, olcott wrote:
>>>>>> On 9/18/2021 2:24 PM, Richard Damon wrote:
>>>>>>> On 9/18/21 1:08 PM, olcott wrote:
>>>>>>>> On 9/18/2021 11:52 AM, André G. Isaak wrote:
>>>>>>>>> On 2021-09-18 10:39, olcott wrote:
>>>>>>>>>> On 9/18/2021 11:10 AM, André G. Isaak wrote:
>>>>>>>>>>> On 2021-09-18 09:17, olcott wrote:
>>>>>>>>>>>> On 9/18/2021 10:04 AM, André G. Isaak wrote:
>>>>>>>>>>>>> On 2021-09-18 07:57, olcott wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> I either must stick with C/x86 code or write a RASP
>>>>>>>>>>>>>> machine, the
>>>>>>>>>>>>>> only way that my key insights can possible be fully
>>>>>>>>>>>>>> understood is
>>>>>>>>>>>>>> to have every single detail as fully operational code such
>>>>>>>>>>>>>> that
>>>>>>>>>>>>>> we can simply see what it does and thus not merely imagine
>>>>>>>>>>>>>> what
>>>>>>>>>>>>>> it would do.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Why do you insist on continuously repeating this rather
>>>>>>>>>>>>> ridiculous
>>>>>>>>>>>>> claim?
>>>>>>>>>>>>>
>>>>>>>>>>>>> When working with Turing Machines one doesn't need to 'merely
>>>>>>>>>>>>> imagine what it would do.' One can see *exactly* what it does.
>>>>>>>>>>>>>
>>>>>>>>>>>>> André
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> When H is defined as a simulating halt decider then H correctly
>>>>>>>>>>>> decides the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩.
>>>>>>>>>>>
>>>>>>>>>>> And this statement relates to my post how exactly?
>>>>>>>>>>>
>>>>>>>>>>> André
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> How can [One can see *exactly* what it does] show that my
>>>>>>>>>> claim that
>>>>>>>>>> simulating halt decider H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ does not correctly
>>>>>>>>>> decide the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩ ?
>>>>>>>>>
>>>>>>>>> I made no claims whatsoever in my post about your H.
>>>>>>>>
>>>>>>>> This is exactly what I mean by dishonest dodge AKA the strawman
>>>>>>>> error.
>>>>>>>>
>>>>>>>> When we examine the Peter Linz H applied to ⟨Ĥ⟩ ⟨Ĥ⟩
>>>>>>>>
>>>>>>>> there is nothing in the peter Linz text where
>>>>>>>> [One can see *exactly* what it does]
>>>>>>>>
>>>>>>>> when we assume that the Peter Linz H/Ĥ are based on simulating halt
>>>>>>>> deciders.
>>>>>>>
>>>>>>> In the Linz text, we are not given the detail of what the
>>>>>>> machines do
>>>>>>> inside for their processing, but we know EXACTLY how they behave
>>>>>>> at an
>>>>>>> input/output level.
>>>>>>>
>>>>>>> H is given a defined input, a properly encoded version of H^ (<H^>)
>>>>>>>
>>>>>>> and is defined to end, based on whatever algorithm is inside H to
>>>>>>> end at
>>>>>>> either H.qy or H.qn.
>>>>>>>
>>>>>>> He then defines a machine H^ that is based on a nearly exact copy
>>>>>>> of H,
>>>>>>> with just a minor change in the qy state to make it non-terminal but
>>>>>>> loop, and the add a duplication of the input, so H^ can take as an
>>>>>>> input
>>>>>>> <H^> and then get to the copy of the code of H with <H^> <H^> on the
>>>>>>> tape, which is by definition the encoding of the machine H^(<H^>).
>>>>>>>
>>>>>>> Since it is identical code with identical input, but the property of
>>>>>>> being a Computation, if H(<H^>.<H^>) will end at H.qn, then H^
>>>>>>> will end
>>>>>>> at H^.qn (and then halt) and if H ends at H.qy then H^ will get to
>>>>>>> H^.qy
>>>>>>> (and then loop forever).
>>>>>>>
>>>>>>> Yes, Linz doesn't describe how H is designed to get from H.q0 to
>>>>>>> H.qn or
>>>>>>> H.qy, and that is intentional, as that is specified totally by the
>>>>>>> design of H, and since NOTHING has been assumed about it, no
>>>>>>> possible H
>>>>>>> has been excluded from the reasoning.
>>>>>>>
>>>>>>> Thus, even your simulating halt decider case fits in his model.
>>>>>>>
>>>>>>> Once we know what the provided H will do when given this input,
>>>>>>> we can
>>>>>>> see what the machine that this input represents, and if H said it
>>>>>>> would
>>>>>>> halt, it loops, and if H says it won't halt, it Halts, thus any
>>>>>>> answer H
>>>>>>> gives will be wrong.
>>>>>>>
>>>>>>> The only other posibilities is that H never gets to either H.qn or
>>>>>>> H.qy,
>>>>>>> in which case it has also failed to give the right answer.
>>>>>>>
>>>>>>
>>>>>> That is factually incorrect.
>>>>>> H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly transitions to H.qy.
>>>>>
>>>>> When did you ever claim that H (not H1) ever said that H^(H^) was
>>>>> halting.
>>>>>
>>>>> You can't use H1, as H^ is built on H, if you want to use H1, you need
>>>>> to build the H1^ that calls it to test.
>>>>>
>>>>> Maybe you still don't know what that line means.
>>>>>
>>>>>>
>>>>>> The Linz text does cannot possibly get into sufficient detail to show
>>>>>> how this is not true simply because it is true.
>>>>>>
>>>>>
>>>>> Since your described algorithm for H says that H will declare this
>>>>> input
>>>>> to be non-halting, you are lying to say that this H goes to the
>>>>> terminal
>>>>> state qy.
>>>>>
>>>>> The actual behavior of machine H is determined by the algorithm
>>>>> embedded
>>>>> in it. That algorithm says that <H^> <H^> represents a non-halting
>>>>> computation, therefore H will go to H.qn.
>>>>>
>>>>> Linz says that the H that gives the RIGHT answer for an input that is
>>>>> Halting will go to H.qy, but your H doesn't go there because it is not
>>>>> right.
>>>>>
>>>>> 'Give the right answer' is NOT a valid algorithm for a Turing Machine.
>>>>>
>>>>
>>>> When I refer to H1/H I am referring to my C/x86 code.
>>>> When I refer to H/Ĥ I am referring to the Peter Linz templates.
>>>> You can't seem to keep this straight.
>>>>
>>>>
>>>
>>>
>>> Which means you have something MAJORLY wrong with your argument.
>>>
>>> H1 and H in you C/x86 code are two copies of your decider
>>>
>>> Linz H is the Correct Halting decider that is what you claim is
>>> equivalent of you H
>>>
>>
>> Not any more. Ever since I created H1 that does not have pathological
>> self-reference (two weeks ago?) retaining H that does have
>> pathological self-reference, my H(P,P) is equivalent to the Linz Ĥ.qx
>> ⟨Ĥ⟩.
>>
>> My H1(P,P) is equivalent to the Linz H ⟨Ĥ⟩ ⟨Ĥ⟩.
>> Previosly I had no idea how two different halt deciders would
>> coordinate between themselves so I did not discuss the Linz H ⟨Ĥ⟩ ⟨Ĥ⟩.
> There's something horrendously confused about this.
>
> To the extent that I can actually follow your claims given that you keep
> changing the names of things, here is my current understanding of what
> you have:
>
> You have created a 'Halt Decider' H.
>
> Alongside that, you also have a 'confounding case' P which you claim is
> derived from your H in the same way that Linz derives H_Hat from H (It
> isn't actually, but let's not worry about that for now).
>
> You also have a second Halt Decider H1 which is the same as H except
> that it 'does not have pathological self-reference'. You've never shown
> *any* code for this H1, but my assumption is that it is simply a copy of
> H, but since H1 resides at a distinct machine address from H, if H is
> called from within H1 it won't be seen as a recursive call.
>
> The problem here is that Linz's proof asserts that for any putative halt
> decider H, we can construct a new Turing Machine H_Hat which H will be
> unable to decide.
>
> Your H cannot correctly decide H(P, P). You seem to acknowledge this.
>
> Your H1 according to you *can* correctly decide H1(P, P).
>
> But your P isn't derived from your H1. It is derived from your H.
> Alongside your H1 there will be a P1 such that H1(P1, P1) will not be
> correctly decided, so you still aren't overcoming Linz.
>
> Linz doesn't claim that it is impossible for the halting status of
> H_Hat(H_Hat) to be decided. He claims only that it cannot correctly be
> decided by H.
>
> Basically (subject to seeing your actual code), you have a machine H
> which cannot correctly decide whether P(P) halts but which can correctly
> decide whether P1(P1) halts. You also have a machine H1 which can
> correctly decide whether P(P) halts but which cannot correctly decide
> whether P1(P1) halts. So neither of these can possibly count as a
> universal halt decider since each has a case it cannot decide. Neither
> your H nor your H1 can decide the corresponding case described by the
> Linz Proof.
>
> André
>

By using the H1/H pair we have a universal halt decider.
Whenever they don't provide the same result then one of them is wrong.

int main()
{
if (H1((u32)P, (u32)P) != H((u32)P, (u32)P))
OutputString("Pathological self-reference error!");

[olcott]

On 9/18/2021 6:09 PM, Richard Damon wrote:
> On 9/18/21 6:58 PM, olcott wrote:
>> On 9/18/2021 5:55 PM, André G. Isaak wrote:
>>> On 2021-09-18 16:32, olcott wrote:
>>>> On 9/18/2021 5:28 PM, André G. Isaak wrote:

>>>>> And since you have no idea *which* one of them is wrong, how exactly
>>>>> is it that you have a 'universal halt decider'?
>>>>>
>>>>> André
>>>>>
>>>>>
>>>>
>>>> I just defeated Rice's theorem, the other details are for another day.
>>>
>>> How exactly have you managed to do that?
>>>
>>
>> I already told you. I wish you would pay attention.

>>
>> int main()
>> {
>>   if (H1((u32)P, (u32)P) != H((u32)P, (u32)P))
>>     OutputString("Pathological self-reference error!");
>> }
>>
>>
>

> Which itself proves nothing.
>
> What is the precise Semantic Property that you are deciding on.
>
> Also, Rice's theorem requires a Decider to give the answer, so an if in
> main isn't the decider that disproves Rice.
>
> Define your property precisely enough that others can verify it.
>
> Define a decider (maybe call it R) that decides that property on a
> machine given to it.
>
> My first guess is that you mean R to be:
>
> u32 R(u32 P) {
> return H1(P,P) != H(P,P);
> }
>
> but now you have to specify what semantic property of P it is detecting.
>

As I have been saying since at least 2004:
As I have been saying since at least 2004:
As I have been saying since at least 2004:
As I have been saying since at least 2004:

The input has the exact same error as the Liar Paradox

[Halting Problem Final Conclusion]
comp.theory
Peter Olcott
Sep 5, 2004, 11:21:57 AM

The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

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

int main()
{
Output("Pathological Self-Reference(Olcott 2004) = ",
PSR_Olcott_2004((u32) P));

[olcott]

On 9/19/2021 1:00 AM, André G. Isaak wrote:
> On 2021-09-18 23:12, 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é
>>>
>>
>> Bingo! I have said it this same way recently.
>
> No, you have not.


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 rejects P on
> the basis that P has the
> pathological self-reference(Olcott 2004) error.

> decidability decider that correctly rejects P on
> the basis that P has the
> pathological self-reference(Olcott 2004) error.

> decidability decider that correctly rejects P on
> the basis that P has the
> pathological self-reference(Olcott 2004) error.

>
>> // Decidability Decider
>> u32 PSR_Olcott_2004(u32 P)
>> {
>>    return H1(P,P) == H(P,P);
>> }
>
> And how is the above related to anything I wrote in my original post or
> in the post clarifying that post to which you are responding? You don't
> answer the actual question which was asked (i.e. which semantic property
> do you claim to be able to decide using the above?) nor do you show even
> the remotest evidence of having even read my post.
>
> André

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

[olcott]

On 9/19/2021 11:56 AM, André G. Isaak wrote:

> Right, which means this is entirely irrelevant to Rice's theorem.
>

Many historical posts in comp.theory say otherwise.
If a function can be provided that correctly decides that a specific TM
cannot correctly decide a specific input pair (according to many
historical posts on comp.theory) this does refute Rice's theorem.

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

> No, it does not. It decides that the results of H1(P, P) doesn't match
> the results of H(P, P). It 'decides' that one of these is correct and
> the other is not but it cannot tell you which one, which means it can't
> decide whether H(P, P) can correctly decide the halt status of its input.
>

I simply have not gotten to that part yet.

>> thus a semantic property of H relative to P.
>

> That's not a property (semantic or otherwise) of *either* P or H.

>
>> The Liar Paradox works this same way.
>

> The liar's paradox is completely irrelevant to Linz.
>
> André
>

The pathological self-reference error (Olcott 2004) is specifically
relevant to:
(a) The Halting Theorem
(b) The 1931 Incompleteness Theorem
(c) The Tarski undefinability theorem
(d) The Liar Paradox (upon which (c) is based).

[Jeff Barnett]

On 9/19/2021 11:07 AM, olcott wrote:
> The pathological self-reference error (Olcott 2004) is specifically
> relevant to:
> (a) The Halting Theorem
> (b) The 1931 Incompleteness Theorem
> (c) The Tarski undefinability theorem
> (d) The Liar Paradox (upon which (c) is based).

Nothing you have done in the past two decades seems to be relevant to
anything. Seems? Just being polite. Actually, why bother: Nothing you
have done in the past two decades is relevant to anything. How long has
your illness made your brain dysfunctional? Friendly reminders: don't
get ahead of yourself; take your meds, all of them.

There are only two paths to long lasting fame for yourself: The first is
to write the USENET version of "The Trisectors" by Underwood Duddley.
The second is to collect two decades of your idiotic newsgroup threads
and turn them into a classic entitled "How to Go Directly from Stark
Personal Depression to Being a World Class Self-Deluded Troll Without
Missing a Meal."

The latter suggestion would be enhanced if you could put your
publication in an academic series with "How To Go Directly Into Solo Law
Practice Without Missing a Meal" by Gerald M. Singer (an LA lawyer).
Fame and notoriety all based on your original works awaits you. And now
we see how all those clever copyright annotations are going to pay off
with big bucks.
--
Jeff Barnett

[olcott]

On 9/19/2021 12:25 PM, André G. Isaak wrote:

> So what is the semantic property *of P* that you claim your
> PSR_Olcott_2004 is capable of identifying?
>
> You can't claim that there is anything 'erroneous' about P. There isn't.
>
> The fact that you run into a problem when you pass a description of P to
> some *other* TM is not an indicator that there is something wrong with
> P. That's like saying that the expression 40 + 50 is 'erroneous' because
> I can't pass it as an argument to tangent().

>
>>>> 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,
>>>
>>>
>>> No, it does not. It decides that the results of H1(P, P) doesn't
>>> match the results of H(P, P). It 'decides' that one of these is
>>> correct and the other is not but it cannot tell you which one, which
>>> means it can't decide whether H(P, P) can correctly decide the halt
>>> status of its input.
>>>
>>
>> I simply have not gotten to that part yet.
>

> And yet you claimed to be able to 'decide' that H(P, P) cannot correctly
> decide the halt status of its input. Until you actually 'get to that
> part' you have no business making such a claim.
>

Odd man out:
When H1(P,P) != H(P,P) we test
HX(P,P) != H1(P,P)
HX(P,P) != H(P,P)

The one that HX(P,P) agrees with is the correct one.

>>>> thus a semantic property of H relative to P.
>>>
>>> That's not a property (semantic or otherwise) of *either* P or H.
>>>
>>>> The Liar Paradox works this same way.
>>>
>>> The liar's paradox is completely irrelevant to Linz.
>>>
>>> André
>>>
>>
>> The pathological self-reference error (Olcott 2004) is specifically
>> relevant to:
>> (a) The Halting Theorem
>> (b) The 1931 Incompleteness Theorem
>> (c) The Tarski undefinability theorem
>> (d) The Liar Paradox (upon which (c) is based).
>

> So why don't you:
>
> (a) provide a proper definition of "pathological self-reference error"
>     That means a definition which will allow one to unambiguosly
> determine whether an arbitrary expression/entity has this error.

I just provided a reference to function that correctly decide this.
As long as my "pure function of its inputs" becomes fully validated
I will be able to provide the actual source-code that makes this decision.

> (b) explain in what sense an "error" is a property.
> (c) demonstrate that whatever property you are referring to is a
> *semantic* property.
>
> André
>

The pathological self reference error is when an
(a) Input P to a halt decider // halting theorem
has self-reference such that the Boolean value of H(P,P)
cannot be correctly determined by H.

(b) An expression of natural language // liar paradox
has self-reference such that the Boolean value this expression cannot be
correctly determined.

(c) An expression of formal language // incompleteness / undefinability.
has self-reference such that the Boolean value this expression cannot be
correctly determined within the same formal system.

[olcott]

On 9/19/2021 1:24 PM, André G. Isaak wrote:

> There are a potentially infinite number of Hns. Your 'decider' only
> qualifies as a decider if it works for *every* one of them. Your 'odd
> man out strategy' only works if the case you are testing happens to be
> among the three which are included in your test function.
>

The halting theorem is based on an artificially contrived example that
would never actually occur in actual practice. In actual practice we
would only actually need H.

The odd-man-out system does correctly decide an input that was
artificially contrived to specifically have the pathological
self-reference error (Olcott 2004) for either H or H1. All of the rest
of the cases are simply correctly decided by either H or H1.

>>>>>> thus a semantic property of H relative to P.
>>>>>
>>>>> That's not a property (semantic or otherwise) of *either* P or H.
>>>>>
>>>>>> The Liar Paradox works this same way.
>>>>>
>>>>> The liar's paradox is completely irrelevant to Linz.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> The pathological self-reference error (Olcott 2004) is specifically
>>>> relevant to:
>>>> (a) The Halting Theorem
>>>> (b) The 1931 Incompleteness Theorem
>>>> (c) The Tarski undefinability theorem
>>>> (d) The Liar Paradox (upon which (c) is based).
>>>
>>> So why don't you:
>>>
>>> (a) provide a proper definition of "pathological self-reference error"
>>>      That means a definition which will allow one to unambiguosly
>>> determine whether an arbitrary expression/entity has this error.
>>
>> I just provided a reference to function that correctly decide this.
>

> No. You provided an ad hoc function which decides it for a *single*
> case. That's not the same thing as a function which correctly decides it.
>

This will come later when my "pure function of its inputs" has been
totally validated.

> It is a well-established fact that you cannot trisect an arbitrary angle
> using only a compass and straightedge. I can show you how to trisect a
> 90° angle using a compass and straightedge, but this doesn't refute the
> claim. Only a solution which works for *any* angle would refute the claim.

>
>> As long as my "pure function of its inputs" becomes fully validated
>> I will be able to provide the actual source-code that makes this
>> decision.
>>
>>> (b) explain in what sense an "error" is a property.
>>> (c) demonstrate that whatever property you are referring to is a
>>> *semantic* property.
>>>
>>> André
>>>
>>
>> The pathological self reference error is when an
>> (a) Input P to a halt decider   // halting theorem
>> has self-reference such that the Boolean value of H(P,P)
>> cannot be correctly determined by H.
>> (b) An expression of natural language // liar paradox
>> has self-reference such that the Boolean value this expression cannot
>> be correctly determined.
>>
>> (c) An expression of formal language // incompleteness / undefinability.
>> has self-reference such that the Boolean value this expression cannot
>> be correctly determined within the same formal system.
>

> None of those constitute definitions. Nor do they identify properties.
> And if you want to claim that PSR is an actual thing, you need a single
> definition. And, as has been pointed out to you numerous times, neither
> the halting problem proofs nor the incompleteness theorem involve
> self-reference at all. This is just your imaginary bugaboo.
>
> André

[olcott]

On 9/20/2021 9:21 PM, Richard Damon wrote:
> On 9/20/21 9:33 PM, olcott wrote:
>> On 9/20/2021 8:28 PM, Richard Damon wrote:
>>> On 9/20/21 7:33 PM, olcott wrote:
>>>> On 9/20/2021 5:06 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 9/20/2021 5:00 AM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> The two machines are already fully operational.
>>>>>>>> H1 is merely a copy of H.
>>>>>>> It's deceptive to call your secret C functions "machines".  It
>>>>>>> hints at
>>>>>>> the formality a clarity of Turing machines, but a TM that is a
>>>>>>> copy of
>>>>>>> another will have exactly the same transfer function (i.e. it will
>>>>>>> never
>>>>>>> compute a different result).
>>>>>>
>>>>>> Unless one of them has a pathological self-reference relationship with
>>>>>> its input and the other one does not.
>>>>>
>>>>> No.  I stated a fact (about TMs) that has no exceptions.  Your secret C
>>>>> code is another matter, of course.  It's just the deception of calling
>>>>> your code a "machine" that I was objecting to.  It gives your hidden
>>>>> code an air of formality that it lacks.
>>>>>
>>>>
>>>> This is easily proven in a way that you are incapable of understanding.
>>>>
>>>> void P(u32 x)
>>>> {
>>>>    if (H(x, x))
>>>>      HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>>    Output("Input_Halts = ", H((u32)P, (u32)P));
>>>>    Output("Input_Halts = ", H1((u32)P, (u32)P));
>>>> }
>>>>
>>>> Line 1 of main() specifies a different computation than line 2 of main()
>>>> even though the source code of H1 is a copy of H.
>>>>
>>>
>>> Right, and since it is a DIFFERENT computation, it doesn't count that it
>>> can decide P.
>>>
>>> It is only the computation that P (really H^) is built on that matters.
>>>
>>> Since H and H1 are different computaitons, H1 doesn't count.
>>>
>>
>> They are only different because of the pathological self reference
>> (self-contradiction) error. All inputs not having this error relative to
>> their halt decider derive identical results for both H and H1.
>>
>
> There is NO 'pathological self reference error' for Turing machines,
> because they CAN'T self reference, only provide copies.
>

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ halts, and

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
if the simulated ⟨Ĥ⟩ applied to ⟨Ĥ⟩ does not halt

Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ does specify infinitely nested simulation to every
simulating halt decider: Ĥ.qx

Ĥ does have its own machine description as its input so
IT IS SELF-REFERENCE

H ⟨Ĥ⟩ ⟨Ĥ⟩ does not specify infinitely nested simulation to any
simulating halt decider: H

H does not have its own machine description as its input so
IT IS NOT SELF-REFERENCE

It doesn't matter what this difference is called, it can even be called
"late for dinner". That this difference exists and causes the behavior
to vary is what needs to be known.

[olcott]

> Either H.q0 <H^><H^> and H^.qx <H^><H^> both transition to their
> respective rejecting states, or H.q0 <H^><H^> transitions to H.qy and
> H^.qx <H^><H^> does not halt. This difference in behaviour is of no
> help to you.
>
> Feel free to quote me. I won't deny having said this next week. If I
> find I'm wrong about it, I'll say so. That's what an honest person
> does. Whether anything /you/ say can be trusted will depend on how you
> respond to other recent posts.
>

The same initial input to a specific partial halt decider instance H
must always consistently derive the same final output is sustained.

That an exact copy of this partial halt decider instance H1 must alway
derive the same results as the original on the same input as the orginal
seems to be refuted.

The only exception to the rule may be when the input invokes one of
these instances and not the other one.

Ĥ applied to ⟨Ĥ⟩ is applied to its own TM description.
H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ is NOT applied to its own TM description.
This makes the two computations distinctly different.

It may be the case that this is the only exception where identical
machines on the same input do not derive identical results.