On 9/21/21 3:25 PM, 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.
>
>
>> 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.
>
>> 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
> 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.

No, C is not 'More Powerful' in the sense that any Computation that you
can do in C, you can also do on a Turing Machine.

PERIOD.

Yes, C code FRAGMENTS can do things that Turing Machine Fragments can't
do, but you don't actually run fragments, only programs, and in general
a program will be a computation, so C programs can be replicated by
Turing Machines (They may use different techniques to do the job, but
they give the eqivalent answer)

The one exception is if the program 'talks' to something external like
another computer or some special hardware. The basic Turing Machine has
limited I/O so that can't be copied, but that isn't important to
Computation Theory.

A cluster of Computers that talk to each other and together perform a
computation CAN be converted into a Turing Machine.

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

If your holding the execution trace still keeps you a Computation, then
a Turing Machine can do it, it just may be done differently.

One key thing is that with Turing Machines, often the 'recursion' is
converted into iteration, which is simpler to handle.

>
> If the only way that it can do this requires passing the execution trace
> through P where P can erase it, then again TM's are strictly less
> powerful that my C function.

But IS that the only way, and is the way you are doing it keeping your
machine a computation? So far you haven't been very good at proving that
H is actually a computation.

>
>> But then you're not dealing with the halting problem which asks about
>> a hypothetical computation whose input consists only of a description
>> of a machine and its input and whose output is simply accept or reject.
>>
>> André
>>
>
> The full execution trace across multiple recursive invocations <is> a
> pure function of the original input machine addresses. It seems that
> this is the point where you err.
>
>

If THAT is the way you are looking at it, the the top level H ISN'T the
Computation, but the WHOLE series of machines is, at which point your H
and your P have lost their independent identities, and you fail to make
the form of Linz. You H isn't a complete computation in itself, but has
been merged with the machine it is deciding (this sort of also come out
of the fact that P isn't in a seperate address space, but part of H).

I think where this is coming from is that you aren't actually
'simulating' the inner layers, but 'single stepping them' as part of the
main program (with their own stack) and the inner copies of H are doing
the deciding work of the outer 'simulator' (who isn't really simulating).

As I said, this rolls the whole bundle into a single
computation/machine, so H isn't a complete computation by itself, it
NEEDS to have a copy of the machine it is being asked to 'simulate' as
part of its code.