## Neil D. Jones

University of Copenhagen

The author's forthcoming book proves central results in
computability and complexity theory from a programmer-oriented
perspective. In addition to giving more natural definitions,
proofs and perspectives on classical theorems by Cook, Hartmanis,
Savitch, etc., some new results have come from the alternative approach.
One: for a computation model more natural than the Turing machine,
multiplying the available problem-solving time provably increases
problem-solving power (in general not true for Turing machines). Another:
the class of decision problems solvable by Wadler's "treeless" programs,
or by cons-free programs on Lisp-like lists, are identical with the
well-studied complexity class **LOGSPACE**.

A third is that cons-free programs augmented with recursion can solve
*all and only* **PTIME** problems. Paradoxically, these programs often
run in exponential time (not a contradiction, since they can be simulated
in polynomial time by memoization). This tradeoff indicates a tension
between running time and memory space which seems worth further
investigation.

DIKU, University of Copenhagen

Universitetsparken 1

2100 Copenhagen East

Denmark

** Email:**neil@diku.dk

** Home page: **
http://www.diku.dk/people/NDJ.html

Back to the list of talks