Решить эту проблему можно с помощью машины Тьюринга.Машины Тьюринга.Занимаясь проблемами эффективной вычислимости Тьюринг выделил класс абстрактных машин ( автоматов ), о которых выдвинул гипотезу о том, что они могут быть использованы для реализации («механической») любого вычислительного процесса. Эти абстрактные машины называются - машины Тьюринга.Машина Тьюринга: состоит из бесконечной в обе стороны ленты, которая разделена на ячейки, управляющего устройства, которое находиться в одном из возможных состояний. Число возможных состоянийуправляющего устройства конечно и определено.Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. В ячейки может быть записан выделенный символ - пустой символ , заполняющий все клетки ленты, кроме тех из них, на которых записаны входные данные.Управляющее устройство перемещается согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Машина Тьюринга определяется множеством букв или символов алфавита A, множеством состояний Q ( cдвумя выделенными символами: q0 – начальное состояние,qk – конечное состояние ) и набором правилР, по которым работает машина: qa→br, qa→bRrqa→bLr , q,rQ, a,bA, элементы Р называются командами, Р – программой МТ, для каждого состояния qQимеется только одна команда с левой частью qa, правил нет только для конечного состоянияqk, попав в которое машина останавливается. qa→bRr–записать в ячейку символ b, переместится вправо и перейти в состояние r, аналогично для команды qa→bLr, только переместится влево. Если состояние МТ равно qk она прекращает работу.Теорема. Всякая функцияf, вычислимая на машинa Тьюринга, является рекурсивной функцией, ( а следовательно является эффективно вычислимой ).Формально машинa Тьюринга представляет собой следующую систему M={ Q, S, P, q0, qk } и вычисляет функцию f(,Q = {, S={a0=, a1, …, an=| }.Тезис Тьюринга. Числовая функция fалгоритмически вычислиматогда и только тогда, когда функция является вычислимой по Тьюрингу, т.е. когда она может быть вычислена на некоторой машине Тьюринга.Теорема.Следующие классы функций (заданные на натуральных числах и принимающие натуральное значение ) совпадают:1. Класс всех функций вычислимых по Тьюрингу, 2. Класс всех рекурсивных функций.Класс всех эффективно вычислимых функций.Тезис Черча, Тьюринга:для любой вычислимой функции f существует алфавит Г и машина Тьюринга с алфавитом Г, которая вычисляет f.Пример универсальной вычислимой функции, нахождения решений системы линейных уравнений.Рассмотрим пример из введения и докажем, что задача нахождения решений системы линейных уравнений по теореме Крамера рекурсивна, а следовательно вычислима.Итак пусть задана система линейных уравнений n-го порядка расширенной матрицей, по теореме Крамера решение xi=Di/D, определители соответствующих матриц Di, D. Разложим функцию xi=Di/D на элементарные ( исходные ) примитивно рекурсивные функции.По теореме Лапласа Di=А11*а11+А12*а12+…+А1n*a1n, A1j – алгебраическое дополнение элемента а1j, алгебраическое дополнение это минор со знаком: A1j=M1j, M1j – это определитель на один размер меньше исходного. Следовательно согласно определениям и теоремам § 1 мы получаем на каждом шаге: - примитивно рекурсивная функция, сj*a1j=a - примитивно рекурсивная функция, ck*a1k=b - примитивно рекурсивная функция, a+b=d - примитивно рекурсивная функция, следовательно через конечное число шагов мы получим: Di, D–примитивно рекурсивные функции, следовательно xi=Di/D - примитивно рекурсивная функция, следовательно согласно тезиса Черча она вычислима, существует алгоритм U, который за конечное число шагов найдет значение xi.Для реализации этого алгоритма в виде вычислительного процесса, скажем в Excel, формально мы можем доопределить функцию xi=Di/D так, чтобы она стала всюду определенной:где а0 некоторый выделенный символ не принадлежащий множеству чисел, но принадлежащий области значений нашей функции, доопределенная таким образом функция стала эффективно вычислимой.Заключение.Рассмотрев основные свойства рекурсивных функций и воспользовавшись тезисом Черча, мы установили, что если удается доказать, что произвольная функция рекурсивна ( через разложение на исходные функции ) то она вычислима: существует алгоритм U, который за конечное число шагов выдаст значение функции для любого набора аргументов.Литература.Клини С.К. Математическая логика. –М.: Издательство Наука, 1987. – 336 с..Марков А.А. Элементы математической логики. –М.: Издательство Моск. Университета, 1984. – 80 с..Мендельсон Э. Введение в математическую логику. –М.: Издательство Наука, 1971. – 320 с..Новиков П.С. Элементы математической логики. –М.: Издательство Наука, 1971. – 400 с..Черч А. Введение в математическую логику. –М.: Издательство ИЛ, 1960. – 484 с..