Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #118986 > unrolled thread

How to write a self-referencial TM?

Back to article view | Back to comp.theory

Contents

  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

Page 1 of 6  [1] 2 3 4 5 6  Next page →

#118986 — How to write a self-referencial TM?

Q: Write a turing machine that performs D function (which calls itself):

void D() {
 D();
}

Easy?

[toc] | [next] | [standalone]

#118988

[I mistakenly sent my reply by email first time round. My 
apologies to wij for the mis-click.]

On 14/05/2025 06:13, wij wrote:
> Q: Write a turing machine that performs D function (which calls itself):
> 
> void D() {
>   D();
> }
> 
> Easy?
> 
> 

Yes.

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

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119016

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.
To make a TM that references itself the closest
thing is a UTM that simulates its own TM source-code.


-- 
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#119037

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?

[toc] | [prev] | [next] | [standalone]

#119039

On 14/05/2025 17:43, 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?

It doesn't have to simulate anything. All it has to do is to 
restore the state into which the programmer wishes to recurse.
I've already shown how this can be done.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119045

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:
> > > 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?
> 
> 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?

[toc] | [prev] | [next] | [standalone]

#119051

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.

> 
>> I've already shown how this can be done.
> 
> Where?
> 
Message-ID: <1001bmf$2ao7o$2@dont-email.me>

Here's the gist of that article...

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

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119055

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?

> > 
> > > I've already shown how this can be done.
> > 
> > Where?
> > 
> Message-ID: <1001bmf$2ao7o$2@dont-email.me>
> 
> Here's the gist of that article...
> 
> 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

[toc] | [prev] | [next] | [standalone]

#119062

On 14/05/2025 19:01, wij wrote:
> 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."

Yes.

> 
> Then, what is it?

It's my answer to your question:

Q: Write a turing machine that performs D function (which calls 
itself):

void D() {
  D();
}


>>>> I've already shown how this can be done.
>> Here's the gist of that article...
>>
>> 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.

[0] is the *tape*.

TMs have a tape, a read/write head, a single-stepping tape motor, 
and a finite state machine.

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.

> 2. D() should have at least one final state

Yours doesn't, so why should mine?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119075

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

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#119077

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.


-- 
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

[toc] | [prev] | [next] | [standalone]

#119080

On 14/05/2025 21:02, olcott wrote:
> 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.

Correct.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119078

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.

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

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119086

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.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#119099

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.

/Flibble

[toc] | [prev] | [next] | [standalone]

#119184

On 2025-05-14 21:13:19 +0000, Mr Flibble said:

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

You cannot pose in finite time a problem that has an infinite behaviour
in its formulation. If the problem will not be posed in a finite time
it will never be solved.

-- 
Mikko

[toc] | [prev] | [next] | [standalone]

#119108

On 14/05/2025 21:49, Keith Thompson wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:

<snip>

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

Of course. HP is a thought experiment, not an exercise for 
hardware engineers (or indeed software engineers). I just can't 
help turning my thoughts in that direction.

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

Quite so.

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

All acknowledged, all agreed.

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

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119111

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.

In C terms, there is no real world output device that can hold the
output of `while (1) putchar('x');`.

It's the unboundedness of the tape that makes the halting problem
unsolvable.  It's what allows the combined internal (finite state)
and external (unbounded tape) state of a TM to be unbounded.  If we
considered only TMs that consume less than N tape cells, for any
finite N, the halting problem *for such TMs* would be theoretically
solvable by detecting or not detecting a repeated state.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#119120

On 14/05/2025 22:40, Keith Thompson wrote:
> 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.

Indeed, but the existence of TMs for which it isn't long enough 
doesn't mean there aren't plenty of TMs for which a C90 would be 
more than adequate.

A hobbyist wishing to code up a TM shouldn't be put off by the 
fact that his laptop doesn't have an infinitely large hard disk.

<read and snipped>
-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#119139

On 14/05/2025 21:16, Richard Heathfield wrote:
> 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.

	Indeed, there are lots of computationally equivalent versions:

  -- two or more tapes [indeed, two-dimensional tapes]
  -- one-way or two-way
  -- "paper" tapes where you can punch holes to change the content but not
       stick the chad back in to "unpunch" the holes
  -- two symbol, three symbol, ...
  -- move two or more spaces at a time
  -- others I've forgotten

Once you've shown they're equivalent, you can use a convenient version to
solve problems and the simplest versions to investigate theoretical limits.
See below for more info.

>> (Though with a one-way tape, I'm not sure what happens if the TM
>> runs off the end of the tape.)

	It's helpful to have an end-of-tape "marker" [could be a symbol
used only for this purpose].

> I should imagine that you could build one hell of a stack on one-way tape.

	Yes, but for theoretical purposes you probably need two stacks [or
near equivalents] to hold two arbitrary-length integers.  On the other hand,
the tape can be read as two integers reading outwards from the head position,
and the TM transitions then correspond to fiddling with the least-significant
digits of these integers.  See also below.

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

	An alternative view is that you can attach a "tape factory" to your
TM, and add a new square or three when you would otherwise run off the end.

> 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.
	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
"now mount the next disc".  So I used to point out to the students that
this was quite precisely a TM.  The PC was a FSM which could read/write
"squares" consisting of one floppy disc each containing several million
binary digits depending on the state of the PC, from time to time going to
the next or previous floppy.  If you didn't have a next floppy, you went
to a shop and bought some more.

	All the material described above is discussed in my lecture notes,
on the Web starting at

   https://www.cuboid.me.uk/anw/G12FCO/header.html

[see especially the last few lectures/problem classes/courseworks, all
linked from the header page].  Of course, there are many other excellent
web pages and books that discuss this stuff with varying degrees of
formality and level of maths/logic required as a pre-requisite.

	[May be worth noting that the references to emulation and to self-
referential programs in lecture 18 pre-date musings by Messrs Olcott and
Flibble by years, and they certainly weren't original to me.]

-- 
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Heller

[toc] | [prev] | [next] | [standalone]

Page 1 of 6  [1] 2 3 4 5 6  Next page →

Back to top | Article view | comp.theory

csiph-web