Turing machines and bimachines

• Type: Article in International Scientific Journal
• Date: 2008

Authors

John Rhodes (Author) Other; Pedro V. Silva (Author) FCUP

Journal

Title: Theoretical Computer Science

Vol. 400

Pages: 182-224

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 4 Citations

ISI Web of Science

Scopus - 3 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 43