Re: A UTM halt decider <is> a pure function of its inputs (Pure function of COFF file)

[olcott]

On 4/1/2021 12:47 PM, Richard Damon wrote:
> On 4/1/21 12:57 PM, olcott wrote:
>> On 4/1/2021 11:43 AM, Richard Damon wrote:
>
>>> To a finite level, it is easy to envision, and, because you have assumed
>>> that Halts can detect the recursion attempt and stop the recursion, you
>>> will only ever reach a finite level.
>>>
>>> If you ACTUALLY get to an infinite depth, then by definition your
>>> computation will be non-halting.
>>>
>>> Now, each stage gets slower and slower to run, but time is immaterial to
>>> Turing Machines (except maybe to O() notation).
>>>
>>> If a UTM needs 100 states to simulate a state of its simulated machine,
>>> then the first simulated UTM will be running at 1/100th speed, and the
>>> machine it is simulating now runnning at 1/10,000 speed and so on when
>>> looked at from the perspective of the top level.
>>>
>>> Of course, since a machine can't tell that it is running inside a UTM,
>>> it thinks it is doing just fine.
>>>
>>> I've actually seen this done several layers deep where each layer of
>>> simulator is actually simulating a different architecture, and the
>>> original machine the inner simulator was designed for isn't available
>>> anymore is is just run in a simulator.
>>>
>>
>> How would you define a UTM X that simulates another UTM Y that simulates
>> another UTM Z infinitely?
>>
>> How would you define a UTM H that simulates another UTM H^ that
>> simulates another UTM Z infinitely, such that the infinite simulation
>> can be detected?
>>
>>
> I thought you knew how to write a REAL simulator. First thing you need
> to realize is that you will NEVER be able to build a 'real' simulator
> that goes infinitely deep, as that will require infinite memery, so
> until you can figure out how to store infinite information in a finite
> space you are out of luck (one problem with trying to model the
> potentially infinite Turing Machine on a strictly finite processor).
>
> First, Detecting the infinite recursion is YOUR problem, that is a core
> feature to your proof, and in my opinion, ultimately it can't be done,
> but if it can't be done, your proof fails, so it is up to you to figure
> out, but you have to do it with a system that is built right, which is
> what makes it hard.
>
> How to build nested UTMS.
>
> First, you place in the top Turing Machine code for the UTM that is at
> the top level. By definition, it has a finite number of states, and so
> when we write a program that uses it as part of its computation, it will
> add a finite length to the representation of that program. This
> repesentation for the program and its input are placed on the tape and
> the machine started. The UTM will then start processing the
> representation of the program, and adding somewhere on the tape the
> scratch data that the UTM needs to run its simulation of the machine
> (like the current state of that machine).
>
> One thing to note, Current state might be kept track of by inserting a
> special code at the beginning of the representation for the current
> state in the representation of the machine.
>
> At each step, the UTM will need to move its tape to the point that
> represents the current tape position of the machine, read what symbol is
> there, then go back to the current state and see what the next state
> should be (and mark it) and what if any output to make, and then go to
> the tape to do that.
>
> Now, if the code represented on the taps just happens to be another UTM
> (or a copy of itself), the UTM just keeps running like this executing
> the states as that machine goes through its paces, and is those states
> reference the tape it keeps moving back and forth and just runs.
>
> If you are losing yourself in that description, because it is too
> abstract, let us look at how to do simulators on a standard computer.
>

We take the simpler case of a master UTM M that is simulating a UTM H
that is simulating itself.

The master UTM M has a portion of its own tape for
(a) The machine description of the simulated UTM H
(b) The tape of the simulated UTM H
(c) A scratch area for M to perform the simulation of H

If a UTM is literally simulating itself then every time that it does
this it must provide a tape for each subsequent simulation. If it makes
a copy of itself and simulates the copy then it is not simulating
itself. The only way to model actual recursion is for a UTM to literally
simulate itself without making a copy.

--
Copyright 2021 Pete Olcott

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