While-programs are Turing-incomplete for non-strict oracles

Ulrich Berger

(Swansea University)

We show that while-loops (or primitive recursion + unbounded search) form a less powerful programming concept than recursion when oracles accepting partially defined inputs are present. This implies that in a non-strict functional programming language while-programs cannot replace recursive programs with regard to the computation of functionals of type two.
Tuesday 26th March 2002, 14:00
Robert Recorde Room
Department of Computer Science