pipette
ENEnglish

Non-recursive trade-offs for two-way machines

Christos Kapoutsis

Preprint

En palabras de los autores

If the machines of some type A have enough resources to (i) solve problems that no machine of type B can solve, and (ii) simulate any unary two-way deterministic finite automaton that has access to a linearly-bounded counter, then typically no recursive function can upper bound the increase in the size of description when a machine of type A is replaced by an equivalent machine of type B.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: International Journal of Foundations of Computer Science, 16:943-956, 2005. Number of pages: 14. Number of figures: 0