New Languages of Abstract Automata

EasyChair Preprint 7718

Abstract

The conventional theory of automata and algorithms associates only one language with each automaton or algorithm. Here it is demonstrated that each automaton or algorithm determines several algorithmic languages on different levels of computability. Properties of these languages and relations between them and conventional languages of automata or algorithms are studied. The obtained results made possible the discovery of a new class of algorithmic languages in addition to the well-known recursively enumerable and recursively coenumerable languages. The new languages are called recursively bienumerable comprising both recursively enumerable and recursively coenumerable languages.

Keyphrases: Turing machine, algorithmic language, finite automaton, logic, recursively coenumerable language, recursively enumerable language

@booklet{EasyChair:7718,
  author    = {Mark Burgin},
  title     = {New Languages of Abstract Automata},
  howpublished = {EasyChair Preprint 7718},
  year      = {EasyChair, 2022}}