О порядке следования команд в программах элементарных машин Тьюринга степени 2 - Будько, А.Е. (Веснік Брэсцкага ўніверсітэта. Серыя 4. Фізіка. Матэматыка, 2021)
Рассматривается одноленточная машина Тьюринга с внешним алфавитом, состоящим из двух символов. Программа машины задаётся списком команд. Определяется, каким образом машина отыскивает очередную команду в своей программе, которую она должна выполнять. Определяется оптимальный порядок следования команд в программе как порядок, при котором время их отыскания будет наименьшим. Под наименьшим понимается наименьшее среднее время как отношение суммы времени отыскания по всем начальным конфигурациям к числу этих конфигураций. Исходя из структуры программы машины, заданной графом, определяются элементарные машины Тьюринга степени 2. Для элементарных машин степени 2 указан оптимальный порядок следования команд и определено минимальное время их отыскания.