Machines with more power can cause huge size increases in equivalent simpler machines
Non-recursive trade-offs for two-way machines
Formal Languages and Automata Theory
Summary
Some types of computing machines are much more powerful than others, meaning they can solve problems the simpler ones can't. The authors find that when you try to convert a powerful machine into a simpler one, the size of the description can explode beyond any predictable limit. This means there is no general way to estimate how big the simpler machine’s description will get. The study focuses on machines that use two-way reading and counters in a very specific way.
What this means in practice
- •For automata designers: Recognize that converting powerful two-way machines to simpler ones can lead to unpredictably large increases in description size, guiding architecture choices.
- •For compiler developers: Avoid expecting size-efficient translations from certain powerful machine models to simpler automata when optimizing low-level representations.
A theory result. No direct application yet.
Authors
Christos Kapoutsis
Abstract
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.