Modelling distributive computation by selective machines. Issue 5 (3rd September 2021)

• Record Type: Journal Article
• Authors: Burgin, Mark
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 36:Issue 5(2021)
• Page Start: 395
• Page End: 411
• Publication Date: 2021-09-03
• Subjects: Distributed computing -- positive processor -- negative processor -- selective machine -- axiom -- language -- interaction -- dual machine -- recursive -- inductive -- regular; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2021.1934837
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : In this paper, classes of automata that perform distributed computations with unconventional interaction are described and studied. These automata are called selective machines and they are more powerful than Turing machines while their high computing and recognising power can be achieved exclusively by interaction when a system of recursive algorithms (automata) becomes super-recursive due to their interaction. Computations of selective machines are described by selective algorithms, which are super-recursive allowing computations of functions that are incomputable by Turing machines. Examples of selective algorithms are grammars with prohibition, correction grammars and grammars with exclusion. The study of selective machines and selective algorithms is based on the axiomatic theory of algorithms, in which the results are obtained in the general situation of axiomatically defined classes of automata and algorithms. Then these results are specified for many concrete classes of automata and algorithms, such as finite automata or Turing machines, by checking the necessary axioms.