Algorithmics and recursive function theory

The following sections are included:

• Algorithm and effective computability

• Recursive functions

  • Primitive recursive function

  • Diagonalization

  • Partial recursive function

  • Enumeration of partial recursive functions

  • Existence of uncomputable reals

  • Church-Turing thesis

  • Computation = polynomial equation

  • Recursively enumerable ≠ recursive

• Universal computers

  • Turing Machine

  • Cellular Automata

  • Register machines

  • Digital computers are physical systems which are universal up to finite complexities

• Finite automata

  • Definition

  • Distinguishability of states

• Oracles

  • Definition

  • Zeno squeezing

• Recursive analysis

• Formal systems correspond to computable processes