Natural limitations of decisions procedures for arithmetic with bounded quantifiers.
Nondeterminism is essential for reversal-bounded two-way multihead finite automata
On a certain event recognizable in real time
On real-time Turing machines
On the complexity of the word problem for finitely presented commutative semigroups.
Propriétés de complexité pour une famille d'algorithmes de Markov
Some problems in automata theory which depend on the models of set theory
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L(x1d49c;) accepted by a Büchi 1-counter automaton x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton x1d49c; such that the cardinality of the complement L(𝒜) − of the ω-language L(𝒜) is not determined...
Some problems in automata theory which depend on the models of set theory
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L(𝒜) accepted by a Büchi 1-counter automaton 𝒜. We prove the following surprising result: there exists a 1-counter Büchi automaton 𝒜 such that the cardinality of the complement L(𝒜) − of the ω-language L(𝒜) is not determined by ZFC: (1) There is a model V1...
Some remarks on multihead automata
The difference and truth-table hierarchies for NP
The observational predicate calculus and complexity of computations (Preliminary communication)
Wadge degrees of -languages of deterministic Turing machines
We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
Wadge Degrees of ω-Languages of Deterministic Turing Machines
We describe Wadge degrees of ω-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξω where ξ = ω1CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
What machines can and cannot do.
In this paper, the questions of what machines cannot do and what they can do will be treated by examining the ideas and results of eminent mathematicians. Regarding the question of what machines cannot do, we will rely on the results obtained by the mathematicians Alan Turing and Kurt G¨odel. Turing machines, their purpose of defining an exact definition of computation and the relevance of Church-Turing thesis in the theory of computability will be treated in detail. The undecidability of the “Entscheidungsproblem”...
Алгорифмы Колмогорова сильнее машин Тьюринга
Временная сложность многомерных машин Тьюринга
Вычисление эффективных операторов на машинах Тьюринга с ограниченным стиранием
Вычисления на машинах Тьюринга в конечно-аксиоматизируемых теориях.
Вычисления с оракулами: обобщённая селекция.
Вычислимость с двуместным оракулом.