Вычислимые по Тьюрингу функции.

Определение 1. Ф-я наз-ся вычислимой по Тьюрингу, если существует машина Тью­ринга, вычисляющая ее, т.е. такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функ­ция для данного набора значений аргументов не определена.

Остается договориться о некоторых условностях для того, что­бы это определение стало до конца точным. Во-первых, напом­ним, что речь идет о функциях (или возможно о частичных фун­кциях, т. е. не всюду определенных), заданных на множестве нату­ральных чисел и принимающих также натуральные значения. Во-вторых, нужно условиться, как записывать на ленте машины Тью­ринга значения х₁,, х₂, ..., х_п аргументов функции f(x₁, x₂, ..., х_п), из какого положения начинать переработку исходного слова и, на­конец, в каком положении получать значение функции. Это можно делать, например, следующим образом. Значения х₁,, х₂, ..., х_п ар­гументов будем располагать на ленте в виде следующего слова:

Здесь полезно ввести следующие обозначения. Для натурально­го х обозначаем:

I^х = , 0^х = .

Дополнительно полагаем 0° = 1° = Ù — пустое слово. Так что на слова 1° = Ù, I¹ = 1, I² = 11, I³ = 111, ... будем смотреть как на «изображения» натуральных чисел 0, 1, 2, 3, ... соответственно.

Таким образом, предыдущее слово можно представить следую­щим образом: .Далее, начинать переработку дан­ного слова будем из стандартного начального положения, т.е. из положения, при котором в состоянии q₁ обозревается крайняя правая единица записанного слова. Если ф-я f(x₁, x₂,..., х_п) определена на данном наборе значений аргументов, то в резуль­тате на ленте должно быть записано подряд f(x₁, x₂, ..., х_п) еди­ниц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сфор­мулированное определение 1 становится абсолютно строгим.

Сконструировать машину Тьюринга — значит написать (соста­вить) ее программу. В этом процессе два этапа: сначала создается алгоритм вычисления значений функции, а затем он записывается на языке машины Тьюринга (программируется).