Операции над машинами Тьюринга.

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

Остается договориться о некоторых условностях для того, чтобы это определение стало до конца точным.

Во-первых, напомним, что речь идет о функциях (или возможно о частичных функциях, т. е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения.

Во-вторых, нужно условиться, как записывать на ленте машины Тьюринга значения х1,, х2,..., х_п аргументов функции f(x1, x2,..., хп), из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции.

Это можно делать, например, следующим образом. Значения х1,, х2,..., хп аргументов будем располагать на ленте в виде следующего слова:

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

I_х = , 0_х = .

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

Таким образом, предыдущее слово можно представить следующим образом: . Далее, начинать переработку данного слова будем из стандартного начального положения, т.е. из положения, при котором в состоянии q1 обозревается крайняя правая единица записанного слова.

Если функция f(x1, x2,..., хп) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f(x1, x2,..., хп) единиц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сформулированное определение 1 становится абсолютно строгим.

Вычислимость по Тьюрингу частично-рекурсивных функций

Теорема. Если функцияf(x,y) правильно вычислима на машине Тьюринга, то и функция φ(x)=μy[f(x,y)=0], получающаяся с помощью оператора минимизации из функцииf(x,y), также правильно вычислима на машине Тьюринга.

Следствие. Всякая частично рекурсивная функция вычислима по Тьюрингу.

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

Это совпадение будет означать, что понятие нормально вычислимой функции равносильно понятию функции, вычислимой по Тьюрингу, а вместе с ним и понятию частично рекурсивной функции.

Теорема1. Всякая функция, вычислимая по Тьюрингу, будет также и нормально вычислимой.

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

Таким образом, класс нормально вычислимых функций совпадает с классом функций, вычислимых по Тьюрингу.

Элементы теории игр. Понятие об игровых моделях. Нижняя и верхняя цены игры. Принцип минимакса. Вполне определенные игры, не содержащие седловой точки. Решение игр в смешанных стратегиях. Геометрическая интерпретация игры 2x2.

Математические методы анализа конфликтных ситуаций объединяются под названием теории игр, сама конфликтная ситуация носит название игры, а стороны, участвующие в конфликте, называются игроками. Исход игры называется выигрышем (или проигрышем) игроков. Если в игре участвуют только два игрока, то игра называется парной. Будем рассматривать в дальнейшем только парные игры. Если выигрыш одного игрока равен проигрышу другого, то игра называется антагонистической.

Величина a называется нижней ценой игры или максимином. Это гарантированный выигрыш игрока А. С другой стороны, игрок В выбирая свою стратегию В _j понимает, что игрок А ответит такой стратегией А_i, чтобы его выигрыш был максимален. Поэтому из наилучших вариантов для А (максимальных элементов каждого столбца) игроку В рационально выбрать свою стратегию, соответствующую минимальному из этих чисел: .

Величина β называется верхней ценой игры или минимаксом. Это максимальный проигрыш игрока В. Реальный результат решения конфликтной ситуации, называемый ценой игры n, заключен между верхней и нижней ценой: . В случае, если верхняя и нижняя цены совпадают , то игра имеет решение в чистых стратегиях, то есть можно точно определить стратегии , которые выгодны для обоих сторон. Если одна сторона отойдет от своей оптимальной стратегии, то ее выигрыш от этого только уменьшится.

Вполне определенные игры называют играми с седловой точкой. Элемент в матрице такой игры является одновременно минимальным в строке , максимальным в столбце и называется седловой точкой. Седловой точке соответствуют оптимальные стратегии игроков, их совокупность – это решение игры, которое обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого отклонение от его оптимальной стратегии не может быть выгодно. Точка называется седловой из-за формы графика функции выигрыша в точке , которая напоминает седло, убывая при изменении одной из переменных и возрастая при изменении другой переменной. Необходимо отметить, что в случае, если цена антагонистической игры равна 0, игра называется справедливой.

Смешанной стратегией S_A игрока А называется применение чистых стратегий A₁, A₂,..., A_m с вероятностями p₁, p₂,..., p_i,..., p_m причем сумма вероятностей равна 1: Смешанные стратегии игрока А записываются в виде матрицы

или в виде строки S_A = (p₁, p₂,..., p_i,..., p_m) Аналогично смешанные стратегии игрока В обозначаются: , или, S_B = (q₁, q₂,..., q_i,..., q_n), где сумма вероятностей появления стратегий равна 1:

Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S^*_A, S^*_B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: α ≤ v ≤ β, где α и β — нижняя и верхняя цены игры.

Решение игры 2×2 допускает наглядную геометрическую интерпретацию. Пусть игра задана платежной матрицей Р = (a_ij), i, j = 1, 2. По оси абсцисс (рис. 3.1) отложим единичный отрезок A₁ A₂ точка A₁(х=0) изображает стратегию A₁, а все промежуточные точки этого отрезка — смешанные стратегии S_A первого игрока, причем расстояние от S_A до правого конца отрезка — это вероятность p₁ стратегии A₁, расстояние до левого конца — вероятность p₂ стратегии A₂. На перпендикулярных осях I — I и II — II откладываем выигрыши при стратегиях A₁ и A₂ соответственно. Если 2 -й игрок примет стратегию B₁, то она дает выигрыши a₁₁ и a₂₁ на осях I — I и II — II, соответствующие стратегиям A₁ и A₂. Обозначим эти точки на осях I—I и II—II буквой B₁. Средний выигрыш v₁, соответствующий смешанной стратегии S_A, определяется по формуле математического ожидания v₁ = a₁₁ p₁ + a₂₁ p₂ и равен ординате точки M₁, которая лежит на отрезке B₁ B₁ и имеет абсциссу S_A (рис. 3.1).

Рис. 3.1	Рис. 3.2

Аналогично строим отрезок B₂B₂, соответствующий применению вторым игроком стратегии B₂ (Рис. 3.2). При этом средний выигрыш v₂ = a₁₂ p₁ + a₂₂ p₂ — ордината точки M₂. В соответствии с принципом минимакса оптимальная стратегия S*_A такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум. Ординаты точек, лежащих на ломаной (рис. 3.3 в примере 3.4.1), показывают минимальный выигрыш игрока А при использовании им любой смешанной стратегии (на участке B₁ N — против стратегии B₁ , на участке NB₂ — против стратегии B₂). Оптимальную стратегию S*_A = (p*₁ , p*₂) определяет точка N, в которой минимальный выигрыш достигает максимума; ее ордината равна цене игры v. На рис. 3.3 (пример 3.4.1) обозначены также верхняя и нижняя цены игры α и β.