Efficient simulations between a wide class of computation models—including Turing machine variants with multiple heads, tapes, and auxiliary storage—have been found.

e. that of effective computability. It is also natural to ask whether the concept of feasible computability described in Section 1 itself admits a mathematical analysis similar to Church’s Thesis. We saw above that \(\sc{FACTORIZATION}\) is an example of a problem of antecedent mathematical and practical interest for which more efficient algorithms have historically been sought. The task of efficiently solving combinatorial problems of the sort exemplified by \(\sc{TSP}\), \(\sc{INTEGER}\