Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Thu, 15 May 2025 10:11:58 +0800
Organization: A noiseless patient Spider
Lines: 166
Message-ID: <922b79b3f3c5f6a1b2e168a006a044a81f95aa7d.camel@gmail.com>
References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com>
				<1002akp$2i4bk$2@dont-email.me>
				<479eebef3bd93e82c8fe363908b254b11d15a799.camel@gmail.com>
				<1002j0r$2k04b$1@dont-email.me>
				<3b177909de383fcf209cfb9ff81fe2f118640578.camel@gmail.com>
				<1002l44$2k04b$3@dont-email.me>
				<8c7a8437e78a5b798cc23d77a8e1b6080e59ab0e.camel@gmail.com>
				<1002nvo$2k04b$5@dont-email.me>	<87plgb9d4i.fsf@nosuchdomain.example.com>
				<1002tma$2k04c$5@dont-email.me> <1003bbu$2d57f$1@dont-email.me>
			 <87zffe914z.fsf@nosuchdomain.example.com>
		 <7d480ebd5935e07082c8f37d6c810a28974f7bca.camel@gmail.com>
	 <efb3bbe803871e5892460a4596c64f5e1cedab03.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Thu, 15 May 2025 04:12:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b7c2e7cb48bac1670f833664c84ad09e";
	logging-data="3072424"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18QF3m5hQdsoUIatSJzmUxH"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:HgwBJarGXk+DoGypLLBNDen9Qoc=
In-Reply-To: <efb3bbe803871e5892460a4596c64f5e1cedab03.camel@gmail.com>

On Thu, 2025-05-15 at 09:58 +0800, wij wrote:
> On Thu, 2025-05-15 at 09:38 +0800, wij wrote:
> > On Wed, 2025-05-14 at 17:19 -0700, Keith Thompson wrote:
> > > Andy Walker <anw@cuboid.co.uk> writes:
> > > > 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 computati=
onally
> > > > > > equivalent, so the distinction doesn't matter all that much.
> > > >=20
> > > > 	Indeed, there are lots of computationally equivalent versions:
> > > >=20
> > > > =C2=A0-- two or more tapes [indeed, two-dimensional tapes]
> > > > =C2=A0-- one-way or two-way
> > > > =C2=A0-- "paper" tapes where you can punch holes to change the cont=
ent but not
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 stick the chad back in to "unpunch" =
the holes
> > > > =C2=A0-- two symbol, three symbol, ...
> > > > =C2=A0-- move two or more spaces at a time
> > > > =C2=A0-- others I've forgotten
> > >=20
> > > Not to mention the very common variant where landing on Free Parking
> > > means you get all the money from the center of the board.=C2=A0 Or wa=
s that
> > > something else?
> > >=20
> > > [...]
> >=20
> > // Manpage of class Spu
> > NAME
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Spu - Class of general purpose Sof=
t-CPU
> >=20
> > SYNOPSIS
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Except POD types, C structures, al=
l types are declared in namespace Wy.
> >=20
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 #include <CSCall/Sct.h>
> >=20
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Spu=C2=A0 (Soft=C2=A0 CPU)=C2=A0 i=
s=C2=A0 a revised model of Turing Machine and a class that
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 acts like a general purpose CPU-ba=
sed computing machine to=C2=A0 provide=C2=A0 se=E2=80=90
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 mantics for computing language and=
 for remote program communication.
> >=20
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 The=C2=A0 main differences of Spu =
and general purpose CPU (or TM) is that Spu
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 has no =C2=B4register=C2=B4 nor =
=C2=B4flag=C2=B4, Spu has only a tape. The tape is initially
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 empty. Every object (referred to a=
s tape variable) in the tape is=C2=A0 allo=E2=80=90
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 cated via instruction Alloc and id=
entified by a continuous index number.
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Tape variable can be any C++ type,=
 including Spu.
> >=20
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 The=C2=A0 instruction=C2=A0 of Spu=
 is application definable. Except necessary few,
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 about=C2=A0 >30=C2=A0 instructions=
=C2=A0 are=C2=A0 defined=C2=A0 for=C2=A0 convenience,=C2=A0=C2=A0 see=C2=A0=
=C2=A0 manpage
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Wy.Sct(3wy).
> >=20
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Documentation following omits the =
scope name Wy::Sct for each occurrence
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 of Spu for clearity.
> >=20
> > [cut]
> > ----------------------
> >=20
> > 1. In Spu, objects in the tape are allocated (constructed).
> > 2. Accessing the tape outside range will throw an error.
> > 3. Instructions in Spu are class members. 'instructions' can be conside=
red=20
> > =C2=A0=C2=A0 variable or stateful (useful in developing theory), becaus=
e data structure=C2=A0
> > =C2=A0=C2=A0 related to instruction is considered part of the instructi=
on, simiar to the
> > =C2=A0=C2=A0 OO concept of C++ class.
> > 4. Multi-tasking can be modeled by multi-instances of Spu (or tape vari=
able
> > =C2=A0=C2=A0 can be an Spu object)
> >=20
>=20
> With the issue of TM's tape at least, I think Spu is more *realistic* tha=
n TM.


/* Copyright is licensed by GNU LGPL, see file COPYING.       by I.J.Wang 2=
025
=20
   Spu program: 'instruction' is a C++ function:
       "Mov a,b" performs the function of the expression "a=3Db"
       "Add a,b" performs the function of the expression "a+=3Db"
       "Add a,b,c" performs the function of the expression "c=3Da+b"
=20
   Build: g++ s_tut2.cpp -lwy
*/
#include <Wy.stdio.h>
#include "CSCall/Sct.h"

using namespace Wy;
using namespace Wy::Sct;

void t0() {
 Errno r;
 Spu spu;

// Note: In general, program.reserve(...) is needed if non-memcpy_able vari=
able
//       (String) is used. Because this spu program is simple and no error =
is=20
//       thrown, we save the trouble.
/* 0 */ spu.add_instr( new Alloc<float>());  // 0 (alloc 3 float)
/* 1 */ spu.add_instr( new Alloc<float>());  // 1
/* 2 */ spu.add_instr( new Alloc<float>());  // 2
/* 3 */ spu.add_instr( new Alloc<String>()); // 3 (alloc 3 String)
/* 4 */ spu.add_instr( new Alloc<String>()); // 4
/* 5 */ spu.add_instr( new Alloc<String>()); // 5
/* 6 */ spu.add_instr( new Mov<float,float>(TpVar(0),1.32)); // init. var.
/* 7 */ spu.add_instr( new Mov<float,float>(TpVar(1),3.2)); =20
/* 8 */ spu.add_instr( new Add<float,float>(TpVar(0),TpVar(1),TpVar(2)));=
=20
/* 9 */ spu.add_instr( new Cout<float>(TpVar(2))); // print resut of v(0)+v=
(1)
/* 10 */ spu.add_instr( new Cout<char>('\n'));=20

/* 11 */ spu.add_instr( new Mov<String,const char*>(TpVar(3),"hello "));
/* 12 */ spu.add_instr( new Mov<String,const char*>(TpVar(4),"world\n"));
/* 13 */ spu.add_instr( new Add<String,String>(TpVar(3),TpVar(4)));
/* 14 */ spu.add_instr( new Cout<String>(TpVar(3))); // print result of v(3=
)+v(4)
/* 15 */ spu.add_instr( new Free<String>()); // free 3 non-memcpy-able obje=
cts
/* 16 */ spu.add_instr( new Free<String>());
/* 17 */ spu.add_instr( new Free<String>());
/* 18 */ spu.add_instr( new Fin(0));

 if((r=3Dspu.run( InstrIdx(0) ))!=3DOk) { // run the program from InstrIdx(=
0)
   WY_THROW(r);
 }
};

int main(int argc, const char* argv[])
try {
 t0();
 cout << "OK" WY_ENDL;
 return 0;
}
catch(const Errno& e) {
 cerr << wrd(e) << WY_ENDL;
 return -1;  // e.c_errno();
}
catch(...) {
 cerr << "main() caught(...)" WY_ENDL;
 throw;
};

------------------
If matured, there can be 'Spu language', everything will be lots more conve=
nient,
including for theory development.