Границы программирования. Принципиальная и практическая неразрешимость

Введение в теоретическое программирование.

Каковы пределы автоматизации (замены интеллектуальной деятельности «машинной», точнее программой, написанной другими людьми)? Эти проблемы мы осветили в терминах области машинного моделирования интеллектуальной деятельности, традиционно называемой «искусственный интеллект» (ИИ). Задачи ИИ относят к самым сложным и самым необходимым.

Что такое интеллект? Как минимум – способность решать задачи. Чем умный решатель отличается от глупого? Умному достаточно постановки задачи, спецификации, он сам находит метод решения. Глупый лишь исполняет алгоритм, постановки задачи он может и не знать.

алгоритм

ответ

данные

алгоритм

спецификация ответ

данные

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

Использование рекурсии вместо циклов даёт языки более высокого уровня, хотя и менее эффективные. Чаще действует «золотое правило»: чем более универсален метод, тем менее эффективен он в каждом частном случае.

Можно ли сделать компьютер более умным?

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

Основная задача ИИ («проба пера») – построить универсальный решатель задач, написать алгоритм, который в качестве входа принимает текст постановки задачи на некотором формальном языке спецификации, а на выходе выдаёт программу её решения на некотором языке программирования. Трактовка задачи корректна.

Язык спецификации Язык программирования

Существуют универсальные языки программирования, например: Паскаль, язык блок-схем или Ассемблер. Существуют универсальные языки спецификаций.

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

Примеры:

1) Проблема остановки: нельзя написать программу, проверяющую по тексту входящей программы, зацикливается ли она:

а) на заданных значениях;

б) на некоторых значениях.

Либо язык не даёт зацикливаться, либо он неуниверсален.

2) Существуют синтаксические анализаторы, проверяющие по входному тексту программы, является ли она на самом деле выражением данного языка программирования.

Задача написать семантический анализатор неразрешима.

а) Написать программу, которая проверяет функциональную эквивалентность двух программ.

б) Написать программу, проверяющую, удовлетворяет ли данная программа заданной спецификации.

Доказательства сложны, но причина тривиальна – все они сводятся к задаче проверки бесконечного числа входов.

Уточним постановку: написать программу, которая по данной спецификации выдаёт решение задачи, либо строку «Нет решений».

Универсального решателя задач не существует. Существует большой круг решаемых задач. Более того, в некотором смысле это все задачи. Это конечные задачи с конечным числом входов, вариантов решения.

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

Для каждой ли задачи существует полиномиальное решение? В этом суть знаменитой ПНП-проблемы.

Вернёмся к постановке задачи…

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

Пример моделирования интеллектуальной деятельности – задача «Обезьяна и банан». Содержательная постановка: в комнате находятся обезьяна, ящик и подвешенный к потолку банан. Как обезьяне его достать?

Понятно, что если обезьяна может подойти к ящику, перенести его под банан, встать на ящик и сорвать банан, то она должна сделать именно это. Очевидно, этот случай неявной спецификации алгоритма, в которой по умолчанию подразумевается возможность действовать «как обычно», «как все делают».

А как делают все? Что такое комната-ящик-банан? Как берут ящик?

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

Дата добавления: 2014-01-05