О порядке следования команд в программах элементарных машин Тьюринга степени 2

Abstract

Рассматривается одноленточная машина Тьюринга с внешним алфавитом, состоящим из двух символов. Программа машины задаётся списком команд. Определяется, каким образом машина отыскивает очередную команду в своей программе, которую она должна выполнять. Определяется оптимальный порядок следования команд в программе как порядок, при котором время их отыскания будет наименьшим. Под наименьшим понимается наименьшее среднее время как отношение суммы времени отыскания по всем начальным конфигурациям к числу этих конфигураций. Исходя из структуры программы машины, заданной графом, определяются элементарные машины Тьюринга степени 2. Для элементарных машин степени 2 указан оптимальный порядок следования команд и определено минимальное время их отыскания.