Университет XXI века: научное измерение

Научная конференция научно-педагогических работников, аспирантов, магистрантов ТГПУ им. Л. Н. Толстого 190 q 1 1 0 1 q 2 1 0 1 0 q 3 1 0 1 0 0 q 0 1 0 1 0 1 , получаем представление о потенциальной бесконечности ленты, то есть воз- можности при необходимости слева или справа приписать новую ячейку, за- полненную автоматически пустым символом. При этом преобразование можно записать при помощи конфигураций 10q 1 1 → 101q 2 0 → 1010q 3 0 → 1010q 0 1. Таким образом, при помощи машины Тьюринга имеем практически иде- альную модель ЭВМ, имеющую бесконечную память в виде потенциально бес- конечной ленты и осуществляющую преобразования слов на битовом уровне, то есть при помощи преобразования ячейки. Это позволило выдвинуть тезис Тьюринга: функция вычислима (то есть существует алгоритм, вычисляющий её значения) тогда и только тогда, когда она вычислима по Тьюрингу. В качестве примера продемонстрируем вычислимость по Тьюрингу функ- ции сложения при помощи машины Тьюринга с программой: q 1 1q 2 0L, q 2 1q 2 1L, q 2 *q 2 *L, q 2 0q 3 1R, q 3 1q 3 1R, q 3 *q 3 *R, q 3 0q 1 0L, q 1 *q 0 0L, которую для удобства применения можно записать в виде таблицы: 0 1 * q1 q20L q00L q2 q31R q21L q2*L q3 q10L q31R q3*R Рассмотрим преобразование слова 111*1q 1 1 : 111*1q 1 1 → 111* q 2 10 → 111q 2 *10 → … → q 2 111*10 → q 2 0111*10 → 1q 3 111*10 → → 11q 3 11*10 → … → 1111*1q 3 0 → 1111*q 1 10 → … → 11111q 1 *00 → 1111q 0 10. Данная машина Тьюринга начальную стандартную конфигурацию для ар- гументов данной функции переводит в заключительную стандартную конфигу- рацию, воспринимающую при помощи читающей головки значение данной функции, то есть функция сложения вычислима по Тьюрингу. Другим уточнением понятия алгоритма является частичная рекурсивность вычислимых функций, что выражено в тезисе Чёрча (1937 г.). Для этого опре- деляются три исходных функции: нуль функция, функция следования и функ- ция индивидуализации, то есть выделения переменной, а также три оператора: суперпозиции (подстановки функций вместо переменных), примитивной рекур- сии (определение функции для 0 и каждого последующего значения аргумента) и − оператор (минимизации, так как определяет значение функции при помо- щи наименьшего значения аргумента, удовлетворяющего её условию). Таким образом, алгоритмически вычислимая функция получается выводимой из ис- ходных функций при помощи этих трёх операторов.