High level languages of maximum power
H. Raymond Strong · 1971
The high level languages here are simplified programming languages focussing attention on various facilities such as recursion and pushdown stores. They are assumed to have some kind of subroutine facility. The notion of power studied is obtained by treating the programs as presenting functions of variable sub-routines and arguments of arbitrary data type. Languages are exhibited which are capable of expressing all such functions computable in a deterministic way. This result complements previous work of Paterson and this author who showed that certain flow chart languages, which are usually regarded as universal, were not universal in this sense. A simple function (of subroutines) which is inherently nondeterministic and thus not expressible in any of the standard high level programming languages is also exhibited.