User Tools

Site Tools



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


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


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



  • Burgin, M. Super-recursive algorithms as a tool for high performance computing. In Proceedings of High Performance Computing Symosium (San Diego, 1999) 224-228
  • 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
theory_of_algorithms.txt · Last modified: 2007/07/11 16:34 by nik