Mutual Upper Bounds of Size and Time for a Turing Machine and a Markov-Post Algorithm for Mutual Simulations

摘要

A Markov-Post algorithm and a Turing machine, which have mutual upper bounds on time and space, are proven to be interchangeable up to a linear function of space and a polynomial of time for the Turing machine, respectively. No more than two-letter extensions of the exterior alphabet are used.