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.
Язык оригиналаанглийский
Страницы (с-по)72–74
ЖурналVestnik St. Petersburg University: Mathematics
Том48
Номер выпуска2
DOI
СостояниеОпубликовано - 2015
Опубликовано для внешнего пользованияДа

Fingerprint Подробные сведения о темах исследования «Mutual Upper Bounds of Size and Time for a Turing Machine and a Markov–Post Algorithm for Mutual Simulations». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать