Слово или цепочка употребляются в одном и том же смысле.
Алфавит – конечное, непустое множество символов.
V= {a1, a2, …, an}
Цепочкой в алфавите V называется конечный объект, получаемый выписыванием одного за другим символов из алфавита V.
Для V= {0, 1, 2, …, 9} цепочкой является натуральное число.
Длина цепочки есть количество символов в ней. |α| - длина цепочки.
Пустая цепочка не содержит ни одного элемента (ε) алфавита. Пустая цепочка не есть символ пробела.
Множество всех цепочек (включая и пустую) над алфавитом V обозначается V*.
n-местной словарной функцией над алфавитом V называется n-местная функция над множеством V*× V*×V*×V*×…×V*→V*.
В качестве двуместной словарной функции может выступать операция конкатенации. Цепочка γ называется подцепочкой цепочки α, если α представляет собой конкатенацию α=υγω, где ω,υ – возможные цепочки. При этом γ называется префиксом цепочки α, если цепочка υ пустая, или суффиксом, если ω пустая.
Существует взаимнооднозначное соответствие между неотрицательным целым числом и цепочкой в произвольном алфавите V. Символы алфавита V можно произвольным образом упорядочить, перенумеровать их числами {1,2,…,n}. Задаётся функция упорядочивания . Пустой цепочке поставим в соответствие число 0, а остальные цепочки упорядочим по следующим правилам.
Если |α|<|β|, то α располагается левее β.
Если цепочки имеют одинаковую длину, то они упорядочены в алфавитном порядке, т.е. с учётом порядковых номеров символов алфавита.
Порядковый номер цепочки в полученной записи последовательности задаёт соответствующее ему натуральное число, называемое числовым кодом цепочки. Обратное кодирование осуществляется тем же способом. Можно аналогичным способом установить взаимно однозначное соответствие между цепочками любых двух алфавитов.
Определённое ранее понятие функции не содержит указаний на то, как по заданному аргументу получить значение функции. Желательно переформировать определение так, чтобы оно содержало конструктивную процедуру или алгебраическое нахождение функции. Однако подобное определение будет приведённого ранее. Оно будет задавать некоторый подкласс функций, который называется вычислимыми функциями.
Тьюринг определил функции с помощью абстрактной математической машины, вычисляющей значение функции по значению её аргумента. Тезис Тьюринга состоит в том, что каждая функция, для которой составлен алгоритм нахождения её значений, представима некоторой машиной Тьюринга, т.е. является вычислимой; тезис Тьюринга не может быть доказан.
Машина Тьюринга T задаёт словарную функцию под некоторый алфавит V и представляет собой описание машины, т.е. набор объектов (V, Q, q0, #, I).
V – алфавит машины.
Q – алфавит состояний, .
q0– начальное состояние, .
# - пустой символ, .
I – программа машины Тьюринга.
Программа – конечное множество цепочек вида qa→q΄a΄d,которые называются командами.
В каждой цепочке
Предполагается, что в программе никакие две команды не могут иметь одинаковую пару одинаковых символов.
Функционирование машины Тьюринга может быть описано следующим образом. Предполагается, что машина Тьюринга работает с потенциальной бесконечной в обе стороны лентой управления, по которой перемещается считывающая - записывающая головка. Лента разбита на ячейки, в которых могут быть записаны символы из алфавита V или пустой символ #. Расшифровав программу, которая однозначно определяет поведение машины и управление головкой, мы получаем работу машины Тьюринга. Головка в каждый момент времени расположена напротив одной ячейки ленты. Символ, находящийся в ячейке, считывается, после чего машина Тьюринга записывает некоторый символ и, либо остаётся на месте, либо сдвигается влево или вправо.
Машина работает по программе следующим образом.
В начальный момент времени на ленте записывается некоторая цепочка из множества V*, все остальные клетки ленты заполнены символом #. Управление в начальный момент находится в состоянии q0, считывающая – записывающая головка обозревает крайний слева символ записанной цепочки. Работа машины состоит в повторе следующего цикла элементарных действий:
1. Чтение головкой символа из ячейки напротив неё.
2. Поиск применимой команды, а именно команды qa → q’a’d, где q-некоторое состояние управления, a-считываемый символ.
3. Выполнение найденной команды, которая состоит в следующем. В обозреваемую головкой ячейку записывается символ a’, символ a-стирается, управление переходит в состояние q’ и головка смещается относительно d. Если d=r головка смещается на одну ячейку вправо, если l - смещается на одну ячейку влево, p – перемещение не производится. Остановка производится в том случае, если на очередном шаге ни одна команда программы не является применимой. Результатом работы машины Тьюринга является цепочка, записанная на ленте.
. Пустой цепочке поставим в соответствие число 0, а остальные цепочки упорядочим по следующим правилам.
приведённого ранее. Оно будет задавать некоторый подкласс функций, который называется вычислимыми функциями.
.
.
.