Egon Börger: Introduction into the Theory of Computation.
A Register Machine Approach.
HyperCOSTOC-Course (COmputer Supported Teaching Of Computer science).
10 Lectures (2100 KBytes) developed with AUTOOL +
handbook (735K, pp.334).
Edited with assistance of
R.Bellucci, G.Pulice, E.Vannini, R.Gherardi.
Hofbauer, München 1989.
Electronic introductory course (with accompanying textbook in printed
form) containing a streamlined version (and adaptation to the
electronic medium) of the following selected themes from the
Computability, Complexity, Logic book
- While programs and recursive functions
- An interpreter for While programs
- Church's thesis and algorithmically undecidable problems
- Enumeration and recursion theorem
- Recursion theorem: applications
- Finite automata 1
- Finite automata 2
- Modular decomposition of automata
- A small universal Turing machine program
- NP-completeness