10. Функции, вычислимые по Тьюрингу. Тезис Тьюринга

Рассмотрим следующий двухэлементный список внешних символов: . Представим натуральное число как слово, состоящее из единиц: . Числовая -местная функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая конфигурацию преобразует в конфигурацию с машинным словом , если функция определена и равна , и останавливается не в заключительном состоянии (нет команды для очередной конфигурации!) или не останавливается, если функция не определена.

Приведем примеры вычисления функций на машинах Тьюринга.

1) Функция следования вычислима по Тьюрингу. Действительно, эта функция вычисляется следующей программой машины Тьюринга: . Если на входе дано , то изменения конфигурации следующие: .

2) Нулевая функция вычислима по Тьюрингу. Пишем программу: . Изменения конфигурации ():

.

11. Одноместные функции, вычислимые по Тьюрингу

Одноместная функция f:N₀N₀ с областью определения DN₀ называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел xN₀

начальную конфигурацию преобразует в заключительную конфигурациюq₀1^y1, если xD и y=f(x),

и не выдает никакого результата, если xD.

Примеры. 1) Функция f(x)=x+2 вычислима по Тьюрингу.

Программа Тьюринга для функции f:

	_	1
1	1 Л 0	1 Л 1
2	1 Н 0

Преобразования конфигурации при x=2 (и y=4):

q₁111, q₁_111, q₂_1111, q₀11111.

2) Функция g(x)=1 вычислима по Тьюрингу.

Программа Тьюринга для функции g:

	_	1
1	1 Л 2	_ П 1
2	1 Н 0

Преобразования конфигурации при x=2 (и y=1):

q₁111, _ _ _q₁_, _ _ _q₂_1, q₀11.

12. Двухместные функции, вычислимые по Тьюрингу

Двухместная функция f:N₀N₀N₀ с областью определения DN₀N₀ называется вычислимой по Тьюрингу, если существует машина Тьюринга, которая для любых чисел x,yN₀

начальную конфигурацию преобразует в заключительную конфигурациюq₀1^z1, если (x,y)D и z=f(x,y),

и не выдает никакого результата, если (x,y)D.

Примеры. 1) Функция f(x,y)=x1 вычислима по Тьюрингу.

Программа машины Тьюринга для функции f(x,y)=x1:

x1	_	1
1	_ П 2	1 П 1
2	_ Н 3	_ П 2
3	_ Л 3	1 П 4
4	1 П 0

Преобразования конфигурации для f(x,y)=x1 при x=2, y=1, z=3:

q₁111_11, 111q₁_11, 111_q₂11, 111_ _ _q₂, 111_ _ _q₃,

11q₃1_ _ _, 11q₃1_ _ _, 111q₄, 111q₄, 1111q₀.

2) Функция z=xy вычислима по Тьюрингу.

Программа машины Тьюринга для функции z=xy:

xy	_	1
1	1 П 2	1 П 1
2	_ Л 3	1 П 2
3		_ Л 4
4		_ Л 0

Преобразования конфигурации для z=xy при x=2, y=1, z=3:

q₁111_11, 111q₁_11, 1111q₂11, 111111q₂, 11111q₃1, 1111q₄1_, 111q₀1_ _.