A view of computability on term algebras

AbstractA framework of definitions for, and questions about, notions of computability, complexity, and logic for term algebras is built around known results in the literature and the current work. The term algebra for finite binary trees and various classes of programs for computing on them, a class similar to LISP being the most powerful, serve as a focus. Several interesting classes of programs less powerful than LISP are obtained by varying the functions and predicates available in the programming language. It is shown how they relate to one another and then some of their properties are explored. For example, there is a class powerful enough to compute all the partial recursive functions on the natural numbers that is neither sufficiently powerful to code the binary trees into the natural numbers nor to recognize any set that is both infinite and coinfinite. A simple logic sufficient to talk about trees and LISP-like computations is given and it is suggested that certain pebble games provide very reasonable measures of complexity of trees. It is also indicated how various particular results give further insight into such fundamental notions as Turing computable and recursively enumerable