Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2008.03.019 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
new algebraic notion,limit behavior,algebraic profinite description,double semidirect product,iterated block product,deterministic Turing machine,upper triangular matrix,Cook’s theorem,Turing machine,Bimachine,Complexity,matrix multiplication,certain semigroups | Journal | 400 |
Issue | ISSN | Citations |
1-3 | Theoretical Computer Science | 1 |
PageRank | References | Authors |
0.36 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Rhodes | 1 | 89 | 20.04 |
| Pedro V. Silva | 2 | 141 | 29.42 |