Re: How to write a self-referencial TM?

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

 
Not to mention the very common variant where landing on Free Parking
means you get all the money from the center of the board.  Or was that
something else?
 
[...]

// Manpage of class Spu
NAME
       Spu - Class of general purpose Soft-CPU

SYNOPSIS
       Except POD types, C structures, all types are declared in namespace Wy.

       #include <CSCall/Sct.h>

       Spu  (Soft  CPU)  is  a revised model of Turing Machine and a class that
       acts like a general purpose CPU-based computing machine to  provide  se‐
       mantics for computing language and for remote program communication.

       The  main differences of Spu and general purpose CPU (or TM) is that Spu
       has no ´register´ nor ´flag´, Spu has only a tape. The tape is initially
       empty. Every object (referred to as tape variable) in the tape is  allo‐
       cated via instruction Alloc and identified by a continuous index number.
       Tape variable can be any C++ type, including Spu.

       The  instruction  of Spu is application definable. Except necessary few,
       about  >30  instructions  are  defined  for  convenience,  see   manpage
       Wy.Sct(3wy).

       Documentation following omits the scope name Wy::Sct for each occurrence
       of Spu for clearity.

[cut]
----------------------

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 considered
   variable or stateful (useful in developing theory), because data structure 
   related to instruction is considered part of the instruction, simiar to the
   OO concept of C++ class.
4. Multi-tasking can be modeled by multi-instances of Spu (or tape variable
   can be an Spu object)