Мат. логика

41.Разрешимость и перечислимость множеств. Следствие теоремы Тарского.

Пусть N = {0,1,2,…,n,…}, Nn = N*N*…*N. Будем рассматривать функции y = f(x1,…,xn), задающие

отображение: f: Nn → N

Как обычно: Df = {( x1,…,xn) | f(x1,…,xn) - определена};

If = {y | Ǝ x1,…,xn (f(x1,…,xn) = y)}.

Определение. Функция f(x1,…,xn) называется вычислимой, если существует алгоритм, позволяющий вычислять её значения для тех наборов аргументов, для которых она определена, и работает вечно, если не определена.

Следует помнить, что алгоритм и вычисляемая им функция – это не одно и то же. Одна и та же функция может вычисляться с помощью разных алгоритмов.

Пусть МNn = N*N*…*N.

Определение. Множество М называется разрешимым, если существует алгоритм Ам, который по любому объекту а дает ответ:

А ϵ М или А не ϵ М.

Алгоритм Ам называется разрешающим алгоритмом для М. Если Хм (x1,…,xn) =

Отсюда ясно, что М разрешимо тогда и только тогда, когда Хм вычислима. Пусть теперь МN.

Определение. Множество МN называется (рекурсивно, эффективно, алгоритмически) перечислимым, если М либо пусто, либо есть область значений (= М) некоторой вычислимой

функции ψм (х) или, другими словами, если существует алгоритм для последовательного перечисления (порождения) всех его элементов.

А ϵ М тогда и только тогда, когда Ǝх (а = ψм (х)).

Пример. Рассмотрим множество М = {0, 1,4,9,16,25,…} квадратов натуральных чисел. Оно перечислимо, так как существует вычислимая функция ψм (х) = x2, а М = {12, 22, 32, 42, …}. Это множество к тому же и разрешимо: чтобы проверить, принадлежит или нет некоторое число данному множеству, нужно разложить число на простые множители, что позволяет выяснить, является ли оно точным квадратом.

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

Теорема. Если множества М и L перечислимы, то перечислимы множества М U L и M∩L. Доказательство. Если множества M и L перечислимы, то существуют алгоритм Ам, который

последовательно порождает элементы l1, l2,… множества М U L. Следовательно, множество М U L перечислимо.

Алгоритм АМ U L также поочередно с помощью алгоритмов Ам и АL порождает элементы m1, l1, m2, l2,… При этом каждый вновь порожденный элемент mi сравнивается со всеми ранее порожденными элементами lj (j=1,…,i-1).

Если mi совпадает с одним из них, то он включается во множество M∩L. В противном случае надо переходить к порождению элемента l и сравнивать его со всеми mj (j=1,..,i-1) и т.д. Такая процедура позволяет перечислить все элементы множества M∩L, значит оно перечислимо.

Теорема. Пусть МN. Множество М разрешимо тогда и только тогда, когда оно само и его

дополнение перечислимы.

Доказательство. Необходимость. Пусть М – разрешимо. Можно считать, то М ≠ Ǿ, тогда имеется элемент а ϵ М. Если М – разрешимо, то характеристическая функция Хм – вычислима, т.е. имеется алгоритм для её вычисления.

Рассмотрим функцию: f(x) =

Отсюда М = {f(0), f(1), f(2),…}, т.е. М есть множество значений функции f, которая вычислима,

поскольку вычислима. Следовательно, М – перечислимо. Теперь возьмем элемент b не ϵ M и построим функцию:

g(x) =

которая также вычислима ввиду вычислимости . Нетрудно видеть, что

= {g(0), g(1), g(2),…}, т.е. – перечислимо.

Достаточность. Пусть множества М и перечислимы, т.е.

М = {f(0), f(1), f(2),…}, а = {g(0), g(1), g(2),…}, где f и g – некоторые вычислимые функции. Нетрудно построить алгоритм, который последовательно порождает элементы f(0), g(0), f(1), g(1), f(2), g(2),… и на каждом шаге порождаемый элемент сравнивает с произвольно заданным числом а. Поскольку а

должно принадлежать либо М, либо , то на конечном шаге получим либо f(k) = a, либо g(k) = a.

Если f(k) = a, то а ϵ M, а если g(k) = a, то а ϵ и, значит, а не ϵ M. Следовательно, множество М разрешимо.

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

….. ….. …..

…..….. …..

Перечисление осуществляется последовательным прохождением по диагоналям, начиная с левого верхнего угла. Можно доказать, что пара (m,n) имеет номер

С(m,n) =

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

Теорема. Существует перечислимое, но неразрешимое множество натуральных чисел. Доказательство. Для доказательства теоремы достаточно привести пример такого множества U

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

количество. Следовательно, все перечислимые множества можно расположить в последовательности (перенумеровать): М0, М1, М2,…

Более того, можно считать, что эта нумерация эффективна, то есть по номеру множества можно восстановить само это множество.

Рассмотрим теперь алгоритм АU, который последовательно порождает все элементы следующего множества U. На шаге с номером С(m,n) этот алгоритм вычисляет m-й элемент множества Mn, и если элемент совпадает с n, то он относит его в множество U.

Таким образом, n ϵ U тогда и только тогда, когда n ϵ Mn.

Итак, U порождается алгоритмом АU, т.е. U перечислимо. Поскольку дополнение множества U состоит из всех таких n, что n не ϵ Mn, то отличается от любого перечислимого множества хотя бы одним элементом. Поэтому – неперечислимо, а U – неразрешимо.

Доказанная теорема проливает свет на теорему Тарского, которая является более сильной теоремой, чем теорема Гёделя о неполноте.

Приведем без доказательства следствие теоремы Тарского.

Множество номеров формул истинных арифметических высказываний неперечислимо. (Не то, что неразрешимо, а даже неперечислимо).

Перефразируя образное изречение Квайна, можно сказать, что формальные системы попытались проглотить больший кусок онтологии, чем они в состоянии переварить.

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

42. Нумерация машин Тьюринга.

Рассмотрим конечный алфавит: Аст = {λ, |, q, П, Л, Н} и назовет его стандартным.

Все символы бесконечных последовательностей q0, q1, q2,… и a0(λ), a1, a2,… выразим словами конечного стандартного алфавита Аст:

qi (i = 0,1,2,…) закодируем словом из i+1 букв q: q0 – q; q1 – qq; q2 – qqq и т.д. aj (j = 1,2,…) обозначим словом из j палочек: a1 - |, a2 - || и т.д.

Это позволит нам любую программу машины Тьюринга записать в виде одного слова в алфавите Аст. Например, программу МТ:

q1a0 → q2a0П, q1a1 → q1a1П, q2a0 → q0a1Н, q2а1 → q2a1П можно закодировать одним словом: q q λ q q q λ П q q | q q | П q q q λ q | Н q q q | q q q | П.

Существует алгоритм, позволяющий узнать: является ли заданное слово в алфавите Аст программой некоторой МТ или нет?

Для этого нужно анализировать все подслова данного слова, заключенные между всевозможными парами букв из {П,Л,Н}. Эти подслова должны иметь единую структуру:

(q…q)( λ / 1…1)(q…q)( λ / 1…1).

Ясно, что каждая МТ вполне определяется некоторым конечным словом в алфавите Аст.

Поскольку множество всех конечных слов в конечном алфавите счетно, то и всех мыслимых МТ имеется не более чем счетное множество.

Перенумеруем теперь все МТ, для чего, работая в шестеричной системе счисления (символы: λ,1,q,П,Л,Н) составим счетно-бесконечную последовательность слов длины 1,2,3,…:

λ 1 q П Л Н λ λ λ 1 λ Н H H λ λ λ H H H

Обозначим эту последовательность слов как β0, β1, β2, … , βj, …

Дальше от этой последовательности слов перейдем к последовательности α0, α1, α2,…, αi,… по следующему правилу:

α0 – первое слово в последовательности β0, β1, …, являющееся МТ (пусть это βj0).

α1 – первое слово в последовательности βj0+1, βj0+2, …, являющееся МТ (например, это βj1) и т.д.

Последовательность α0, α1, α2,… - это последовательность программ всех мыслимых машин Тьюринга. Число n будем называть номером машины Тьюринга, если программа этой машины записывается словом αn.

Машина Тьюринга с номером n реализует некоторый алгоритм (обозначим его Аn).

Таким образом, существует вычислимая функция φ, которая по номеру n позволяет определить алгоритм Аn и наоборот по заданному алгоритму Аn позволяет найти его номер. Т.е. φ(n) = Аn, φ(Аn) = n.

Это означает, что множество всех МТ (всех алгоритмов) счетно.

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

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

Доказательство. Рассмотрим функции f(x), где х = 0,1,2,…; f = 0,1,2,… Причем 0 - |, 1 - ||, 2 - ||| и т.д. Докажем, что множество всех числовых функций f(x) несчетно.

Пусть f(x) = 0/1. Допустим, от противного, что это множество счетно. Тогда их можно занумеровать f0, f1, f2,…

Определим функцию f(n) =

Эта функция отлична от любой функции fi, i ϵ N.

Следовательно, нельзя занумеровать все функции, принимающие значения 0 и 1, значит, это множество функций несчетно. А так как оно – подмножество всех числовых функций, то и множество всех числовых функций несчетно. Оно имеет мощность континуума.

Напоминание. Континуум – гипотеза.

Мощность континуума – наименьшая, превосходящая мощность счетного множества, и промежуточных мощностей между счетным множеством и континуумом нет.

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

Пример. Пусть А = {1}. Слово α = ||…| = |n.

Зададим функцию: ψ(α) =

Функция ψ(α) не вычислима по Тьюрингу.

Доказательство. Допустим противное. Это означает, что существует МТ Т, вычисляющая эту функцию. Пусть К – номер этой машины в нумерации, описанной выше. Предположим, что машина Тьюринга перерабатывает α = |k в слово βк. Тогда по определению вычислимости функции ψ(α) на машине Тьюринга это означает, что ψ(|k) = βк. С другой стороны, по определению функции ψ(α) имеем ψ(|k) = βк |. Противоречие. Значит, что ψ(α) не вычислима.

44. Проблемы распознавания самоприменимости и применимости.

Предположим, что на ленте МТ записана её собственная программа, закодированная в алфавите машины.

Если машина применима к такой конфигурации, то будем называть её самоприменимой, в противном случае – несамоприменимой.

Проблема распознавания самоприменимости формулируется так: по заданной программе МТ установить, к какому классу относится машина: к классу самоприменимых или к классу несамоприменимых машин.

Теорема. Проблема распознавания самоприменимых машин Тьюринга алгоритмически не разрешима.

Доказательство. Предположим, что алгоритм для такого распознавания существует. Это означает, что существует МТ, которая реализует данный алгоритм. Пусть Т – такая машина.

На ленту машины Т заносится соответствующим образом закодированная программа той или иной МТ. При этом, если машина самоприменима, то занесенное слово перерабатывается машиной Т в символ σ, что означает ответ «да». Если же машина несамоприменима, то занесенное на ленту слово перерабатывается машиной Т в символ τ, означающий ответ «нет».

Из машины Т, модифицируя её, построим машину Т, которая после выработки символа σ вместо остановки продолжает его неограниченно повторять.

Однако, машина Т' невозможна, так как возникает противоречие.

1.Если машина Т’ самоприменима, то работая как машина Т, она выработает символ σ и зациклится, что означает, что она несамоприменима. Противоречие.

2.Если машина Т’ несамоприменима, то работая как машина Т, она выработает символ τ и остановится. Это означает, что машина Т’ самоприменима. Противоречие.

Так как невозможна машина Т’, то невозможна и машина Т, что и доказывает теорему.

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

можно было бы узнать, применима ли машина к слову, кодирующему её собственную программу, то есть самоприменима ли она. Но из предыдущей теоремы известно, что такого алгоритма не существует.

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

45. Теорема Райса.

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

Пусть, по-прежнему φ – некоторая нумерация алгоритмов, то есть

φ(х) = Ах, φ-1(Ах) = х, х = 0,1,2,…

Кроме того, алгоритм Ах вычисляет функцию fx.

Теорема Райса. Пусть С – любой непустой собственный класс вычислимых функций от одного аргумента (существуют как функции, принадлежащие С, так и вычислимые функции, не принадлежащие С). Тогда множество М = {x | f(x) ϵ C} неразрешимо.

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

Хм(х) =

Пусть f0 – нигде не определенная функция. Рассмотрим случай 1: f0 не ϵ C.

Выберем какую-нибудь конкретную вычислимую функцию fa ϵ C и определим функцию F(x,y):

F(x,y) =

Функция F(x,y) вычислима. Для её вычисления надо вычислять : если определена, то этот

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

, каковой она по определению и является.

Зафиксируем в функции F(x,y) аргумент х. Тогда F станет вычислимой функцией от одного аргумента

у.

Номер этой функции в единой нумерации φ зависит от значения х, то есть является всюду определенной функцией g(x).

Функция g(x) вычислима, так как g(x) = φ-1(F(x,y)), а F и φ-1 – вычислимые функции. Таким образом, F(x,y) = fg(x)(y) и, значит,

fg(x)(y) =

Отсюда следует, что

Это означает, что g(x) ϵ М тогда и только тогда, когда определена. Используя характеристическую функцию Хм от аргумента g(x), можно записать:

Хм(g(x)) =

Поскольку Хм и g – вычислимые функции, то последнее равенство означает, что мы для каждого

номера х можем выяснить, определено значение или нет. Так как определена тогда и только тогда, когда Ах(х) применим, то это, в свою очередь, означает, что построена разрешающая функция Хм(g(x)) для проблемы самоприменимости алгоритма, что невозможно. Поэтому, наше исходное предположение, что множество М разрешимо, не верно, то есть М – неразрешимо.

Рассмотрим случай 2: f0 ϵ C. Выбрав fa не ϵ С можно провести аналогичные рассуждения и выйти к разрешающей функции 1 - Хм(g(x)) для проблемы самоприменимости, что также противоречит доказанной ранее неразрешимости этой алгоритмической проблемы. Теорема доказана.