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.
Back to the list of talks