Конспект установочных лекций по комплексному курсу Информатика, Теория информации




Разрешимость


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

Невычислимые функции

Все формализмы для представления алгоритмов позволяют представлять алгоритмы через конечные термы («программы»). Пусть PRG есть множество всех таких термов, которые представляют одноместные функции, например в нотации m-рекурсии. На самом деле PRG есть формальный язык. Для р Î

PRG обозначим через fp частичное отображение, вычисляемое программой р.

Все элементы р Î PRG есть слова над конечным множеством знаков и могут быть однозначно представлены («закодированы») с помощью натуральных чисел. Соответственно, существует инъективное отображение, гёделизация для PRG:

code: PRG -> N.

Существование такого кодирования получается тотчас из существования вычислимого, инъективного отображения, которое отображает конечные последовательности над “N в N. Например, мы можем

seqcode:N*àN

специфицировать через

seqcode(<n... nk>) = рn11 ,... ,рnkk

,

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

Теорема. Существует тотальная функция

g: -N->N,

которая не является вычислимой.

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

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




Содержание  Назад  Вперед