Доказательство алгоритмической неразрешимости

Доказательство от противного. Допустим, что алгоритм, распознающий самоприменимость, существует. На основании тезиса Тьюринга существует и машина Тьюринга, реализующая этот алгоритм. Обозначим такую машину как . На её ленту заносится каким-либо образом закодированная программа другой машины Тьюринга, а после работы занесённые данные перерабатываются в какое-то слово , если исходная программа была самоприменима, или в слово , если она была несамоприменима.

Вторым шагом немного модифицируем машину так, чтобы она по-прежнему перерабатывала несамоприменимые программы в , а на самоприменимых программах зацикливалась, то есть являлась неприменимой к ним. Сделать подобное преобразование очень легко — после записи слова машина не заканчивает работу, а продолжает бесконечно записывать его на ленту. Обозначим эту машину как . Существование такой машины приводит к противоречию, потому что не может быть ни самоприменимой, ни несамоприменимой. Действительно, если самоприменима, то она применима к собственной записи. Но по построению машины это свидетельствует как раз о том, что несамоприменима. Если же несамоприменима, то по построению она применима к собственной записи, так как она применима к любой записи несамоприменимой машины. Но это как раз означает, что самоприменима. Исходя из этого делается вывод о невозможности построения машины , поскольку тогда из неё легко можно было бы получить .

17

Доказательство — логическая форма мысли, обосновываю­щая истинность того или иного положения посредством других положений, истинность которых уже обоснована или самоочевидна; - это логическая операция обоснования истинности какого-либо суждения с помощью других истинных и связанных с ним суждений. Таким образом, доказательство – это одна из разновидностей процесса аргументации, а именно аргументация, устанавливающая истинность суждения на основе других истинных суждений.

Доказательство в логике отличается от доказательства в повседневной жизни. В обыденности доказательство – это факты, с помощью которых обосновывается истинность какого-то положения, т.е. саму действительность. Логика же исследует доказательство только как мысленную структуру, как форму мысли, как конструкцию логически связанных между собой нескольких мыслей, обосновывающих исходную мысль; как форму более сложную, чем умозаключение, так как доказательство может состоять из нескольких умозаключений.

Аргументация -  операция  обоснования каких-либо суждений, в которой наряду с логическими применяются также речевые, эмоционально-психологические и другие внелогические методы и приемы убеждающего воздействия. Теория аргументации – комплексное учение о наиболее эффективных в коммуникативном процессе логических и внелогических методах и приемах убеждающего воздействия.] Доказательство состоит из:  тезиса (доказываемое положение);  аргументов (основания, посылки, т. е. положения, которые используются для обоснования тезиса);  демонстрации (связи тезиса и аргументов; способ доказательства). Логика естественного вывода позволяет строить формальные доказательства, структура которых наиболее точно передаёт логическое строение обычных рассуждений. Натуральные исчисления были изобретены независимо друг от друга С. Яськовским и Г. Генценом в 30ые гг. XXв. Система естественного вывода содержит правила логического следования (модус поненс, введение и удаление конъюнкции, введение и удаление дизъюнкции), правила построения доказательства (в том числе правила построения прямого и косвенного доказательства) и определение доказуемой формулы.

15

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

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

Вер­немся к интуитивному представлению об алгоритмах: одно из свойств алгоритма заключается в том, что он представляет собой единый способ, позволяющий для каждой задачи из некоего бесконечного множества задач за конечное число шагов найти ее решение.

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

Остается уточнить, что значит уметь вычислять значения фун­кции. Это значит вычислять значения функции с помощью подхо­дящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых, обширный опыт показали, что такой класс функций чрезвычай­но широк. Каждая функция, для вычисления значений которой существует какой-нибудь алгоритм, оказывалась вычислимой по­средством некоторой машины Тьюринга. Это дало повод Тьюрин­гу высказать следующую гипотезу, называемую основной гипоте­зой теории алгоритмов, или тезисом Тьюринга: Для нахождения значений функции, заданной в некотором алфави­те, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т. е. когда она может вычисляться на подходящей машине Тьюринга. Это означает, что строго математическое понятие вычислимой (по Тьюрингу) функции является по существу идеальной моде­лью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, выдвигаемый нами, о взаимо­связях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же данный тезис в прин­ципе не может быть доказан методами математики, потому что он не имеет внутриматематического характера (одна сторона в тези­се — понятие алгоритма — не является точным математическим понятием). Он выдвинут исходя из опыта, и именно опыт под­тверждает его состоятельность. Точно так же, например, не могут быть доказаны и математические законы механики; они открыты Ньютоном и многократно подтверждены опытом.

16 Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

В состав машины Тьюринга входит неограниченная (иногда ограниченная) в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называетсяголовкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

19

Тезис Маркова – принцип нормализации.Любой вербальный алгоритм в алфавите M может быть реализован некоторым нормальным алгорифмом над алфавитом M.

О том, что эти два тезиса справедливы (или не справедливы) одновременно, гласит следующая теорема.

Теорема 8.1. Для любой машины Тьюринга (Т) в алфавите М существует нормальный алгорифм (N) над алфавитом М такой, что для всех aÎМ^*, N(a)=Т(a).Для любого нормального алгорифма (N) в алфавите М существует машина Тьюринга (Т) над алфавитом М такая, что для всех aÎМ^*, Т(a)=N(a).

Еще один тезис теории алгоритмов звучит так.