Necessary and sufficient conditions for the universality of programming formalisms
type: Item
instance of: scholarly article
title: Necessary and sufficient conditions for the universality of programming formalisms
zbMATH Open document ID: 0552.68008
DOI: 10.1007/BF00288773
author: Assaf Kfoury
author: Paweł Urzyczyn
published in: Acta Informatica
publication date: 1985-01-01T00:00:00Z
review text: Over many familiar datatypes the notion of ''computable'' coincides with the notion of ''flowchartable''. For example, any partial recursive function is defined by a flowchart program over the datatype \((\omega,=,succ,0)\) where succ is the successor operation on the set \(\omega\) of natural numbers. It is also known that flowcharts are not a universal programming formalism over arbitrary datatypes, in the sense that the notion of ''computable'' is strictly more general than the notion of ''flowchartable''. In this paper we consider various extensions and restrictions of the basic formalism of flowcharts, and then for every such formalism, we characterize the datatypes over which the computable functions are exactly the functions programmable in this formalism. We say that a function is computable over a datatype if it is effective relative to the primitive operations and relations of the datatype (which are assumed to be defined everywhere on the domain of the datatype). Our results are expressed algebraically, putting simple restrictions on the primitive operations and relations of datatypes. For example, we prove that the notion of ''computable'' over an arbitrary (one-sorted) datatype A coincides with the notion of ''definable by a flowchart program over A with recursive calls'' if and only if: (\(\forall k)(\exists \ell)\) (\(\forall\) k-tuple a of elements in the domain of A) [If a generates more than \(\ell\) elements then a generates infinitely many elements]. We also prove that the notion of ''computable'' over an arbitrary datatype A coincides with the notion of ''definable by a flowchart program over A with counters'' if and only if: (\(\forall k)(\exists \ell)\) (\(\forall\) k- tuple a of elements in the domain of A) [Every element at all generated by a can be generated using \(\ell\) memory locations]. We prove several other similar results. In the last section of the paper, we examine programmability over familiar algebraic structures (groups, rings,…
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 3880076
zbMATH Keywords: data types
zbMATH Keywords: partial recursive function
zbMATH Keywords: flowchart
zbMATH Keywords: algebraic structures
MaRDI profile type: Publication
cites work: Interpolation theorems for program schemata
cites work: Program Schemes with Pushdown Stores
cites work: On Classes of Program Schemata
cites work: Q3347253
cites work: Algorithmic properties of structures
cites work: Q4074367
cites work: Generalized galois theory and its application to complexity
cites work: Q5625129
cites work: Program schemes, recursion schemes, and formal languages
cites work: First-order dynamic logic
cites work: Translatability of schemas over restricted interpretations
cites work: Definability by programs in first-order structures
cites work: Definability by deterministic and non-deterministic programs (with applications to first-order dynamic logic)
cites work: Q4139653
cites work: On formalised computer programs
cites work: A difference in expressive power between flowcharts and recursion schemes
cites work: Relative complexity of operations on numeric and bit-string algebras
cites work: Relative complexity of algebras
cites work: Q5590814
cites work: Axiomatic Definitions of Programming Languages
cites work: Termination assertions for recursive programs: Completeness and axiomatic definability
cites work: Definability in dynamic logic
cites work: Q4185781
cites work: Q4088800
cites work: The unwind property in certain algebras
cites work: A necessary and sufficient condition in order that a Herbrand interpretation be expressive relative to recursive programs
cites work: Nontrivial definability by flow-chart programs
cites work: Q3326828
cites work: A view of computability on term algebras
cites work: Classification of algebraic structures by work space
full work available at URL: https://doi.org/10.1007/bf00288773
OpenAlex ID: W1977367505
description: scientific article; zbMATH DE number 3880076