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

Abstract

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