On 9/21/2021 10:45 PM, André G. Isaak wrote:
> On 2021-09-21 13:25, olcott wrote:
>> On 9/21/2021 1:43 PM, André G. Isaak wrote:
>>> On 2021-09-21 12:22, olcott wrote:
>>>> On 9/21/2021 12:51 PM, André G. Isaak wrote:
>>>>> On 2021-09-21 09:19, olcott wrote:
>>>>>> On 9/21/2021 7:23 AM, Richard Damon wrote:
>>>>>>>
>>>>>>> On 9/21/21 12:55 AM, olcott wrote:
>>>>>>>> o in other words a C function with static local data can detect
>>>>>>>> that it
>>>>>>>> was called in infinitely nested simulation, yet a TM is not
>>>>>>>> allowed to
>>>>>>>> have static local data therefore the C function is strictly more
>>>>>>>> powerful than a TM.
>>>>>>>
>>>>>>> Just to clarify a bit here.
>>>>>>>
>>>>>>> A C/x86 code FRAGMENT can do more than a Turing Machine Code
>>>>>>> Fragment,
>>>>>>> as Turing Machine fragments are still computations. but C/x86
>>>>>>> don't need
>>>>>>> to be.
>>>>>>>
>>>>>>> By Code fragment, I mean a piece of code that some 'Program' will
>>>>>>> enter
>>>>>>> and exit from multiple times, and the fragment is allowed to keep
>>>>>>> some
>>>>>>> 'internal' state that the rest of the program doesn't know about.
>>>>>>>
>>>>>>> Computation Theory doesn't care about this, as it only deals with
>>>>>>> Computations as a whole, not fragments.
>>>>>>>
>>>>>>> On the other hand, a whole C/x86 PROGRAM (or Subprogram) can't do
>>>>>>> anything that a Turng Machine can't do (the Turing Machine might
>>>>>>> do it
>>>>>>> differently, but can give the same results). By a Program, I mean a
>>>>>>> piece of code that is entered when it starts, and it stays within
>>>>>>> the
>>>>>>> program until it finishes, and gives up it output to what ever
>>>>>>> was using it.
>>>>>>>
>>>>>>
>>>>>> Then H(P,P) is a computation based on its initial input and final
>>>>>> output even though it requires static local data.
>>>>>>
>>>>>> The bottom line is that a TM must use the equivalent of static
>>>>>> local data to be able to keep track that it is stuck in infinitely
>>>>>> nested simulation:
>>>>>>
>>>>>> the simulation of the
>>>>>>
>>>>>> machine description of a UTM H that simulates
>>>>>> the machine description P the simulates
>>>>>>
>>>>>> machine description of a UTM H that simulates
>>>>>> the machine description P the simulates
>>>>>>
>>>>>> machine description of a UTM H that simulates
>>>>>> the machine description P the simulates ...
>>>>>>
>>>>>> Olcott H can detect when Olcott P is doing this only when Olcott H
>>>>>> is able to use static local data, otherwise Olcott H has its
>>>>>> memory of prior invocations erased upon every subsequent simulation.
>>>>>>
>>>>>> It seems ridiculous that this level of functionality is simply
>>>>>> disallowed. If it is simply disallowed then that makes my H
>>>>>> strictly more powerful than the Linz TM H can be.
>>>>>
>>>>> The problem here is that you are trying to somehow justify your use
>>>>> of static variables without making any effort to understand what a
>>>>> computation actually is.
>>>>>
>>>>> The question which the theory of computation deals with (very
>>>>> simplistically) is as follows:
>>>>>
>>>>> Given some set of information I, how do we construct a method M for
>>>>> solving some problem P using *only* the information in I.
>>>>>
>>>>
>>>> This becomes simply impossible when I is merely the machine address
>>>> of the software that must be simulated.
>>>
>>> Turing Machines don't *have* machine addresses.
>>
>> Sure they do, merely no one ever references them. Each state / input
>> pair is a single machine code instruction at a specific machine code
>> address.
>
> No, they do not. Nor do they have machine code instructions. You can't
> just make shit up and expect people to believe you.

The only way that state transitions can actually be implemented requires
current_state / current_input pairs that map to the next state.

Whenever this is not intentionally kept vague it involves integer pairs
that map to another integer.

Whenever this is not intentionally kept vague it involves these pairs
and their mapped state to be stored in some specific location.

Whatever this specific location is can be construed as its machine address.

Typically all these things are left intentionally vague.
Just because no one ever talks about the additional details does not
mean that they are not actually required.

Vagueness merely means that some details have not been specified.
It does not mean that these details do not exist.

>
>>
>>> In the Linz proof, the TM is passed a *description* of the TM and an
>>> input string.
>>>
>>> In the case of your H, if you want to think of it as a computation,
>>> the input would be the *entire* block of code pointed to by the
>>> function pointer, plus the actual string pointed to by the second
>>> parameter. It wouldn't simply be the pointer values themselves.
>>>
>>
>> That merely makes it more cumbersome.
>
> Avoiding cumbersomeness isn't a legitimate reason for doing things the
> wrong way.
>
>>> This is what I am trying to point out to you. The parameters given in
>>> a C function call *don't* correspond to the input string used when
>>> discussing Turing Machines/computations. So just because you have a C
>>> function whose formal parameters resemble that of the input string to
>>> some TM doesn't mean you're dealing with things that are equivalent
>>> or which deal with the same computation.
>>
>> The machine address points to a specific machine code string.
>>
>>>
>>>>> M would be a Turing Machine. I would be the input string to that
>>>>> machine. P would be something like 'does this computation halt?'.
>>>>>
>>>>> The difference between Turing Machines and C isn't that C is
>>>>> somehow more powerful than Turing Machines, it's simply that the
>>>>> way C functions are expressed doesn't map directly to the theory of
>>>>> computation because the formal parameters to a C function don't
>>>>> represent all the information available to the routine; they
>>>>> represent only the information that is passed via the stack which
>>>>> may or may not be all of the information which the function has
>>>>> access to. Information may also be passed in global variables,
>>>>> static variables, etc. Thus, the input to a C function doesn't
>>>>> necessarily represent the same thing that the input to a TM does.
>>>>>
>>>>> If you want to analyze a C function as a computation, you need to
>>>>> gather all the information which the C function makes use of
>>>>> *including* information accessed from sources other than the formal
>>>>> parameters. So to discuss your H in terms of computational theory
>>>>> the set I would consist of the formal paramters of H *plus* the
>>>>> static variable which the function also makes use of as a source of
>>>>> information.
>>>>>
>>>>> We could then construct some Turing Machine which takes an input
>>>>> string representing {P, P, static_execution_trace}. So a Turing
>>>>> Machine is perfectly capable of implementing your H.
>>>>>
>>>>
>>>> This works just fine when we pass the execution trace to P, except
>>>> that P is free to erase the whole execution trace every time that it is
>>>> called.
>>>
>>> Right, because every computation starts with a tabula rasa.
>>>
>>
>> This artificially constrains TM preventing them from having the same
>> power as C. A C function can correctly determine when it has been
>
> This isn't an artificial constraint, nor does it imply that C is somehow
> more powerful. The problem here is that C functions don't map directly
> to computations in many cases, or at least not to the computation that
> the functions prototype would suggest. As I said, when talking about
> computations *all* sources of information supplied to the computation
> are considered part of the input.
>
> So a C function like int
>
> int foo(int x) {
>     return(x+someGlobal)
> }
>
> would have a corresponding Turing Machine whose input string consists of
> *two* components, y and someGlobal. The above *is* a computation; it
> just isn't a computation of a function from x to foo(x). And for any C
> function, if you want to talk about it as a computation you may need to
> restructure it in a similar way.
>
> While people have claimed your H isn't really a computation, what's
> really intended by that is to say that it isn't really the computation
> you claim it to be. It corresponds to a Turing Machine with (minimally)
> *three* components to its input string, not just the two which have been
> declared as formal parameters. And one whose output consists of more
> than a simple binary value but also of an update trace. Which means it
> *can't* be equivalent in any sense to the computation represented by
> Linz's H whose input string consists of only two components and which
> simply accepts or rejects that input.
>
> The C language simply isn't designed with representing or discussing
> computations in mind. Its designed for writing computer programs. Turing
> Machines, on the other hand, were specifically designed with the goal of
> representing and discussing computations. So basically, you're using the
> wrong tool.
>
> It's like deciding you want to come up with a theory of the real numbers
> and then opting to use Roman numerals. Yes, you might be able to do it
> but it would be an incredibly stupid choice.
>
>> involved in infinitely nested simulation a TM that obeys the
>> aribitrary rules cannot. This makes C strictly more powerful than
>> TM's. Since it is much more plausible that you are simply wrong that
>> is what I conclude.
>>
>>> If you want to claim what you are trying to do is equivalent to a
>>> Turing Machine, that machine would have to be one which takes the
>>> execution trace as part of its input string and which writes a new
>>> execution trace to the tape as part of its output which could then be
>>> fed to a new computation.
>>>
>>
>> Unless it can hold the entire execution trace across nested
>> simulations it is strictly less powerful that the C function that can.
>
> TMs can do this, but it would require that said trace (or whatever you
> view the TM equivalent to be since TMs don't really have traces) be
> passed as a formal input to each invocation and that any changes be
> written to the tape as part of each invocations output. TMs are no less
> capable of doing it than C functions, but with C you can obscure *which*
> computation is actually being performed so that you can make a function
> which has a prototype which *looks* like Linz's H but which really an
> entirely different type of computation. With TMs you are forced to more
> clearly express what is going on.
>
> André
>

--
Copyright 2021 Pete Olcott

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