### Subrecursive

- finite automata
- recursive functions
- context-free grammers
- neural nets

### Recursive

#### turing machines

deterministic, probabilistic, nondeterministic, etc. see: Turing Machine Church Turing Thesis (CTT)

- Kolmogorov algoritmhs
- Minsky machines
- array machines
- vector machines
- partial recursive functions
- post systems
- petri nets
- neural nets

### Super-recursive

#### inductive turing machines

the simplest realistic inductive TM (sITM) is essentially similar to an ordinary TM with seperate tapes for input, working and output. an ITM doesnt need to halt in order to produce a result, since the 'result' can be seen as an unchanging (or itteratively converging) word/s on the output tape.

#### limit turing machines and topological turing machines

#### infinite data and infinite time machines

#### limit recursive functions

limit recursive functions are between the computable and the arbitrarily uncomputable.

- limit partial recursive functions

### notes

- based on article in CACM http://www.acm.org/cacm/1101/p82-burgin.pdf
- citeseer references http://citeseer.nj.nec.com/context/57078/0
- see also: Complexity Theory / \ Algorithmic Information Theory

### References

- Burgin, M. Super-recursive algorithms as a tool for high performance computing. In Proceedings of High Performance Computing Symosium (San Diego, 1999) 224-228 http://www.math.ucla.edu/~mburgin/res/compsc/res2/highperfcomp.html
- Burgin, M. Topological algorithms. In Proceedings of 16th International Conference for Computers and Applications ISCA (Seattle, 2001) 61-64
- Goldin, D. and Wegner, P. Persistent Turing Machines. J. Symbolic LOgic 65 (2000). Assoc. of Symbolic Logic. 567-604
- Moore, C. Recursion theory on real- and continuous-time computation. Theoretical Computer Science 162 (1996), 23-44
- Siegelman, H.T. Neural Networks and Analog Computation Birkhauser, Berlin, 1999
- Winograd, T. The design of interaction. Beyond Calculation: The next 50 years of computing(1997) Copernicus, 149-161