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:
>>>>>
>>>>> On 9/18/21 9:54 AM, olcott wrote:
>>>>>> 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
>>>>>>
>>>>>
>>>>> 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 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.
>>>>>
>>>>
>>>>
>>>
>>
>>
>

--
Copyright 2021 Pete Olcott

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