A392245 et al.: result and runlengths of Wolfram’s TM’s

Refs:

Related sequences:

The Turing machine (TM) considered here operates on a tape which is the binary representation of a number n. Position 0 on the tape corresponds to the LSB (least significant bit) of n (and other positions to the bit with weight 2n, so positive n are to the left). Here we consider only integer n and positions >= 0, but we could have negative positions corresponding to the bits of the fractional part to the right of the binary point.

The TM is specified through a transition table { (in,state): (out,state,move) } which specifies the symbol out to write at position on the tape, the new state, and the move (±1) to make towards the new position (+= move), depending on the symbol in read from the tape at position, and the current state.

This TM acts on an integer n by reading the tape (i.e., the bit of n) at the current position and depending on it’s current state, it may change the bit at this position in n, enter a new state and move to a new position.

This action is repeated, starting at position 0 in state 0, until the position becomes negative. The resulting final n is considered to be the result of the computation, if the machine stops. We also consider the “runtime” = number of iterations required to reach a position < 0 depending on the starting value n.)

Programs


# most efficient version, computing the result
# for the particular machines 261, 1285 and 3333.
# (Never goes beyond a '00' in the bits of n, and writes '0' on moving right.)

A392245 = lambda n: n-n%2**next(k for k in range(n+1) if n>>k&3==0)

# simple version for computing runtime for any rule, assuming convergence :
def A393103(n, rule=1285, pos=0, state=0, max_iterations = 999):
  for i in range(max_iterations):  # Python operator precedence: */ +- << & | ==
    bit = n >> pos & 1; p = (2-state*2+bit)*3; state = rule >> p+2 & 1
    if rule >> p+1 & 1 != bit: n ^= 1 << pos
    if 0 > (pos := pos-1 if rule>>p & 1 else pos+1): return i+1 # _M. F. Hasler_, Feb 08 2026

#####################

class TM(dict):
   """The TM can be initialized through the transition table {(in, state): (out, state, move)}
or through the "Wolfram rule number". The transition table can be given with tuples of integers
or strings {'1D': '1DL',...} or as a single string like "1D: 1DL, 0D: 0DL, 1U: 0DL, 0U: 0UR",
or as kwargs (D1='1DL', ...). Additional parameters ('pos', 'state', 'memoize', ...) can also
be given in the same dict or as kwargs. The class provides the following methods:
* reset(self): reset self.pos = self.state = 0
* from_rule(self, rule: int, num_states = 0): make/update transition table according to the rule.
  If not given as argument or in the dict, the number of states will be guessed from the size of the rule.
* rule_number(self) -> int: return the corresponding rule number
* run(self, n) -> (final_n, runtime): reset and run the machine on a tape given by the bits of n.
  The machine stops when position -1 is reached. If this never happens, final_n = runtime = -1.
* result(self, n) -> int: the result `final_n` described above.
* runtime(self, n) -> int: the `runtime` described above (number of iterations until position = -1).
* __str__(self): string representation of the TM.
  (Valid Python code input, including T.pos, T.state, but not memoized results.)
* T.memoize: if truthy, results (final_n and runtime) of computations are stored.
* __call__(self, n): If T=TM(...), then T(n) yields the result of one iteration,
  using the current position `T.pos` and T.state. The bit at `T.pos` in `n`
  and T.pos and T.state change according to the transition table.
  If T.pos < 0 (when called), StopIteration is raised.
"""
   def __init__(self, data=None, **kwargs):
      if isinstance(data, str):
         sep = next(s for s in ('->', ':', '>', ' ', '') if s in data)
         if not sep: raise ValueError("Use ':' or '->' or ' ' to define the mapping.")
         data = {kv[0].strip(): kv[-1].strip() for pair in data.split(',')
                 if (kv := pair.strip().split(sep))}
      elif isinstance(data, int):
         kwargs['rule'] = data; data = kwargs
      elif data is None: data = kwargs
      elif kwargs: data |= kwargs
      self.states = ''
      for key,value in data.items():
        if len(key) == 2:
           #else: raise ValueError(f"Expected (state, symbol_read), got {key!r}.")
           if len(value) != 3: raise ValueError(f"Expected (state, symbol_write, move), got {value!r}.")
           if isinstance(key, str):  key = self.str2num(key)
           if isinstance(value, str): value = self.str2num(value)
        elif key=='rule': self.from_rule(value) 
        self[key] = value
      num_states = len(self.states) or 1+max(s[1] for s in self if isinstance(s, tuple))
      # default values
      for k,v in {'pos': 0, 'state': 0, 'memoize': True}.items():
         if k not in self: self[k]=v

      # move this to the end of the dict
      states = self.pop('states') or ('*' if num_states < 2 else 'UD' if num_states < 3
                else str(bytes(range(65,65+num_states))))
      self.states = states 
      super().__setattr__('results', {})# in any case -- we may want to activate memoization later

   def str2num(self, s: str):
      "Return numerical version of (read, state) or (write, state, move)."
      s = sorted(s.upper()) # digit first
      if not s[0].isdigit(): raise ValueError(f"No digit in {s}'!")
      if len(s) > 2:
        for move in 'LR':
          if move in s: del s[s.index(move)]; break
        else: raise ValueError(f"No move (L/R) found in {s}.")
        s.append(1 if move=='L' else -1)
      # now s = [ in_out_digit, state_letter, [move_integer] ]
      if s[1] not in self.states: self.states += s[1]
      s[0] = int(s[0]) ; s[1] = self.states.index(s[1])
      return tuple(s)

   def __call__(self, n):
      """Apply the TM in its current state to a n's bits, return the new n."""
      if self.pos < 0: raise StopIteration
      input = (n >> self.pos) & 1
      out, self.state, move = self[input, self.state]
      if out != input: n ^= 1 << self.pos
      self.pos += move
      return n

   def result(self, n):
      "Return the result for starting value n, or -1 if the TM doesn't stop."
      return self.run(n)[0]
   def runtime(self, n):
      "Return the runtime for starting value n, or -1 if the TM doesn't stop."
      return self.run(n)[1]
   MAX_ITER = 99
   def run(self, n):
      "Apply the TM to n until position < 0; return (final n, number of iterations)."
      if result := self.results.get(n): return result
      starting_value = n ; self.reset()
      for iter in range(self.MAX_ITER):
         if self.pos < 0: break
         n = self(n)
      else: n = iter = -1 # or: n if self.pos > bit_length(n)+2 else -1 ?
      if self.memoize: self.results[starting_value] = n, iter
      return n, iter

   def reset(self): self.state = self.pos = 0

   def num2str(self, s):
      "Convert (in,state) or (out,state,move) to string. Return s if not a tuple."
      return f"{s[0]}{self.states[s[1]]}{''if len(s)<3 else 'L' if s[2]>0 else 'R'}" if isinstance(s, tuple) else s 

   def as_str(self): return {self.num2str(k):self.num2str(v) for k,v in self.items() if k!='states'}
   def __repr__(self): return f"TM('{", ".join(f"{k}: {v}" for k,v in self.as_str().items())}')"
   #def __str__(self): return str(self.as_str())
   __str__=__repr__
   # to use self.pos instead self['pos'] etc.:
   def __getattr__(self, key): return self[key]
   def __setattr__(self, key, value): self[key] = value

   def rule_number(self): # return Wolfram's rule number
      num_symbols = 2 # 1+max(s[0]for s in self if isinstance(self, tuple))
      num_states = len(self.states)
      base = num_symbols * num_states; BL = base.bit_length()
      return sum( ((f[0] + f[1]*num_symbols)*2 + (f[2]<0)) << BL*(base-k)
                  for k,f in enumerate(self.values(),1) if isinstance(f, tuple))
   def from_rule(self, rule, num_states = None):
      if num_states is None and not(num_states := self.get('num_states')):
         # try to guess from size of rule
         # a single state machine has only 2 mappings of 2 bits (what to output and where to move depending on input)
         # For a 2 state machine there are 4 octal digits, max = 7777 = 8^4-1
         num_states = 1 if rule < 8 else 2 if rule < 8**4 else 3 # TODO: extend to larger values
      base_size = (2 * num_states).bit_length() # the leading 1 adds the bit for the move
      state_mask = 2**(num_states - 1).bit_length() - 1
      for state in range(num_states-1,-1,-1):
         for input in (0,1):
            self[input,state] = rule & 2 and 1, (rule>>2) & state_mask, -1 if rule & 1 else 1
            rule >>= base_size


################## TESTING ##############
if 1:
 T = TM("1U -> 1UL, 0U -> 0DL, 1D -> 0UL, 0D -> 0DR")
 for n in range(1,9):
  T.pos=T.state=0
  seq = [(k:=T(k)if i else n, T.pos) for i in range(9) if T.pos>=0]
  print(" => ".join(f"{k:b}[{p}]" for k,p in seq))

(PARI) /* work in progress */

rule2plot(rule,states="UD")={print(" U1  U0  D1  D0\n ", strjoin([
 Str(if(t>3,"D","U"),bittest(t,1),if(t%2,">","<")) | t<-Vec(digits(rule,8),-4)]," "))}

rule2plot(261)
 U1  U0  D1  D0
 U0< D0< U0< D0>
rule2plot(1285)
 U1  U0  D1  D0
 U1< D0< U0< D0>
rule2plot(3333)
 U1  U0  D1  D0
 D1< D0< U0< D0>

/* show state, position & tape */
display(n,state,pos, width=20)={printf(Str("%",width-pos,"s\n%"width"s\n"),if(state,"D","U"),strjoin(binary(n)))}

result(n, rule=261, pos=0, state=0, show=0, max_iter=99)={for(i=1,max_iter, show && display(n,state,pos);
  my(in=bittest(n, pos), p=(!state*2+in)*3);
  bittest(rule,p+1)!=in && n=bitxor(n, 1<<pos); state = bittest(rule,p+2); (0 > pos += (-1)^bittest(rule,p))&& break);n}

/* "light" version w/o iter_counter & display */
A392245(n, rule=261, pos=0, state=0)={until(pos<0, my(in=bittest(n, pos), p=(!state*2+in)*3);
 bittest(rule,p+1)!=in && n=bitxor(n, 1<<pos); state = bittest(rule,p+2); pos += (-1)^bittest(rule,p));n} \\ _M. F. Hasler_, Feb 08 2026

/* "light" version for just computing the runtime */
A393103(n, rule=1285, pos=0, state=0)={for(i=1,oo, my(in=bittest(n, pos), p=(!state*2+in)*3);
 bittest(rule,p+1)!=in && n=bitxor(n, 1<<pos); state = bittest(rule,p+2);
 if(0 > pos += (-1)^bittest(rule,p), return(i))} \\ _M. F. Hasler_, Feb 08 2026


A392245(n)=result(n,rule=261)
[A392245(n) | n <- [1..20]]