Q: Write a turing machine that performs D function (which calls itself):
void D() {
D();
}
Easy?
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?
On Wed, 2025-05-14 at 18:14 +0100, Richard Heathfield wrote:
On 14/05/2025 17:43, wij wrote:
On Wed, 2025-05-14 at 09:51 -0500, olcott wrote:
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?
It doesn't have to simulate anything. All it has to do is to
restore the state into which the programmer wishes to recurse.
So, when you say "A UTM simulates X", it means 'the UTM' doesn't have to do anything. So, 'UTM' is human (e.g. you), not a real TM?
I've already shown how this can be done.
Where?
On Wed, 2025-05-14 at 18:49 +0100, Richard Heathfield wrote:
On 14/05/2025 18:33, wij wrote:
On Wed, 2025-05-14 at 18:14 +0100, Richard Heathfield wrote:
On 14/05/2025 17:43, wij wrote:
On Wed, 2025-05-14 at 09:51 -0500, olcott wrote:
<snip>
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?
It doesn't have to simulate anything. All it has to do is to
restore the state into which the programmer wishes to recurse.
So, when you say "A UTM simulates X", it means 'the UTM' doesn't have to do
anything. So, 'UTM' is human (e.g. you), not a real TM?
No, it doesn't mean that.
You said "It doesn't have to simulate anything. All it has to do is to restore the state into which the programmer wishes to recurse."
Then, what is it?
Here's the gist of that article...I've already shown how this can be done.
Here's the tape:
[0]
current state: 0
content of the square being scanned: 0
new content of the square: 0
move left, right, or stay: stay
next state: 0
This TM functions by returning the state of the machine to its
starting state.
The only functional difference between this code and yours is
that yours will blow the stack. (Mine doesn't have a stack to blow.)
1. Apparently your TM (one single symbol '0') is not what you say.
2. D() should have at least one final state
On 5/14/2025 3:00 PM, Keith Thompson wrote:
Richard Heathfield <rjh@cpax.org.uk> writes:
[...]
See <https://plato.stanford.edu/entries/turing-machine/>[...]
where you can read this:
"A Turing machine then, or a computing machine as Turing
called it, in
Turing’s original definition is a machine capable of a finite
set of
configurations q1,…,qn (the states of the machine, called
m-configurations by Turing). It is supplied with a one-way
infinite
and one-dimensional tape divided into squares each capable of
carrying
exactly one symbol. At any moment, the machine is scanning the
content
of one square r which is either blank (symbolized by S0) or
contains a
symbol S1,…,Sm with S1=0 and S2=1."
There's more to TMs than tapes.
Interesting. The phrase "one-way infinite" implies that the tape
is infinite in only one direction, so the cells can be indexed by
non-negative integers. Elsewhere on that web page, it
acknowledges
that there are variations in Turing machines, including one-way
vs. two-way infinite tapes. It's implied that Turings original
concept had a one-way infinite tape. I wasn't able to confirm or
deny that in a very quick look through Turings original paper.
I've always assumed that a TM tape is two-way infinite.
I presume that one-way and two-way infinite tapes are
computationally
equivalent, so the distinction doesn't matter all that much.
(Though with a one-way tape, I'm not sure what happens if the TM
runs off the end of the tape.)
I don't think that is precisely accurate.
A unlimited tape is not an infinite tape
it merely has all of the space that it needs.
I presume that one-way and two-way infinite tapes are computationally equivalent, so the distinction doesn't matter all that much.
(Though with a one-way tape, I'm not sure what happens if the TM
runs off the end of the tape.)
Richard Heathfield <rjh@cpax.org.uk> writes:
On 14/05/2025 21:00, Keith Thompson wrote:
<snip>
I presume that one-way and two-way infinite tapes are computationally
equivalent, so the distinction doesn't matter all that much.
(Though with a one-way tape, I'm not sure what happens if the TM runs
off the end of the tape.)
I should imagine that you could build one hell of a stack on one-way
tape.
Of course, the tape doesn't /have/ to be infinite. It only has to be
long enough so that you /don't/ run off the end. Just how long that is
depends on what problem you're addressing.
In the Real World, tapes can't be infinite, so an implementor has to
decide how long 'long enough' is.
TM's don't necessarily operate in the Real World.
If the TM's alphabet consisted of 256 discrete symbols (no reason why
not) a megabyte would give you a disk-based 'tape' a million cells
long.
Ought to be enough for `take one down and pass it around'.
Sure. "Infinite tape" might be more precisely expressed as "sufficient tape". But a TM that advances in one direction along the tape in a loop
will require more than any finite length of tape if you leave it running
long enough, though the amount of tape it consumes in any finite number
of steps is still finite. For that kind of TM in particular, "infinite
tape" is a convenient shorthand.
Richard Heathfield <rjh@cpax.org.uk> writes:
In the Real World, tapes can't be infinite, so an implementor has to
decide how long 'long enough' is.
TM's don't necessarily operate in the Real World.
If the TM's alphabet consisted of 256 discrete symbols (no reason why
not) a megabyte would give you a disk-based 'tape' a million cells
long.
Ought to be enough for `take one down and pass it around'.
Sure. "Infinite tape" might be more precisely expressed as
"sufficient tape".
But a TM that advances in one direction along
the tape in a loop will require more than any finite length of tape
if you leave it running long enough, though the amount of tape it
consumes in any finite number of steps is still finite. For that
kind of TM in particular, "infinite tape" is a convenient shorthand.
Richard Heathfield <rjh@cpax.org.uk> writes:
[...]
Using a highly questionable collection of approximations about the
physical properties of 4mm mylar tape and the number of atoms in the
universe, I calculated that by devoting /everything/ to this tape we
could make it
5285412262156448202959830866807610993657505285
lightyears long (exACtly, of course).
It's still a long way off infinite, but I think it could possibly
qualify as 'long enough'.
It's still not long enough for a TM that repeatedly advances its
position in one direction while indefinitely repeating the same state.
Richard Heathfield <rjh@cpax.org.uk> writes:
[...]
See <https://plato.stanford.edu/entries/turing-machine/>[...]
where you can read this:
"A Turing machine then, or a computing machine as Turing called it, in
Turing’s original definition is a machine capable of a finite set of
configurations q1,…,qn (the states of the machine, called
m-configurations by Turing). It is supplied with a one-way infinite
and one-dimensional tape divided into squares each capable of carrying
exactly one symbol. At any moment, the machine is scanning the content
of one square r which is either blank (symbolized by S0) or contains a
symbol S1,…,Sm with S1=0 and S2=1."
There's more to TMs than tapes.
Interesting. The phrase "one-way infinite" implies that the tape
is infinite in only one direction, so the cells can be indexed by non-negative integers. Elsewhere on that web page, it acknowledges
that there are variations in Turing machines, including one-way
vs. two-way infinite tapes. It's implied that Turings original
concept had a one-way infinite tape. I wasn't able to confirm or
deny that in a very quick look through Turings original paper.
I've always assumed that a TM tape is two-way infinite.
I presume that one-way and two-way infinite tapes are computationally equivalent, so the distinction doesn't matter all that much.
(Though with a one-way tape, I'm not sure what happens if the TM
runs off the end of the tape.)
On 14/05/2025 21:00, Keith Thompson wrote:
I presume that one-way and two-way infinite tapes are computationally
equivalent, so the distinction doesn't matter all that much.
(Though with a one-way tape, I'm not sure what happens if the TM
runs off the end of the tape.)
I should imagine that you could build one hell of a stack on one-way tape.
Of course, the tape doesn't /have/ to be infinite. It only has to be long enough so that you /don't/ run off the end. Just how long that is depends
on what problem you're addressing.
In the Real World, tapes can't be infinite, so an implementor has to decide how long 'long enough' is.
If the TM's alphabet consisted of 256 discrete symbols (no reason why not)When I was lecturing this stuff, it was common for software to be delivered as a stack of floppy discs accompanied by instructions such as
a megabyte would give you a disk-based 'tape' a million cells long.
Q: Write a turing machine that performs D function (which calls itself):
void D() {
D();
}
Easy?
Richard Heathfield <rjh@cpax.org.uk> writes:
[...]
See <https://plato.stanford.edu/entries/turing-machine/>[...]
where you can read this:
"A Turing machine then, or a computing machine as Turing called it, in
Turing’s original definition is a machine capable of a finite set of
configurations q1,…,qn (the states of the machine, called
m-configurations by Turing). It is supplied with a one-way infinite
and one-dimensional tape divided into squares each capable of carrying
exactly one symbol. At any moment, the machine is scanning the content
of one square r which is either blank (symbolized by S0) or contains a
symbol S1,…,Sm with S1=0 and S2=1."
There's more to TMs than tapes.
Interesting. The phrase "one-way infinite" implies that the tape
is infinite in only one direction, so the cells can be indexed by non-negative integers. Elsewhere on that web page, it acknowledges
that there are variations in Turing machines, including one-way
vs. two-way infinite tapes. It's implied that Turings original
concept had a one-way infinite tape. I wasn't able to confirm or
deny that in a very quick look through Turings original paper.
I've always assumed that a TM tape is two-way infinite.
On Wed, 14 May 2025 13:49:03 -0700, Keith Thompson wrote:
Richard Heathfield <rjh@cpax.org.uk> writes:
On 14/05/2025 21:00, Keith Thompson wrote:
<snip>
I presume that one-way and two-way infinite tapes are computationally
equivalent, so the distinction doesn't matter all that much.
(Though with a one-way tape, I'm not sure what happens if the TM runs
off the end of the tape.)
I should imagine that you could build one hell of a stack on one-way
tape.
Of course, the tape doesn't /have/ to be infinite. It only has to be
long enough so that you /don't/ run off the end. Just how long that is
depends on what problem you're addressing.
In the Real World, tapes can't be infinite, so an implementor has to
decide how long 'long enough' is.
TM's don't necessarily operate in the Real World.
If the TM's alphabet consisted of 256 discrete symbols (no reason why
not) a megabyte would give you a disk-based 'tape' a million cells
long.
Ought to be enough for `take one down and pass it around'.
Sure. "Infinite tape" might be more precisely expressed as "sufficient
tape". But a TM that advances in one direction along the tape in a loop
will require more than any finite length of tape if you leave it running
long enough, though the amount of tape it consumes in any finite number
of steps is still finite. For that kind of TM in particular, "infinite
tape" is a convenient shorthand.
Flibble's Law still applies:
If a problem permits infinite behavior in its formulation, it permits infinite analysis of that behavior in its decidability scope.
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?
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
If there was such a UTM then examining things
like a termination analyzer would be too difficult
because of the volume of details. Even moving a
single value to a specific memory location can
take many many steps.
A RASP machine https://en.wikipedia.org/wiki/Random-access_stored-program_machine
is a much better fit for examining the details of any
complex algorithm.
The x86 language is essentially the same thing as a RASP
machine for all computations that can be accomplished
with the amount of memory that is available.
To be a computable function within a model of computation
a sequence of the steps of a specific algorithm must be
applied to (an often finite string) input to derive an output. https://en.wikipedia.org/wiki/Computable_function
When computing the sum() function the steps of the algorithm
of arithmetic must be applied to the inputs.
*When computing the halt() function steps with a simulating*
*termination analyzer the behavioral steps specified by the*
*input must be simulated according to the computer language*
*of this input*
*I may be wrong yet it seems to me that*
Computer science never knew these things before in that
it never placed any limit on the type of algorithm that
must be performed.
I think that it was Ben that said that one of two
functions that do nothing besides return true or false
is correct on all of the counter-example inputs
to the halting problem.
When we require that a mapping be computed from an
input, then this idea is rejected.
If you're just playing/learning about TMs then probably you
really just want a very basic TM emulator
On 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?
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the 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.
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.
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
On 5/15/2025 2:57 PM, wij wrote:
On Thu, 2025-05-15 at 11:47 -0500, olcott wrote:
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
Sort of.
If there was such a UTM then examining things
like a termination analyzer would be too difficult
because of the volume of details. Even moving a
single value to a specific memory location can
take many many steps.
So, which part of POOH is "fully encoded UTM"
A RASP machine
https://en.wikipedia.org/wiki/Random-access_stored-program_machine
is a much better fit for examining the details of any
complex algorithm.
The x86 language is essentially the same thing as a RASP
machine for all computations that can be accomplished
with the amount of memory that is available.
Absolutely false. POOH is the example that rejected TM/RASP instead of C.
In trying making P!=NP proof (may have defects, I just leave it there
to improve)
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
I feel TM would be very long and tedious, so I claimed that no *algorithm* can
solve NPC (algorithmic) problems. (thanks to olcott, this proof was inspired in
refuting POOH.)
See also Spu in my recent post. TM is very low-level to solve many idea
of problems.
To be a computable function within a model of computation
a sequence of the steps of a specific algorithm must be
applied to (an often finite string) input to derive an output.
https://en.wikipedia.org/wiki/Computable_function
When computing the sum() function the steps of the algorithm
of arithmetic must be applied to the inputs.
*When computing the halt() function steps with a simulating*
*termination analyzer the behavioral steps specified by the*
*input must be simulated according to the computer language*
*of this input*
*I may be wrong yet it seems to me that*
Computer science never knew these things before in that
it never placed any limit on the type of algorithm that
must be performed.
I think that it was Ben that said that one of two
functions that do nothing besides return true or false
is correct on all of the counter-example inputs
to the halting problem.
When we require that a mapping be computed from an
input, then this idea is rejected.
You are excellent in quoting tautology to support your claims.
Most people don't know that a mapping must be
computed from the inputs, hence Ben's mistake.
On 5/15/2025 1:49 PM, wij wrote:
On 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?
The TM description language is more accurately
referred to as the TM specification language.
On Thu, 2025-05-15 at 14:15 -0500, olcott wrote:
On 5/15/2025 1:49 PM, wij wrote:
On 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?
The TM description language is more accurately
referred to as the TM specification language.
A UTM is a hypothetical thing that is specified
to have some source source-code that it operates
on yet none of the details of this are ever
fully elaborated.
That is why I needed to use the x86 language
as a fully specified proxy. With my x86utm
operating system we make a 100% concrete
simulating termination analyzer such that
zero of the details are "abstracted away".
It is the details that have been "abstracted away"
by the abstractions that cause the conventional
halting problem proofs to be insufficiently
understood.
Unfortunely, refuting HP suggests halting decider is a real thing.
Proving by "abstracted away" the real part?
[wij's] question "what is the source of such UTM?" seems to be asking
to be pointed to some sample source code for a UTM? I don't have
any! But I'm sure someone somewhere will have gone to all the
trouble of coding an actual UTM, and will have made that available
online somewhere. Note that a UTM is a firstly a TM, but TMs can be described as text "source code" and someone could have made that
available online.
Perhaps someone else here knows of useful sources for this?
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean several things in one post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape would not be defined. Saying "UTM can simulate any TM" is misleading because no such TM (UTM as TM) exists.
On 16/05/2025 01:40, Mike Terry wrote:
[...]
[wij's] question "what is the source of such UTM?" seems to be asking
to be pointed to some sample source code for a UTM? I don't have
any! But I'm sure someone somewhere will have gone to all the
trouble of coding an actual UTM, and will have made that available
online somewhere. Note that a UTM is a firstly a TM, but TMs can be
described as text "source code" and someone could have made that
available online.
Perhaps someone else here knows of useful sources for this?
Minsky's "Computation" has on its front cover [at least in the
Open University edition] and inside, as Fig. 7.2.9 on p142, a complete
UTM as a state-transition diagram. ICBA to count [or to look for more details in the text], but it has ~20 states and uses ~10 symbols. It
would represent perhaps an hour's [routine] work to convert into the
standard quintuples, or a similar amount of work to convert to C. The
text describes fully how an arbitrary TM, expressed as quintuples, and
its input tape, should be represented on the UTM's tape.
On 5/16/2025 2:33 AM, Mikko wrote:
On 2025-05-15 20:50:34 +0000, olcott said:
On 5/15/2025 2:57 PM, wij wrote:
On Thu, 2025-05-15 at 11:47 -0500, olcott wrote:
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
Sort of.
If there was such a UTM then examining things
like a termination analyzer would be too difficult
because of the volume of details. Even moving a
single value to a specific memory location can
take many many steps.
So, which part of POOH is "fully encoded UTM"
A RASP machine
https://en.wikipedia.org/wiki/Random-access_stored-program_machine
is a much better fit for examining the details of any
complex algorithm.
The x86 language is essentially the same thing as a RASP
machine for all computations that can be accomplished
with the amount of memory that is available.
Absolutely false. POOH is the example that rejected TM/RASP instead
of C.
In trying making P!=NP proof (may have defects, I just leave it
there to improve)
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-
en.txt/download
I feel TM would be very long and tedious, so I claimed that no
*algorithm* can
solve NPC (algorithmic) problems. (thanks to olcott, this proof was
inspired in
refuting POOH.)
See also Spu in my recent post. TM is very low-level to solve many
idea of problems.
To be a computable function within a model of computation
a sequence of the steps of a specific algorithm must be
applied to (an often finite string) input to derive an output.
https://en.wikipedia.org/wiki/Computable_function
When computing the sum() function the steps of the algorithm
of arithmetic must be applied to the inputs.
*When computing the halt() function steps with a simulating*
*termination analyzer the behavioral steps specified by the*
*input must be simulated according to the computer language*
*of this input*
*I may be wrong yet it seems to me that*
Computer science never knew these things before in that
it never placed any limit on the type of algorithm that
must be performed.
I think that it was Ben that said that one of two
functions that do nothing besides return true or false
is correct on all of the counter-example inputs
to the halting problem.
When we require that a mapping be computed from an
input, then this idea is rejected.
You are excellent in quoting tautology to support your claims.
Most people don't know that a mapping must be
computed from the inputs, hence Ben's mistake.
Most people don't even know what mappings are. Most people don't
make mistakes just because they don't know what mappings are.
Ben does not make mistakes just because most people don't know
something that Ben does know.
Ben was wrong when he said that there are a
pair of computable functions such that one
of them always gets the correct halt status
decision. IGNORING THE INPUTS IT NOT ALLOWED
On 5/16/2025 2:45 AM, Mikko wrote:You didn't. The input specifies a halting program, but the programmer of
On 2025-05-15 20:08:54 +0000, wij said:
On Thu, 2025-05-15 at 14:15 -0500, olcott wrote:
On 5/15/2025 1:49 PM, wij wrote:
On 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? >>>>>
The TM description language is more accurately
referred to as the TM specification language.
A UTM is a hypothetical thing that is specified
to have some source source-code that it operates
on yet none of the details of this are ever
fully elaborated.
That is why I needed to use the x86 language
as a fully specified proxy. With my x86utm
operating system we make a 100% concrete
simulating termination analyzer such that
zero of the details are "abstracted away".
It is the details that have been "abstracted away"
by the abstractions that cause the conventional
halting problem proofs to be insufficiently
understood.
Unfortunely, refuting HP suggests halting decider is a real thing.
Proving by "abstracted away" the real part?
In which way can a proof that a halting decider does not exist
suggest that a halting decider is a real thing?
The concept of halting decider is a real concept in the same sense
as Arsitotle's concept of unicorn is a real concept but does that
mean that a unicorn and a halting decider are real things?
I have only refuted the standard proof.
A halt decider HHH having a domain of DD and DDD
correctly maps its inputs to the actual behavior
that they actually specify.
     Minsky's "Computation" has on its front cover [at least in the
Open University edition] and inside, as Fig. 7.2.9 on p142, a complete
UTM as a state-transition diagram. [...]
I found it on Amazon, and sure enough there on its front cover is
the state transition diagram! It sounds like a great book, but
realistically I've already got too many books in my reading list...
On 5/16/2025 3:04 PM, Andy Walker wrote:
On 16/05/2025 16:57, Mike Terry wrote:
[I wrote:]
     Minsky's "Computation" has on its front cover [at least in the >>>> Open University edition] and inside, as Fig. 7.2.9 on p142, a complete >>>> UTM as a state-transition diagram. [...]
I found it on Amazon, and sure enough there on its front cover is
the state transition diagram! It sounds like a great book, but
realistically I've already got too many books in my reading list...
     It /is/ a great book. Get* it, and re-order your reading
list to put it first. The only other CS book that I couldn't put
down was the Algol 68 Revised Report.
  * Somewhat on the other hand, I see that it's $silly on Amazon
    and on Abe, so perhaps you should rather borrow it from a
    library. In the UK, it was going to be an Open University
    set book, with therefore guaranteed sales of many thousands,
    But then the OU pulled out, the book was remaindered, and I
    got a brand new copy for £tiny.
This repository contains any material needed to run Marvin Minsky's
Universal Turing Machine in Martin Ugarte's "Turing Machine Simulator"
and to demonstrate its vulnerability as described by Pontus Johnson https://github.com/rozek/Universal-Turing-Machine
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On Thu, 2025-05-15 at 17:08 +0100, Mike Terry wrote:Yes, a UTM can simulate any TM including itself. (Nothing magical changes when a UTM
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? >>>>>>
simulates
itself, as opposed to some other TM.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean several things in one post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM is /equipped/ with an
infinite tape, but the /contents/ of that tape are not a part of that TM's definition.
For example we could build a TM P that decides whether a number is prime. Given a number n, we
convert n into the input tape representation of n, and run P with that tape as input.
It's essentially no different for UTMs. Such a UTM certainly is a "complete TM", equipped with its
own input tape. Of course we don't know what's on the input tape because nobody has said yet what
computation we are asking it to simulate! [Similarly we don't know what's on P's input tape, until
we know what n we want it to test for primeness.] Once you say what computation you want the UTM to
simulate we can build a tape string to perform that particular simulation. That is the case
/whatever/ computation we come up with, so it is simply the case [not misleading] that the UTM can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape is defined (fixed before run).
On 5/16/2025 4:21 PM, wij wrote:
On Fri, 2025-05-16 at 15:38 -0500, olcott wrote:
On 5/16/2025 3:04 PM, Andy Walker wrote:
On 16/05/2025 16:57, Mike Terry wrote:
[I wrote:]
      Minsky's "Computation" has on its front cover [at least in the
Open University edition] and inside, as Fig. 7.2.9 on p142, a
complete
UTM as a state-transition diagram. [...]
I found it on Amazon, and sure enough there on its front cover is
the state transition diagram! It sounds like a great book, but
realistically I've already got too many books in my reading list...
      It /is/ a great book. Get* it, and re-order your reading >>>> list to put it first. The only other CS book that I couldn't put
down was the Algol 68 Revised Report.
   * Somewhat on the other hand, I see that it's $silly on Amazon
     and on Abe, so perhaps you should rather borrow it from a
     library. In the UK, it was going to be an Open University >>>>      set book, with therefore guaranteed sales of many thousands, >>>>      But then the OU pulled out, the book was remaindered, and I >>>>      got a brand new copy for £tiny.
This repository contains any material needed to run Marvin Minsky's
Universal Turing Machine in Martin Ugarte's "Turing Machine Simulator"
and to demonstrate its vulnerability as described by Pontus Johnson
https://github.com/rozek/Universal-Turing-Machine
Thanks for the info. that reminds me of your famous words "read by rote"
Misquote. "Learned by rote" with zero depth of actual understanding.
Not able to do much more than parrot quotes from textbooks.
On 5/16/2025 2:33 AM, Mikko wrote:
On 2025-05-15 20:50:34 +0000, olcott said:
On 5/15/2025 2:57 PM, wij wrote:
On Thu, 2025-05-15 at 11:47 -0500, olcott wrote:
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
Sort of.
If there was such a UTM then examining things
like a termination analyzer would be too difficult
because of the volume of details. Even moving a
single value to a specific memory location can
take many many steps.
So, which part of POOH is "fully encoded UTM"
A RASP machine
https://en.wikipedia.org/wiki/Random-access_stored-program_machine
is a much better fit for examining the details of any
complex algorithm.
The x86 language is essentially the same thing as a RASP
machine for all computations that can be accomplished
with the amount of memory that is available.
Absolutely false. POOH is the example that rejected TM/RASP instead of C. >>>>
In trying making P!=NP proof (may have defects, I just leave it there
to improve)
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-
en.txt/download
I feel TM would be very long and tedious, so I claimed that no *algorithm* can
solve NPC (algorithmic) problems. (thanks to olcott, this proof was inspired in
refuting POOH.)
See also Spu in my recent post. TM is very low-level to solve many idea >>>> of problems.
To be a computable function within a model of computation
a sequence of the steps of a specific algorithm must be
applied to (an often finite string) input to derive an output.
https://en.wikipedia.org/wiki/Computable_function
When computing the sum() function the steps of the algorithm
of arithmetic must be applied to the inputs.
*When computing the halt() function steps with a simulating*
*termination analyzer the behavioral steps specified by the*
*input must be simulated according to the computer language*
*of this input*
*I may be wrong yet it seems to me that*
Computer science never knew these things before in that
it never placed any limit on the type of algorithm that
must be performed.
I think that it was Ben that said that one of two
functions that do nothing besides return true or false
is correct on all of the counter-example inputs
to the halting problem.
When we require that a mapping be computed from an
input, then this idea is rejected.
You are excellent in quoting tautology to support your claims.
Most people don't know that a mapping must be
computed from the inputs, hence Ben's mistake.
Most people don't even know what mappings are. Most people don't
make mistakes just because they don't know what mappings are.
Ben does not make mistakes just because most people don't know
something that Ben does know.
Ben was wrong when he said that there are a
pair of computable functions such that one
of them always gets the correct halt status
decision. IGNORING THE INPUTS IT NOT ALLOWED
On 5/16/2025 2:40 AM, Mikko wrote:
On 2025-05-15 19:15:32 +0000, olcott said:
On 5/15/2025 1:49 PM, wij wrote:
On 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?
The TM description language is more accurately
referred to as the TM specification language.
Not really. The terms "description language" and "specification language"
refer to differenct uses of the languages, not ingerently different
languages. A specification may omit details that a description must
not omit but the choice of such details must a choice of the specifier
and not forced by the language.
The term "specification" typically means all of the relevant details.
The term "description" typically means some of the details.
On 5/16/2025 10:01 PM, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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:What is exactly the source-code on its tape?
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 closestHow does a UTM simulate its own TM source-code?
thing is a UTM that simulates its own TM source-code. >>>>>>>>>>>>>>
You run a UTM that has its own 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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape
contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean
several things in one post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents
of the tape
would not be defined. Saying "UTM can simulate any TM" is
misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"?
A TM is /equipped/ with an
infinite tape, but the /contents/ of that tape are not a part of
that TM's definition.
For example we could build a TM P that decides whether a number is
prime. Given a number n, we
convert n into the input tape representation of n, and run P with
that tape as input.
It's essentially no different for UTMs. Such a UTM certainly is a
"complete TM", equipped with
its
own input tape. Of course we don't know what's on the input tape
because nobody has said yet
what
computation we are asking it to simulate! [Similarly we don't know >>>>> what's on P's input tape,
until
we know what n we want it to test for primeness.]Â Once you say
what computation you want the
UTM to
simulate we can build a tape string to perform that particular
simulation. That is the case
/whatever/ computation we come up with, so it is simply the case
[not misleading] that the UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of
the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be
defined.
I was considering also expressing the idea that undecidable is caused
by 'semantic
self reference'.
Ex1: The truth value of "This sentence is true" is also undecidable.
You have to know what a truth-bearer is to understand
that the Liar Paradox has the same truth value as this
sentence: "What time is it?" I have been working on
that for 22 years too.
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On Thu, 2025-05-15 at 17:08 +0100, Mike Terry wrote:Yes, a UTM can simulate any TM including itself. (Nothing magical changes when a UTM
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:What is exactly the source-code on its tape?
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 closestHow does a UTM simulate its own TM source-code?
thing is a UTM that simulates its own TM source-code. >>>>>>>>>>>>>
You run a UTM that has its own 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? >>>>>>>>
simulates
itself, as opposed to some other TM.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean several things in one post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM is /equipped/ with an
infinite tape, but the /contents/ of that tape are not a part of that TM's definition.
For example we could build a TM P that decides whether a number is prime. Given a number n, we
convert n into the input tape representation of n, and run P with that tape as input.
It's essentially no different for UTMs. Such a UTM certainly is a "complete TM", equipped with
its
own input tape. Of course we don't know what's on the input tape because nobody has said yet
what
computation we are asking it to simulate! [Similarly we don't know what's on P's input tape,
until
we know what n we want it to test for primeness.] Once you say what computation you want the
UTM to
simulate we can build a tape string to perform that particular simulation. That is the case
/whatever/ computation we come up with, so it is simply the case [not misleading] that the UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be defined.
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:Eh? The f was something /you/ introduced! You said it represents some computation which UTM U
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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:What is exactly the source-code on its tape?
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. >>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean several things in one post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM is /equipped/ with
an
infinite tape, but the /contents/ of that tape are not a part of that TM's definition.
For example we could build a TM P that decides whether a number is prime. Given a number n,
we
convert n into the input tape representation of n, and run P with that tape as input.
It's essentially no different for UTMs. Such a UTM certainly is a "complete TM", equipped
with
its
own input tape. Of course we don't know what's on the input tape because nobody has said
yet
what
computation we are asking it to simulate! [Similarly we don't know what's on P's input
tape,
until
we know what n we want it to test for primeness.] Once you say what computation you want
the
UTM to
simulate we can build a tape string to perform that particular simulation. That is the case
/whatever/ computation we come up with, so it is simply the case [not misleading] that the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"? >>>>
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be defined. >>
simulates. How can f suddenly become undefined after you defined it?
Do you mean that f would not be on the input tape for (outer)U? That's not the case at all. In
U(f), the input tape for U contains a representation of f. When (outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of computation U(f), which internally
contains the original representation of f. The f is still there and equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally more careful in your notation!
Using notation <P,I> to mean U's input tape representation of "TM P, running with input I":
Your U(f) is U(<fp,fi>) // fp = TM(f), fi=InputTape(f) >> Your U(U(f)) is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it through step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly attacking that a variable cannot be undefined because it is there. And said I should not gloss over the detail and should think it through step by step.
No idea what you are talking about.
On 5/17/2025 2:46 PM, Mike Terry wrote:
On 17/05/2025 20:26, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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:
What is exactly the source-code on its tape?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. >>>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape >>>>>>>>>>> contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean >>>>>>>>> several things in one post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the
contents of the tape
would not be defined. Saying "UTM can simulate any TM" is
misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be
defined"? A TM is /equipped/ with
an
infinite tape, but the /contents/ of that tape are not a part of >>>>>>>> that TM's definition.
For example we could build a TM P that decides whether a number >>>>>>>> is prime. Given a number n,
we
convert n into the input tape representation of n, and run P
with that tape as input.
It's essentially no different for UTMs. Such a UTM certainly is >>>>>>>> a "complete TM", equipped
with
its
own input tape. Of course we don't know what's on the input
tape because nobody has said
yet
what
computation we are asking it to simulate! [Similarly we don't >>>>>>>> know what's on P's input
tape,
until
we know what n we want it to test for primeness.]Â Once you say >>>>>>>> what computation you want
the
UTM to
simulate we can build a tape string to perform that particular >>>>>>>> simulation. That is the case
/whatever/ computation we come up with, so it is simply the case >>>>>>>> [not misleading] that the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents >>>>>>> of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be
defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be
defined.
Eh? The f was something /you/ introduced! You said it represents
some computation which UTM U
simulates. How can f suddenly become undefined after you defined it? >>>>
Do you mean that f would not be on the input tape for (outer)U?
That's not the case at all. In
U(f), the input tape for U contains a representation of f. When
(outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of
computation U(f), which internally
contains the original representation of f. The f is still there and
equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally
more careful in your notation!
Using notation <P,I> to mean U's input tape representation of "TM P,
running with input I":
    Your U(f)     is U(<fp,fi>)       // fp = TM(f), fi=InputTape(f)
    Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it
through step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly
attacking
that a variable cannot be undefined because it is there. And said I
should
not gloss over the detail and should think it through step by step.
No idea what you are talking about.
Ok we definitely have a two way communication problem! :)
I'll just let you get on with things then... Good luck questing your
UTM. Hopefully you can find out what is source of it, and locate your
undefined tape contents, including the f bit!
Mike.
That is the problem with imaginary abstractions.
No one can look at the imaginary tape and see that
it is empty.
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:Eh? The f was something /you/ introduced! You said it represents some >>> computation which UTM U
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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:What is exactly the source-code on its tape?
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. >>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean several >>>>>>>> things in one post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM
is /equipped/ with
an
infinite tape, but the /contents/ of that tape are not a part of that >>>>>>> TM's definition.
For example we could build a TM P that decides whether a number is >>>>>>> prime. Given a number n,
we
convert n into the input tape representation of n, and run P with that >>>>>>> tape as input.
It's essentially no different for UTMs. Such a UTM certainly is a >>>>>>> "complete TM", equipped
with
its
own input tape. Of course we don't know what's on the input tape >>>>>>> because nobody has said
yet
what
computation we are asking it to simulate! [Similarly we don't know >>>>>>> what's on P's input
tape,
until
we know what n we want it to test for primeness.]Â Once you say what >>>>>>> computation you want
the
UTM to
simulate we can build a tape string to perform that particular
simulation. That is the case
/whatever/ computation we come up with, so it is simply the case [not >>>>>>> misleading] that the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"? >>>>>
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be defined. >>>
simulates. How can f suddenly become undefined after you defined it?
Do you mean that f would not be on the input tape for (outer)U? That's >>> not the case at all. In
U(f), the input tape for U contains a representation of f. When
(outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of computation
U(f), which internally
contains the original representation of f. The f is still there and
equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally more
careful in your notation!
Using notation <P,I> to mean U's input tape representation of "TM P,
running with input I":
   Your U(f)     is U(<fp,fi>) // fp = TM(f), fi=InputTape(f)
   Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it through
step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly attacking >> that a variable cannot be undefined because it is there. And said I should >> not gloss over the detail and should think it through step by step.
No idea what you are talking about.
U(<U>) is the most conventional notation
for U simulating its own source-code.
TM description is a misnomer in that they never
merely describe some of the details of the TM
(as all mere descriptions always do).
Instead they specify ALL of the details, thus have
always actually been a TM specification language more
commonly understood as the source-code for a TM.
On 5/18/2025 3:35 PM, wij wrote:
On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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:
What is exactly the source-code on its tape?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. >>>>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape >>>>>>>>>>>> contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean >>>>>>>>>> several things in one
post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the
contents of the tape
would not be defined. Saying "UTM can simulate any TM" is
misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be
defined"? A TM is /equipped/
with
an
infinite tape, but the /contents/ of that tape are not a part >>>>>>>>> of that TM's definition.
For example we could build a TM P that decides whether a number >>>>>>>>> is prime. Given a
number n,
we
convert n into the input tape representation of n, and run P >>>>>>>>> with that tape as input.
It's essentially no different for UTMs. Such a UTM certainly >>>>>>>>> is a "complete TM",
equipped
with
its
own input tape. Of course we don't know what's on the input >>>>>>>>> tape because nobody has
said
yet
what
computation we are asking it to simulate! [Similarly we don't >>>>>>>>> know what's on P's input
tape,
until
we know what n we want it to test for primeness.]Â Once you say >>>>>>>>> what computation you
want
the
UTM to
simulate we can build a tape string to perform that particular >>>>>>>>> simulation. That is the
case
/whatever/ computation we come up with, so it is simply the
case [not misleading] that
the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents >>>>>>>> of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be
defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be
defined.
Eh? The f was something /you/ introduced! You said it represents >>>>> some computation which UTM U
simulates. How can f suddenly become undefined after you defined it? >>>>>
Do you mean that f would not be on the input tape for (outer)U?
That's not the case at all. In
U(f), the input tape for U contains a representation of f. When
(outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of
computation U(f), which internally
contains the original representation of f. The f is still there
and equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally
more careful in your notation!
Using notation <P,I> to mean U's input tape representation of "TM
P, running with input I":
     Your U(f)     is U(<fp,fi>)       // fp = TM(f), >>>>> fi=InputTape(f)
     Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it
through step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly
attacking
that a variable cannot be undefined because it is there. And said I
should
not gloss over the detail and should think it through step by step.
No idea what you are talking about.
U(<U>)Â Â Â is the most conventional notation
U is not a complete TM. U(<U>) is worst, also not a TM.
It is stipulated that U is a UTM that
has its own source-code as its input.
TM description is a misnomer in that they never
merely describe some of the details of the TM
(as all mere descriptions always do).
Instead they specify ALL of the details, thus have
always actually been a TM specification language more
commonly understood as the source-code for a TM.
On 5/18/2025 4:58 PM, André G. Isaak wrote:
On 2025-05-18 14:57, olcott wrote:
TM description is a misnomer in that they never
merely describe some of the details of the TM
(as all mere descriptions always do).
Instead they specify ALL of the details, thus have
always actually been a TM specification language more
commonly understood as the source-code for a TM.
You seem to be getting bogged down in a relatively inconsequential
terminological issue here which contributes nothing to the overall
debate.
It is not inconsequential. It is the misnomer that an
input is merely described that enables people to believe
that DDD simulated by HHH must have the same behavior
as DDD simulated by HHH1 even when they SPECIFY different
behavior.
In English, both 'description' and 'specification' can refer to
something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
When people talk about passing a UTM a description of a TM, it is
understood that this refers to a *complete* description rather than a
partial one.
If this was true then they would understand that
the input to HHH(DDD) specifies behavior that is
not the same behavior as DDD().
_DDD()
[00002172] 55        push ebp     ; housekeeping
[00002173] 8bec      mov ebp,esp  ; housekeeping
[00002175] 6872210000 push 00002172 ; push DDD
[0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
[0000217f] 83c404Â Â Â Â add esp,+04
[00002182] 5d        pop ebp
[00002183] c3Â Â Â Â Â Â Â Â ret
Size in bytes:(0018) [00002183]
They would understand that no matter how many
instructions of DDD are emulated by HHH according
to the rules of the x86 language that this
correctly emulated DDD cannot possibly halt.
If you prefer the term 'specification', you're free to use it, but
there's no sense in which 'description' is a misnomer.
André
On 5/18/2025 4:46 PM, wij wrote:
On Sun, 2025-05-18 at 15:57 -0500, olcott wrote:
On 5/18/2025 3:35 PM, wij wrote:
On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote: >>>>>>>>>>>>>>> On 15/05/2025 19:49, wij wrote:There is no self-reference trap.
On 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:
What is exactly the source-code on its tape? >>>>>>>>>>>>>>>>>>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. >>>>>>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the >>>>>>>>>>>>>> tape contents of the
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.
Sorry for not being clear on the UTM issue (I wanted to mean >>>>>>>>>>>> several things in one
post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the >>>>>>>>>>>> contents of the tape
would not be defined. Saying "UTM can simulate any TM" is >>>>>>>>>>>> misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be
defined"? A TM is
/equipped/
with
an
infinite tape, but the /contents/ of that tape are not a part >>>>>>>>>>> of that TM's
definition.
For example we could build a TM P that decides whether a >>>>>>>>>>> number is prime. Given a
number n,
we
convert n into the input tape representation of n, and run P >>>>>>>>>>> with that tape as
input.
It's essentially no different for UTMs. Such a UTM certainly >>>>>>>>>>> is a "complete TM",
equipped
with
its
own input tape. Of course we don't know what's on the input >>>>>>>>>>> tape because nobody has
said
yet
what
computation we are asking it to simulate! [Similarly we >>>>>>>>>>> don't know what's on P's
input
tape,
until
we know what n we want it to test for primeness.]Â Once you >>>>>>>>>>> say what computation you
want
the
UTM to
simulate we can build a tape string to perform that
particular simulation. That is
the
case
/whatever/ computation we come up with, so it is simply the >>>>>>>>>>> case [not misleading]
that
the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the
contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be >>>>>>>>> defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not >>>>>>>> be defined.
Eh? The f was something /you/ introduced! You said it
represents some computation which
UTM U
simulates. How can f suddenly become undefined after you defined >>>>>>> it?
Do you mean that f would not be on the input tape for (outer)U?
That's not the case at
all. In
U(f), the input tape for U contains a representation of f. When >>>>>>> (outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of
computation U(f), which
internally
contains the original representation of f. The f is still there >>>>>>> and equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally >>>>>>> more careful in your
notation!
Using notation <P,I> to mean U's input tape representation of "TM >>>>>>> P, running with input I":
      Your U(f)     is U(<fp,fi>)       // fp = TM(f),
fi=InputTape(f)
      Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it
through step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly
attacking
that a variable cannot be undefined because it is there. And said
I should
not gloss over the detail and should think it through step by step. >>>>>> No idea what you are talking about.
U(<U>)Â Â Â is the most conventional notation
U is not a complete TM. U(<U>) is worst, also not a TM.
It is stipulated that U is a UTM that
has its own source-code as its input.
UTM is not a complete TM.
Textbooks define a UTM as a complete TM.
On 5/18/2025 4:58 PM, André G. Isaak wrote:
In English, both 'description' and 'specification' can refer to
something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
On 5/18/2025 10:21 PM, André G. Isaak wrote:
On 2025-05-18 16:08, olcott wrote:
On 5/18/2025 4:58 PM, André G. Isaak wrote:
In English, both 'description' and 'specification' can refer to
something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
I don't think you'll find that most people will agree with this. That
might be your usage.
The problem is that 'specification' has already been used in much of
this discussion to mean something else. A TM's specification outlines
what it is that that TM is supposed to do without going into the
details of how it actually does it.
When you refer to the spec of an algorithm you
are correct. When you refer to the every single
step of the exact behavior that a finite string
specified you are wrong.
For example, the specification of a Parity Decider would be a TM takes
a representation of a natural number as its initial tape content and
accepts it only if it is even.
The description of that machine, on the other hand, would describe
what the alphabet of this machine is, what it's state transitions are,
etc. i.e. it would give all the information necessary to actually
construct the machine.
André
I already know how TM machine descriptions actually work.
DDD simulated by HHH1 has the exact same
sequence of steps as the directly executed DDD().
People here think that when DDD is simulated by
the same simulator that it calls (thus causing
recursive simulation) that DDD must have the same
behavior as DDD simulated by HHH1 that DDD does
not call.
_DDD()
[00002172] 55        push ebp     ; housekeeping
[00002173] 8bec      mov ebp,esp  ; housekeeping
[00002175] 6872210000 push 00002172 ; push DDD
[0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
[0000217f] 83c404Â Â Â Â add esp,+04
[00002182] 5d        pop ebp
[00002183] c3Â Â Â Â Â Â Â Â ret
Size in bytes:(0018) [00002183]
There is no way that DDD simulated by any HHH can
possibly reach its "ret" instruction and halt. People
have consistently ignored this basic fact for 2.5 years.
On 5/16/2025 2:27 AM, Mikko wrote:
On 2025-05-15 16:47:49 +0000, olcott said:
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
Investigations do not need a standard language. For an investigation an
ad hoc language is good enough and usually better.
Until I made this concrete people kept assuming that
an input DD could be defined that actually does the
opposite of whatever value that its simulating termination
analyzer HHH returns.
int main()
{
 DD(); // HHH cannot report on the behavior of its caller.
}
On 5/16/2025 2:27 AM, Mikko wrote:
On 2025-05-15 16:47:49 +0000, olcott said:
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
Investigations do not need a standard language. For an investigation an
ad hoc language is good enough and usually better.
Until I made this concrete people kept assuming that
an input DD could be defined that actually does the
opposite of whatever value that its simulating termination
analyzer HHH returns.
On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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:
What is exactly the source-code on its tape?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. >>>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean several >>>>>>>>> things in one
post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM
is /equipped/
with
an
infinite tape, but the /contents/ of that tape are not a part of that >>>>>>>> TM's definition.
For example we could build a TM P that decides whether a number is >>>>>>>> prime. Given a
number n,
we
convert n into the input tape representation of n, and run P with that >>>>>>>> tape as input.
It's essentially no different for UTMs. Such a UTM certainly is a >>>>>>>> "complete TM",
equipped
with
its
own input tape. Of course we don't know what's on the input tape >>>>>>>> because nobody has
said
yet
what
computation we are asking it to simulate! [Similarly we don't know >>>>>>>> what's on P's input
tape,
until
we know what n we want it to test for primeness.]Â Once you say what >>>>>>>> computation you
want
the
UTM to
simulate we can build a tape string to perform that particular >>>>>>>> simulation. That is the
case
/whatever/ computation we come up with, so it is simply the case [not >>>>>>>> misleading] that
the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"? >>>>>>
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be defined.
Eh? The f was something /you/ introduced! You said it represents some >>>> computation which UTM U
simulates. How can f suddenly become undefined after you defined it? >>>>
Do you mean that f would not be on the input tape for (outer)U? That's >>>> not the case at all. In
U(f), the input tape for U contains a representation of f. When
(outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of computation >>>> U(f), which internally
contains the original representation of f. The f is still there and
equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally more
careful in your notation!
Using notation <P,I> to mean U's input tape representation of "TM P,
running with input I":
    Your U(f)     is U(<fp,fi>) // fp = TM(f), fi=InputTape(f)
    Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it through >>>> step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly attacking >>> that a variable cannot be undefined because it is there. And said I should >>> not gloss over the detail and should think it through step by step.
No idea what you are talking about.
U(<U>) is the most conventional notation
U is not a complete TM. U(<U>) is worst, also not a TM.
On 5/18/2025 3:35 PM, wij wrote:
On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:
On 15/05/2025 19:49, wij wrote:
On 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:
What is exactly the source-code on its tape?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. >>>>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
There is no 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.
Sorry for not being clear on the UTM issue (I wanted to mean several >>>>>>>>>> things in one
post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM
is /equipped/
with
an
infinite tape, but the /contents/ of that tape are not a part of that >>>>>>>>> TM's definition.
For example we could build a TM P that decides whether a number is >>>>>>>>> prime. Given a
number n,
we
convert n into the input tape representation of n, and run P with that
tape as input.
It's essentially no different for UTMs. Such a UTM certainly is a >>>>>>>>> "complete TM",
equipped
with
its
own input tape. Of course we don't know what's on the input tape >>>>>>>>> because nobody has
said
yet
what
computation we are asking it to simulate! [Similarly we don't know >>>>>>>>> what's on P's input
tape,
until
we know what n we want it to test for primeness.]Â Once you say what >>>>>>>>> computation you
want
the
UTM to
simulate we can build a tape string to perform that particular >>>>>>>>> simulation. That is the
case
/whatever/ computation we come up with, so it is simply the case [not >>>>>>>>> misleading] that
the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"? >>>>>>>
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be defined.
Eh? The f was something /you/ introduced! You said it represents some >>>>> computation which UTM U
simulates. How can f suddenly become undefined after you defined it? >>>>>
Do you mean that f would not be on the input tape for (outer)U? That's >>>>> not the case at all. In
U(f), the input tape for U contains a representation of f. When
(outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of computation >>>>> U(f), which internally
contains the original representation of f. The f is still there and >>>>> equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally more >>>>> careful in your notation!
Using notation <P,I> to mean U's input tape representation of "TM P, >>>>> running with input I":
    Your U(f)     is U(<fp,fi>) // fp = TM(f), fi=InputTape(f)
    Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it through >>>>> step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly attacking
that a variable cannot be undefined because it is there. And said I should >>>> not gloss over the detail and should think it through step by step.
No idea what you are talking about.
U(<U>) is the most conventional notation
U is not a complete TM. U(<U>) is worst, also not a TM.
It is stipulated that U is a UTM that
has its own source-code as its input.
On 5/18/2025 4:46 PM, wij wrote:
On Sun, 2025-05-18 at 15:57 -0500, olcott wrote:
On 5/18/2025 3:35 PM, wij wrote:
On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:
On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote: >>>>>>>>>>>>>>> On 15/05/2025 19:49, wij wrote:There is no self-reference trap.
On 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:
What is exactly the source-code on its tape? >>>>>>>>>>>>>>>>>>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. >>>>>>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
Sorry for not being clear on the UTM issue (I wanted to mean several
things in one
post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM is
/equipped/
with
an
infinite tape, but the /contents/ of that tape are not a part of that TM's
definition.
For example we could build a TM P that decides whether a number is >>>>>>>>>>> prime. Given a
number n,
we
convert n into the input tape representation of n, and run P with that tape as
input.
It's essentially no different for UTMs. Such a UTM certainly is a >>>>>>>>>>> "complete TM",
equipped
with
its
own input tape. Of course we don't know what's on the input tape >>>>>>>>>>> because nobody has
said
yet
what
computation we are asking it to simulate! [Similarly we don't know
what's on P's
input
tape,
until
we know what n we want it to test for primeness.]Â Once you say what
computation you
want
the
UTM to
simulate we can build a tape string to perform that particular >>>>>>>>>>> simulation. That is
the
case
/whatever/ computation we come up with, so it is simply the case [not
misleading]
that
the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be defined.
Eh? The f was something /you/ introduced! You said it represents some
computation which
UTM U
simulates. How can f suddenly become undefined after you defined it? >>>>>>>
Do you mean that f would not be on the input tape for (outer)U? That's
not the case at
all. In
U(f), the input tape for U contains a representation of f. When >>>>>>> (outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of computation >>>>>>> U(f), which
internally
contains the original representation of f. The f is still there and >>>>>>> equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally more >>>>>>> careful in your
notation!
Using notation <P,I> to mean U's input tape representation of "TM P, >>>>>>> running with input I":
     Your U(f)     is U(<fp,fi>) // fp = TM(f), fi=InputTape(f)
     Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it through >>>>>>> step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly attacking
that a variable cannot be undefined because it is there. And said I should
not gloss over the detail and should think it through step by step. >>>>>> No idea what you are talking about.
U(<U>) is the most conventional notation
U is not a complete TM. U(<U>) is worst, also not a TM.
It is stipulated that U is a UTM that
has its own source-code as its input.
UTM is not a complete TM.
Textbooks define a UTM as a complete TM.
On Sun, 2025-05-18 at 19:09 -0400, Richard Damon wrote:
On 5/18/25 6:09 PM, olcott wrote:
On 5/18/2025 4:46 PM, wij wrote:
On Sun, 2025-05-18 at 15:57 -0500, olcott wrote:
On 5/18/2025 3:35 PM, wij wrote:
On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote: >>>>>>>>>>>>>>> On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote: >>>>>>>>>>>>>>>>> On 15/05/2025 19:49, wij wrote:There is no self-reference trap.
On 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:
What is exactly the source-code on its tape? >>>>>>>>>>>>>>>>>>>>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> > > > > > > > > > >
itself):(which >>>>>>>>>>>>>>>>>>>>>>>> calls
void D() {
           D();
}
Easy?
That is not a TM.
It is a C program that exists. Therefore, there must> > > > > > > > > >
equivalentbe a
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. >>>>>>>>>>>>>>>>>>>>
Every UTM has some scheme which can be applied to a (TM> > > > > > > >
that& input tape)
is to
be
simulated.
The
scheme says how to turn the (TM + input tape) into a> > > > > > > > > >
thatstring of symbols
represent
that
computation.
So to answer your question, the "source-code on its> > > > > > > > > >
oftape" is the result
applying
the
UTM's
particular scheme to the combination (UTM, input tape)> > > > > > > > >
simulated.that is to be
If you're looking for the exact string symbols,> > > > > > > > > > > >
toobviously you would need
specify
the
exact
UTM
being used, because every UTM will have a different> > > > > > > > > >
question.answer to your
Mike.
People used to say UTM can simulate all TM. I was> > > > > > > > > > >
Because you said "Every UTM ...", so what is the source> > > > > > > >questing such a UTM.
of such UTM?
Yes, a UTM can simulate any TM including itself. > > > > > > > > > > >
when(Nothing magical changes
a
UTM
simulates
itself, as opposed to some other TM.)
Supposed UTM exists, and denoted as U(X), X denotes the> > > > > > > >
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> > > > > > >tape contents of the
But, U(U(f)) would fall into a 'self-reference' trap. >>>>>>>>>>>>>>>above definition.
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> > > > > > >
         but having the same behaviour. >>>>>>>>>>>>>>> - U(U(f)) represents U simulating the previous computation. >>>>>>>>>>>>>>>f of course
There is no reason U(f) cannot be simulated by U. U will> > > > > > >
ithave no knowledge that
is
"simulating
itself", and will just simulate what it is given. >>>>>>>>>>>>>>>
Mike.
Sorry for not being clear on the UTM issue (I wanted to mean> > > > > >
post).several things in one
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the> > > > > > > >
would not be defined. Saying "UTM can simulate any TM" is> > > > > > >contents of the tape
no such TM (UTM as TM) exists.misleading because
What do you mean "the contents of the tape would not be> > > > > > > >
/equipped/defined"? A TM is
with
an
infinite tape, but the /contents/ of that tape are not a part> > > > >
definition.of that TM's
For example we could build a TM P that decides whether a> > > > > > > >
number n,number is prime. Given a
we
convert n into the input tape representation of n, and run P> > > > > >
input.with that tape as
It's essentially no different for UTMs. Such a UTM certainly> > > > >
equippedis a "complete TM",
with
its
own input tape. Of course we don't know what's on the input> > > > > >
saidtape because nobody has
yet
what
computation we are asking it to simulate! [Similarly we> > > > > > > >
inputdon't know what's on P's
tape,
until
we know what n we want it to test for primeness.]Â Once you> > > > > >
wantsay what computation you
the
UTM to
simulate we can build a tape string to perform that> > > > > > > > > >
theparticular simulation. That is
case
/whatever/ computation we come up with, so it is simply the> > > > > >
thatcase [not misleading]
the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the> > > > > > > >
is defined (fixed before run).contents of the tape
Correct, and correct.
So... What do you mean "the contents of the tape would not be> > > > >
defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not> > > > >
be defined.
Eh? The f was something /you/ introduced! You said it> > > > > > > >
represents some computation which
UTM U
simulates. How can f suddenly become undefined after you defined> > >
it?
Do you mean that f would not be on the input tape for (outer)U? > > > >
all. InThat's not the case at
U(f), the input tape for U contains a representation of f. When> > > >
simulating f, (outer)U's tape contains a representation of> > > > > > >(outer)U simulates (inner)U
computation U(f), whichinternally
contains the original representation of f. The f is still there> > > >
U(U(f)).and equally well defined in
I think you would benefit from being more explicit and generally> > > >
notation!more careful in your
Using notation <P,I> to mean U's input tape representation of "TM> > >
P, running with input I":
      Your U(f)     is U(<fp,fi>)       // fp = TM(f),> > > > > > >
fi=InputTape(f)Â Â Â Â Â Â Your U(U(f))Â Â is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it> > > > >
through step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly> > > >>>>>>>> > > > > attacking
that a variable cannot be undefined because it is there. And said> > > >>>>>>>> > > > > I should
not gloss over the detail and should think it through step by step. >>>>>>>> No idea what you are talking about.
U(<U>)Â Â Â is the most conventional notation
U is not a complete TM. U(<U>) is worst, also not a TM.
It is stipulated that U is a UTM that
has its own source-code as its input.
UTM is not a complete TM.> >> > Textbooks define a UTM as a complete TM. >>>
As I pointed out, there are two definitions of what a Turing Macine is.
It can be just the algorithm part, or the combination of the Algorithm>
and Input.
In either case
"U <U>" isn't a valid computation, as in the TM is just tha algoritm>
case, where <U> is a valid string for the representation of the TM, a>
UTM needs as its input the combination of the representation of the>
input program and the representation of its input (if it takes any),
since the program is a UTM, and that needs an input, you need toadd it.
Note that TM cannot *read* input as external information, everything is fixed.
I have no problem with the 'two definition' saying, you just have to make it clear (but as usual in your real number, you invent your own stuff, you are not following your 'standard' and condemn others not following it). However this 'other' definition of TM if exists will have no computation (nothing in the tape). You cannot talk about 'computation'.
On 5/18/2025 10:21 PM, André G. Isaak wrote:
On 2025-05-18 16:08, olcott wrote:
On 5/18/2025 4:58 PM, André G. Isaak wrote:
In English, both 'description' and 'specification' can refer to
something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
I don't think you'll find that most people will agree with this. That
might be your usage.
The problem is that 'specification' has already been used in much of
this discussion to mean something else. A TM's specification outlines
what it is that that TM is supposed to do without going into the
details of how it actually does it.
When you refer to the spec of an algorithm you
are correct. When you refer to the every single
step of the exact behavior that a finite string
specified you are wrong.
For example, the specification of a Parity Decider would be a TM takes
a representation of a natural number as its initial tape content and
accepts it only if it is even.
The description of that machine, on the other hand, would describe what
the alphabet of this machine is, what it's state transitions are, etc.
i.e. it would give all the information necessary to actually construct
the machine.
André
I already know how TM machine descriptions actually work.
DDD simulated by HHH1 has the exact same
sequence of steps as the directly executed DDD().
People here think that when DDD is simulated by
the same simulator that it calls (thus causing
recursive simulation) that DDD must have the same
behavior as DDD simulated by HHH1 that DDD does
not call.
On 5/19/2025 5:48 AM, Mikko wrote:
On 2025-05-18 22:09:47 +0000, olcott said:
On 5/18/2025 4:46 PM, wij wrote:
On Sun, 2025-05-18 at 15:57 -0500, olcott wrote:
On 5/18/2025 3:35 PM, wij wrote:
On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
On 5/17/2025 2:26 PM, wij wrote:
On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
On 17/05/2025 04:01, wij wrote:
On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
On 16/05/2025 20:35, wij wrote:
On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
On 16/05/2025 12:40, wij wrote:
On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote: >>>>>>>>>>>>>>> On 16/05/2025 02:47, wij wrote:
On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote: >>>>>>>>>>>>>>>>> On 15/05/2025 19:49, wij wrote:There is no self-reference trap.
On 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:
What is exactly the source-code on its tape? >>>>>>>>>>>>>>>>>>>>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. >>>>>>>>>>>>>>>>>>>>
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.)
Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
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.
Sorry for not being clear on the UTM issue (I wanted to mean several
things in one
post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the contents of the tape
would not be defined. Saying "UTM can simulate any TM" is misleading because
no such TM (UTM as TM) exists.
What do you mean "the contents of the tape would not be defined"? A TM is
/equipped/
with
an
infinite tape, but the /contents/ of that tape are not a part of that TM's
definition.
For example we could build a TM P that decides whether a number is
prime. Given a
number n,
we
convert n into the input tape representation of n, and run P with that tape as
input.
It's essentially no different for UTMs. Such a UTM certainly is a
"complete TM",
equipped
with
its
own input tape. Of course we don't know what's on the input tape
because nobody has
said
yet
what
computation we are asking it to simulate! [Similarly we don't know
what's on P's
input
tape,
until
we know what n we want it to test for primeness.]Â Once you say what
computation you
want
the
UTM to
simulate we can build a tape string to perform that particular >>>>>>>>>>>>> simulation. That is
the
case
/whatever/ computation we come up with, so it is simply the case [not
misleading]
that
the
UTM
can
simulate any computation.
Mike.
TM has no I/O mechanism. 'Computation' always means the contents of the tape
is defined (fixed before run).
Correct, and correct.
So... What do you mean "the contents of the tape would not be defined"?
Mike.
In "UTM simulates itself", denoted as U(U(f)), the f would not be defined.
Eh? The f was something /you/ introduced! You said it represents some
computation which
UTM U
simulates. How can f suddenly become undefined after you defined it?
Do you mean that f would not be on the input tape for (outer)U? That's
not the case at
all. In
U(f), the input tape for U contains a representation of f. When >>>>>>>>> (outer)U simulates (inner)U
simulating f, (outer)U's tape contains a representation of computation
U(f), which
internally
contains the original representation of f. The f is still there and >>>>>>>>> equally well defined in
U(U(f)).
I think you would benefit from being more explicit and generally more >>>>>>>>> careful in your
notation!
Using notation <P,I> to mean U's input tape representation of "TM P, >>>>>>>>> running with input I":
     Your U(f)     is U(<fp,fi>)       // fp = TM(f), fi=InputTape(f)
     Your U(U(f))  is U((<U,<fp,fi>>)
f is still there! It has not become "undefined".
You gloss over the details and become confused - just think it through
step by step.
Mike.
It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly attacking
that a variable cannot be undefined because it is there. And said I should
not gloss over the detail and should think it through step by step. >>>>>>>> No idea what you are talking about.
U(<U>)Â Â Â is the most conventional notation
U is not a complete TM. U(<U>) is worst, also not a TM.
It is stipulated that U is a UTM that
has its own source-code as its input.
UTM is not a complete TM.
Textbooks define a UTM as a complete TM.
And published UTM's are. No repspectable pulblisher would accept
anything less.
They did accept much less in the early days.
It took a lot of years before a UTM was not
a pure abstraction.
On 5/19/2025 7:29 AM, Mikko wrote:
On 2025-05-19 04:07:11 +0000, olcott said:
On 5/18/2025 10:21 PM, André G. Isaak wrote:
On 2025-05-18 16:08, olcott wrote:
On 5/18/2025 4:58 PM, André G. Isaak wrote:
In English, both 'description' and 'specification' can refer to
something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
I don't think you'll find that most people will agree with this. That
might be your usage.
The problem is that 'specification' has already been used in much of
this discussion to mean something else. A TM's specification outlines
what it is that that TM is supposed to do without going into the
details of how it actually does it.
When you refer to the spec of an algorithm you
are correct. When you refer to the every single
step of the exact behavior that a finite string
specified you are wrong.
For example, the specification of a Parity Decider would be a TM takes >>>> a representation of a natural number as its initial tape content and
accepts it only if it is even.
The description of that machine, on the other hand, would describe what >>>> the alphabet of this machine is, what it's state transitions are, etc. >>>> i.e. it would give all the information necessary to actually construct >>>> the machine.
André
I already know how TM machine descriptions actually work.
DDD simulated by HHH1 has the exact same
sequence of steps as the directly executed DDD().
People here think that when DDD is simulated by
the same simulator that it calls (thus causing
recursive simulation) that DDD must have the same
behavior as DDD simulated by HHH1 that DDD does
not call.
The behaviour of DDD is the behaviour that DDD specifies. If some
program simulaates differently then it does not simulate the
behaviour of DDD.
It's not that hard really.
When an input calls its own simulator with itself as input
THIS DOES CHANGE ITS BEHAVIOR.
On 5/19/2025 5:39 AM, Mikko wrote:
On 2025-05-16 15:40:29 +0000, olcott said:
On 5/16/2025 2:27 AM, Mikko wrote:
On 2025-05-15 16:47:49 +0000, olcott said:
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
Investigations do not need a standard language. For an investigation an >>>> ad hoc language is good enough and usually better.
Until I made this concrete people kept assuming that
an input DD could be defined that actually does the
opposite of whatever value that its simulating termination
analyzer HHH returns.
That need not and should not be assumed. That can be constructively
proven.
Which doesn't matter to any investigation.
There are only two ways to try to define a DD
that actually does the opposition of whatever
value that is termination analyzer returns.
These things cannot be investigated in greatand to my response to that claim.
depth because there is no fully encoded UTM in
any standard language.
On 5/19/2025 5:39 AM, Mikko wrote:
On 2025-05-16 15:40:29 +0000, olcott said:
On 5/16/2025 2:27 AM, Mikko wrote:
On 2025-05-15 16:47:49 +0000, olcott said:
On 5/15/2025 11:08 AM, 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.
These things cannot be investigated in great
depth because there is no fully encoded UTM in
any standard language.
Investigations do not need a standard language. For an investigation an >>>> ad hoc language is good enough and usually better.
Until I made this concrete people kept assuming that
an input DD could be defined that actually does the
opposite of whatever value that its simulating termination
analyzer HHH returns.
That need not and should not be assumed. That can be constructively
proven.
Which doesn't matter to any investigation.
There are only two ways to try to define a DD
that actually does the opposition of whatever
value that is termination analyzer returns.
Neither of the work.
int main()
{
 DDD() // HHH called from DDD can know nothing of it caller.
}
On 5/19/2025 7:29 AM, Mikko wrote:
On 2025-05-19 04:07:11 +0000, olcott said:
On 5/18/2025 10:21 PM, André G. Isaak wrote:
On 2025-05-18 16:08, olcott wrote:
On 5/18/2025 4:58 PM, André G. Isaak wrote:
In English, both 'description' and 'specification' can refer to
something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
I don't think you'll find that most people will agree with this.
That might be your usage.
The problem is that 'specification' has already been used in much of
this discussion to mean something else. A TM's specification
outlines what it is that that TM is supposed to do without going
into the details of how it actually does it.
When you refer to the spec of an algorithm you
are correct. When you refer to the every single
step of the exact behavior that a finite string
specified you are wrong.
For example, the specification of a Parity Decider would be a TM
takes a representation of a natural number as its initial tape
content and accepts it only if it is even.
The description of that machine, on the other hand, would describe
what the alphabet of this machine is, what it's state transitions
are, etc. i.e. it would give all the information necessary to
actually construct the machine.
André
I already know how TM machine descriptions actually work.
DDD simulated by HHH1 has the exact same
sequence of steps as the directly executed DDD().
People here think that when DDD is simulated by
the same simulator that it calls (thus causing
recursive simulation) that DDD must have the same
behavior as DDD simulated by HHH1 that DDD does
not call.
The behaviour of DDD is the behaviour that DDD specifies. If some
program simulaates differently then it does not simulate the
behaviour of DDD.
It's not that hard really.
When an input calls its own simulator with itself as input
THIS DOES CHANGE ITS BEHAVIOR.
On 5/19/2025 7:29 AM, Mikko wrote:
On 2025-05-19 04:07:11 +0000, olcott said:
On 5/18/2025 10:21 PM, André G. Isaak wrote:
On 2025-05-18 16:08, olcott wrote:
On 5/18/2025 4:58 PM, André G. Isaak wrote:
In English, both 'description' and 'specification' can refer to
something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
I don't think you'll find that most people will agree with this.
That might be your usage.
The problem is that 'specification' has already been used in much of
this discussion to mean something else. A TM's specification
outlines what it is that that TM is supposed to do without going
into the details of how it actually does it.
When you refer to the spec of an algorithm you
are correct. When you refer to the every single
step of the exact behavior that a finite string
specified you are wrong.
For example, the specification of a Parity Decider would be a TM
takes a representation of a natural number as its initial tape
content and accepts it only if it is even.
The description of that machine, on the other hand, would describe
what the alphabet of this machine is, what it's state transitions
are, etc. i.e. it would give all the information necessary to
actually construct the machine.
André
I already know how TM machine descriptions actually work.
DDD simulated by HHH1 has the exact same
sequence of steps as the directly executed DDD().
People here think that when DDD is simulated by
the same simulator that it calls (thus causing
recursive simulation) that DDD must have the same
behavior as DDD simulated by HHH1 that DDD does
not call.
The behaviour of DDD is the behaviour that DDD specifies. If some
program simulaates differently then it does not simulate the
behaviour of DDD.
It's not that hard really.
When an input calls its own simulator with itself as input
THIS DOES CHANGE ITS BEHAVIOR.
On 5/21/2025 2:43 PM, Fred. Zwarts wrote:That is your usual reply when you don't understand the rebuttal. You
Op 21.mei.2025 om 06:33 schreef olcott:
On 5/19/2025 7:29 AM, Mikko wrote:
On 2025-05-19 04:07:11 +0000, olcott said:
On 5/18/2025 10:21 PM, André G. Isaak wrote:
On 2025-05-18 16:08, olcott wrote:
On 5/18/2025 4:58 PM, André G. Isaak wrote:
In English, both 'description' and 'specification' can refer to >>>>>>>> something which is either complete or only partial.
Description typically means partial and
specification typically means complete.
I don't think you'll find that most people will agree with this.
That might be your usage.
The problem is that 'specification' has already been used in much
of this discussion to mean something else. A TM's specification
outlines what it is that that TM is supposed to do without going
into the details of how it actually does it.
When you refer to the spec of an algorithm you
are correct. When you refer to the every single
step of the exact behavior that a finite string
specified you are wrong.
For example, the specification of a Parity Decider would be a TM
takes a representation of a natural number as its initial tape
content and accepts it only if it is even.
The description of that machine, on the other hand, would describe >>>>>> what the alphabet of this machine is, what it's state transitions
are, etc. i.e. it would give all the information necessary to
actually construct the machine.
André
I already know how TM machine descriptions actually work.
DDD simulated by HHH1 has the exact same
sequence of steps as the directly executed DDD().
People here think that when DDD is simulated by
the same simulator that it calls (thus causing
recursive simulation) that DDD must have the same
behavior as DDD simulated by HHH1 that DDD does
not call.
The behaviour of DDD is the behaviour that DDD specifies. If some
program simulaates differently then it does not simulate the
behaviour of DDD.
It's not that hard really.
When an input calls its own simulator with itself as input
THIS DOES CHANGE ITS BEHAVIOR.
There is only one DDD that uses the algorithm of only one HHH. How can
that be different?
Its over-your-head.
You are so indoctrinated with the infallible word
of textbook that you disagree with the verified
facts of actual execution traces.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 512 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 85:20:30 |
| Calls: | 10,018 |
| Calls today: | 1 |
| Files: | 13,847 |
| D/L today: |
1 files (9K bytes) |
| Messages: | 6,365,568 |