Turing machines and bimachines

• Tipo: Artigo em Revista Científica Internacional
• Data: 2008

Autores

John Rhodes (Autor) Outra; Pedro V. Silva (Autor) FCUP

Revista

Título: Theoretical Computer Science

Vol. 400

Páginas: 182-224

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 4 Citações

ISI Web of Science

Scopus - 3 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-003-YJM

DOI: 10.1016/j.tcs.2008.03.019

Abstract (EN): We associate the iterated block product of a bimachine with a deterministic Turing machine. This allows us to introduce new algebraic notions to study the behavior of the Turing machine. Namely, we introduce double semidirect products through matrix multiplication of upper triangular matrices with coefficients in certain semigroups, which leads in turn to the study of the iterations of bimachines. By passing to the profinite (or projective) limit, we obtain an algebraic profinite description of the limit behavior of the Turing machine. Finally, we analyze the proof that all languages in NP can be reduced to CIRCUIT sAT from this viewpoint.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 43