On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:There is no self-reference trap.On 15/05/2025 19:49, wij wrote:Supposed UTM exists, and denoted as U(X), X denotes the tape contents of theOn Thu, 2025-05-15 at 17:08 +0100, Mike Terry wrote:>On 14/05/2025 18:53, wij wrote:>On Wed, 2025-05-14 at 12:24 -0500, olcott wrote:>On 5/14/2025 11:43 AM, wij wrote:>On Wed, 2025-05-14 at 09:51 -0500, olcott wrote:>On 5/14/2025 12:13 AM, wij wrote:>Q: Write a turing machine that performs D function (which calls itself):>
>
void D() {
D();
}
>
Easy?
>
>
That is not a TM.
It is a C program that exists. Therefore, there must be a equivalent TM.
>To make a TM that references itself the closest>
thing is a UTM that simulates its own TM source-code.
How does a UTM simulate its own TM source-code?
>
You run a UTM that has its own source-code on its tape.
What is exactly the source-code on its tape?
>
Every UTM has some scheme which can be applied to a (TM & input tape) that is to be simulated.
The
scheme says how to turn the (TM + input tape) into a string of symbols that represent that
computation.
>
So to answer your question, the "source-code on its tape" is the result of applying the UTM's
particular scheme to the combination (UTM, input tape) that is to be simulated.
>
If you're looking for the exact string symbols, obviously you would need to specify the exact
UTM
being used, because every UTM will have a different answer to your question.
>
>
Mike.
People used to say UTM can simulate all TM. I was questing such a UTM.
Because you said "Every UTM ...", so what is the source of such UTM?
Yes, a UTM can simulate any TM including itself. (Nothing magical changes when a UTM simulates
itself, as opposed to some other TM.)
encoding of a TM. And, U(X) should function the same like X.
Given instance U(U(f)), it should function like f from the above definition.
But, U(U(f)) would fall into a 'self-reference' trap.
In your notation:
- f represents some computation.
- U(f) represents U being run with f on its tape.
Note this is itself a computation, distinct from f of course
but having the same behaviour.
- U(U(f)) represents U simulating the previous computation.
There is no reason U(f) cannot be simulated by U. U will have no knowledge that it is "simulating itself", and will just simulate what it is given.
Mike.
| Date | Sujet | # | Auteur | |
| 21 May 26 |  … |
Les messages affichés proviennent d'usenet.