|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010201,
author = {Igor Ban\'{\i}k},
title = {Colonies as Systems of Turing Machines Without States},
journal = jalc,
year = 1996,
volume = 1,
number = 2,
pages = {81--96},
keywords = {colonies, Turing machine, generative power},
abstract = {The paper aims to propose a system of recognizing
machines as a counterpart of colonies of grammars. After
presenting two unsuccessful approaches, the author proposes
systems of Turing machines without states as an adequate
model. The class ${\cal L}_{WS}$ of languages recognized by
single Turing machines without states, as well as the class
recognized by systems of such machines, is investigated. It
is shown that the class ${\cal L}_{WS}$ does not fit into
the Chomsky hierarchy. Systems of Turing machines without
states are proved to have the same generative power as
conventional Turing machines.}
}