Не понял вопроса, как и более раннего возражения по поводу памяти под программу. Роль теории в программировании никто не преуменьшает, всегда полезно знать, что происходит. Но всё же - связь здесь не прямая, результаты именно что можно заимствовать, но не применять напрямую. Почему у программистов не сносит крышу, если программе пытаются подсунуть для обработки данные, которые банально не умещаются в память? По поводу построения таблицы - очень просто, занесу в один столбец все возможные на входе строки, а во второй - ответ "да" или "нет". Алгоритмически всё легко реализуется операторами "if... then... else..."
Ну, допустим, вам нужно, скажем, вычислить колмогоровскую сложность(классический пример невычислимой функции) для всех двоичных строк длины не более
. Вполне определенная задача на конечном множестве.
Начнем с того, что таких строк
, и на каждую у вас в табличке один if, ну да ладно, пусть не
, пусть
. Всего-то ~1000 терабайт.
Но это не самое страшное. Для того, чтобы табличку построить, нужно эту сложность для каждой строки все-таки как-то узнать. Ну, это не общая проблема, можно придумать модель, у которой константа в теореме Чейтина достаточно большая и найти в ней сложность. Но это потребует просто огромного перебора. Жизни не хватит, чтобы эту программу построить.
-- Пн янв 11, 2010 00:20:25 --ау, люди, кто помнит простой и легко формулируемый для неспециалистов пример алгоритмически неразрешимой проблемы.
Так десятая проблема Гильберта же. Дано уравнение вида
,
- это полином. Определить, есть ли у него рациональные решения.