Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #119373
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: How to write a self-referencial TM? |
| Date | 2025-05-17 11:01 +0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <cd31647abcc33f0978415df34ec2c8d41d886591.camel@gmail.com> (permalink) |
| References | (9 earlier) <10067ok$3ib39$1@dont-email.me> <e63d3083ddf6b9ab172cc24c07155410d81ce5b4.camel@gmail.com> <1007lrp$3r388$1@dont-email.me> <0cbe88d46c63af596e4d2ad6a846e61b7efb14bb.camel@gmail.com> <1008fhf$53u$1@dont-email.me> |
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:
> > > > > > > > > > > > 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.
> > >
> > > 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.
Ex2: The following D is also a valid HP counter-example:
void D() {
if(H(D)) return; // never return
while(1) {};
}
The yes/no toggle effect in the HP proof is just for more visibility effect.
The self-reference issue is very common and fundamental. And I think it is
unsolvable in language/theory (all that I saw in set theory is likely wrong).
[snip from ClassGuidelines.trxt]
....
This guideline has no strong opinion on how this self-ops should be handled,
yet (it is like divided by zero error). Implement may check the self-ops (not
generally doable) and return ELOOP. Working around might be needed since the
intent mostly assumes the argument is passed by value, nonetheless a
theoretical bug might be thus hidden.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-14 13:13 +0800
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 07:02 +0100
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 09:51 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 00:43 +0800
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 18:14 +0100
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 01:33 +0800
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 18:49 +0100
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 02:01 +0800
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 19:38 +0100
Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 13:00 -0700
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 15:02 -0500
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 21:19 +0100
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 21:16 +0100
Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 13:49 -0700
Re: How to write a self-referencial TM? Mr Flibble <flibble@red-dwarf.jmc.corp> - 2025-05-14 21:13 +0000
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-15 10:24 +0300
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 22:28 +0100
Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 14:40 -0700
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-14 23:02 +0100
Re: How to write a self-referencial TM? Andy Walker <anw@cuboid.co.uk> - 2025-05-15 01:09 +0100
Re: How to write a self-referencial TM? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2025-05-14 17:19 -0700
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 09:38 +0800
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 09:58 +0800
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 10:11 +0800
Re: How to write a self-referencial TM? Ben Bacarisse <ben@bsb.me.uk> - 2025-05-15 00:55 +0100
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-15 10:17 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 12:24 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 01:39 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-14 12:45 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 02:13 +0800
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-15 01:53 +0800
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-15 17:08 +0100
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-15 11:47 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 03:57 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-15 15:50 -0500
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:33 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:43 -0500
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-16 12:10 -0400
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-17 11:58 +0300
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-15 19:37 -0400
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:27 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:40 -0500
Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-19 10:21 +0200
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:39 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-20 23:41 -0500
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-21 11:47 +0300
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-21 07:11 -0400
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 02:49 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-15 14:15 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 04:08 +0800
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:45 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:47 -0500
Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-16 21:34 +0200
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:40 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:44 -0500
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-17 12:02 +0300
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 01:40 +0100
Re: How to write a self-referencial TM? Richard Heathfield <rjh@cpax.org.uk> - 2025-05-16 01:59 +0100
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 09:47 +0800
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 03:26 +0100
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-16 19:40 +0800
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 16:33 +0100
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 03:35 +0800
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 23:51 +0100
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 11:01 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 22:12 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 11:23 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 22:40 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 11:49 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 22:58 -0500
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-17 09:02 -0400
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-17 15:45 +0100
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-18 03:26 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-17 14:39 -0500
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-18 11:20 +0300
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 04:35 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 15:57 -0500
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-18 17:45 -0400
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 05:46 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 17:09 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 06:35 +0800
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-18 19:09 -0400
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-19 07:54 +0800
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:52 +0300
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:48 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-20 23:36 -0500
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-21 11:56 +0300
Re: How to write a self-referencial TM? André G. Isaak <agisaak@gm.invalid> - 2025-05-18 15:58 -0600
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 17:08 -0500
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-18 19:19 -0400
Re: How to write a self-referencial TM? André G. Isaak <agisaak@gm.invalid> - 2025-05-18 21:21 -0600
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-18 23:07 -0500
Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-19 09:54 +0200
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 15:29 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-20 23:33 -0500
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-21 12:03 +0300
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-21 07:16 -0400
Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-21 21:43 +0200
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-21 14:49 -0500
Re: How to write a self-referencial TM? "Fred. Zwarts" <F.Zwarts@HetNet.nl> - 2025-05-23 13:03 +0200
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:44 +0300
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-19 13:41 +0300
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-17 20:46 +0100
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-17 14:55 -0500
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-17 16:07 -0400
Re: How to write a self-referencial TM? Andy Walker <anw@cuboid.co.uk> - 2025-05-16 12:22 +0100
Re: How to write a self-referencial TM? Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2025-05-16 16:57 +0100
Re: How to write a self-referencial TM? Andy Walker <anw@cuboid.co.uk> - 2025-05-16 21:04 +0100
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 15:38 -0500
Re: How to write a self-referencial TM? wij <wyniijj5@gmail.com> - 2025-05-17 05:21 +0800
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 16:40 -0500
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-16 20:32 -0400
Re: How to write a self-referencial TM? Richard Damon <richard@damon-family.org> - 2025-05-16 17:59 -0400
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-16 10:24 +0300
Re: How to write a self-referencial TM? olcott <polcott333@gmail.com> - 2025-05-16 10:37 -0500
Re: How to write a self-referencial TM? Mikko <mikko.levanto@iki.fi> - 2025-05-15 10:07 +0300
csiph-web