Self-Modifying Finite Automata

This page is Copyright John N. Shutt 1996–1999,2002–2011,2015–2021. Here's what you're allowed to do with it.
Last modified: 04-Jan-21.

An SMFA is similar to an ordinary finite automaton, except that,

1. Each transition not only changes the state and reads an input symbol, it also modifies the set of transitions of the machine.
2. Each SMFA has a fixed finite set of registers, whose values are created states (as opposed to predefined states, which are part of the initial configuration of the machine).  When creating a new transition, its source and destination states must be specified; the only way to specify a created state is by retrieving it from a register; and the value of a register can only be changed to a state that doesn't already exist.  Thus, once a created state is no longer stored in the register that created it, there is no way to create more transitions to/from that state.

Journal papers:

• Y. Wang, K. Inoue, A. Ito, and T. Okazaki, "A note on self-modifying finite automata", Information Processing Letters 72 nos. 1–2 (29 October 1999), pp. 19–24.
  
  
• J. Shutt and R. Rubinstein, "Self-Modifying Finite Automata: An Introduction", Information Processing Letters 56 no. 4 (24 November 1995), pp. 185–190.
  
  
• J. Shutt and R. Rubinstein, "Self-Modifying Finite Automata", In B. Pehrson and I. Simon, editors, Technology and Foundations: Information Processing '94 Vol. I: Proc. 13th IFIP World Computer Congress, Amsterdam: North-Holland, 1994, pp. 493–498.

• WPI-CS-TR-95-4 (ps.gz) (pdf)
  Self-Modifying Finite Automata — Power and Limitations. J. Shutt. December 1995.
• WPI-CS-TR-95-2 (ps.gz) (pdf)
  Self-Modifying Finite Automata — Basic Definitions and Results. J. Shutt and R. Rubinstein. August 1995.
• WPI-CS-TR-93-11 (ps.gz) (pdf)
  Self-Modifying Finite Automata. J. Shutt and R. Rubinstein. December 1993.