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.

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

--
To email remove 'invalid' & replace 'gm' with well known Google mail
service.