scientific article; zbMATH DE number 4125019

From MaRDI portal
Publication:4205083





[For the entire collection see Zbl 0681.00016.] We examine computability by means of Horn clauses from the point of view of a general theory of computability on abstract data types. In this theory, an abstract data type is modelled semantically by a many-sorted algebra A, considered unique up to isomorphism, and various equivalent formalisms are used to define functions and sets on A. Usually these formalisms are generalizations to A of sequential deterministic methods of computing on the natural numbers, or finite strings; however we use a parallel deterministic formalism to study computability on A. We formulate a concept of Horn clause computability that applies to any many-sorted algebra A and consider the following questions: Does Horn clause computability define only, and all, the ``effectively calculable sets and functions on A? Does Horn clause computability, with its non-determinism and potential for parallelism, effect the Generalized Church-Turing Thesis for computation on A? And, since abstract data types may be axiomatically specified: What is the relation between an algebraic specification for A and a Horn clause program over A? In order to answer these questions we extend the theory of computability to discuss the notion of specificability. We begin to determine the scope and limits of effective specification, and postulate an appropriate Church-Turing Thesis for specification that complements the thesis for computation on abstract data types. We show that Horn clause ``computability specifies more than the effectively calculable sets on A, in general. We also show that algebraic specifications and Horn clause ``computability are equivalent specification tools.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4205083)