From: abs@Lynx.com
Newsgroups: relcom.sci.philosophy
Subject: Конец света с точки зрения конструктивизма.
Date: Tue, 13 Apr 1999 00:44:34 GMT
Задела меня тема невычислимых функций,
особенно если учесть, что это то немногое, в чем я понимаю :-)
Возвращение к теме, которую обсуждала конференция
года полтора назад.
Итак.
Функция FI - это программа для машины Тьюринга.
M - машина Тьюринга.
D - некие исходные данные.
R - результат.
Сама функция вычисляет FI(D) -> R
Как она это делает? Исполняясь пошагово на машине:
M(FI, D) -> R
Ща начну коверкать определения, ибо последний раз видел их
год назад; но надеюсь что идею передам верно.
1. Функция вычислима, если для любого D существует R.
2. Функция невычислима, если для любого D машина зацикливается -
то есть работает вечно, меняет состояния, но НИКОГДА не проходит
через состояние "ОСТАНОВ" и никогда не выдает ответа.
Мы имеем конструктивную бесконечность.
3. Функция является частично вычислимой, если найдется D1,
на котором она невычислима и найдется D2, на котором она вычислима.
То есть множество входных данных можно (бы) разбить на два класса -
вычислимых (будет ответ) и невычислимых (ответа не будет).
Самая соль.
К сожалению, алгоритм разбиения множества исходных данных на классы;
равно как и алгоритм разбиения функций на классы вычислимых и нет -
сам НЕВЫЧИСЛИМ. Такой алгоритм должен производить некое тестирование
подсунутых ему данных и/или функций, иного способа по формальной
программе понять её смысл - НЕТ.
Но как только такой алгоритм решит проверить FI против некоего D из
числа невычислимых - всё немедленно навечно зациклится.
То есть алгоритм классификации невычислим, ибо "западает" на
неудобных входных данных.
Можно назвать это "непознаваемостью" в смысле "невозможно расклассифицировать
алгоритмы на вычислимые и не". Имея алгоритм (общего вида) нельзя сказать,
к какому классу он относится.
1. Если повезет и FI вычислима - алгоритм классификации остановится
за конечное время и скажет ДА, вычислима.
2. Если же FI невычислима (хоть где-то), алгоритм классификации
не остановится никогда и ответа НЕТ мы иметь не будем.
Причем, в случае 2) если мы находим, что алгоритм классификации работает
"слишком долго" - вовсе не значит, что "FI с большой вероятностью
невычислима". Это скорее значит, что "FI либо невычислима,
либо очень сложна". Алгоритм имеет право остановиться через миллиард лет,
и сказать ДА. А может не остановиться никогда. Поэтому оценки
A PRIORI должны быть отвергнуты, доверие (уверенность) - только A POSTERIORI.
Принцип Окамма, однако, предписывает людям любить ПРОСТЫЕ данные и
алгоритмы и отбрасывать сложные как маловероятные. Но это ЧЕЛОВЕЧЕСКОЕ
стремление к ясности, простоте и красоте. Столь сложное и хаотическое/сто-
хастическое по натуре образование как Вселенная может иметь алгоритмы ОЧЕНЬ
большой сложности, сопоставимой с числом степеней свободы Вселенной
(или даже 2^N). От "очень большой" до "бесконечной" или же "невычислимой" -
полшага. С бесконечностями, кстати, встанет вопрос о порядке бесконечностей -
счетное/несчетное/алеф1 итп.
ДЕТЕРМИНИЗМ
полагает, что алгоритм функционирования Вселенной -
функция вычислимая. То есть, имелось начальное образование (данные),
имелся начальный план - программа,
и функционируя по нему Вселенная когда-то остановится и
выдаст результат - свой Конец.
Такой алгоритм не обязательно обратим, то есть могут
существовать D1 != D2 : FI(D1) == FI(D2).
Но зато на каждом шаге t состояние Вселенной
предсказуемо по D, t и FI --> FI(D, t).
Отметим, что в силу необратимости (невзаимнооднозначности)
по t, по D(t) "сегодня", нельзя точно найти D(0) "исток",
хотя можно найти КЛАСС { D(0) } которые являются
подходящими или допустимыми. Однако, выбрать конкретный
элемент из { D(0) } мы не сможем. Если только теория не докажет,
что такой элемент ровно один.
Это рассуждение говорит, что теорий о Начале Мира может быть несколько
и даже (увы) непротиворечивых.
Хуже, если мы обнаружим, что { D(0) } - пустое :-(
НЕДЕТЕРМИНИЗМ
а что если Вселенная функционирует по невычислимому алгоритму?
Попросту говоря - после начального толчка она зациклилась.
Она живёт, то есть меняет свои состояния как клеточный автомат,
но в данном случае ВОЗМОЖНО это будет вечно, и конца не имеется.
Однако начало теоретически быть могло.
В данной модели конечного СМЫСЛА у Вселенной нет,
ибо её алгоритм не предполагает остановки и получения результата,
она ничего не вычисляет.
Смысл - раббота самой машины, и всё. ВСЁ.
МОЖНО ЛИ ОТЛИЧИТЬ?
Нельзя. Если алгоритм вычислим - однажды настанет конец света.
Если нет - не настанет никогда.
А построить пробник, прибор-измеритель для ответа на сей вопрос -
НЕЛЬЗЯ. Ибо сама задача о классификации - невычислима,
смотри выше. Даже если мы сочиним алгоритм, нет никакой
гарантии, что он не будет работать вечно.
Данный вопрос наполовину лишен смысла, то есть вопрос не имеет
ответа и есть непознаваемая тайна природы. СМЫСЛ его задавать -
есть. ОТВЕТА на него - нет.
Точнее так: ответ на него можно получить лишь ИСТОРИЧЕСКИ,
функционируя вместе со Вселенной, но не теоретически.
Ответ возможен лишь A POSTERIORI - когда машина Вселенной
остановится, если остановится - мы будем иметь ответ.
А если не остановится - то и ответа не будет,
и можно ждать сколько угодно, оставив вопрос открытым.
Когда же (и если) Вселенная кончится - для НАС сей вопрос
потеряет актуальность, смысл и значение, ибо вместе со Вселенной
перестанем функционировать (а значит и существовать) и мы.
Зато кто-от вовне (чего?) сможет прочесть ответ - результат
работы алгоритма. Назовём потребителя словом "Бог-заказчик"
(в отличие от Бога-творца) и на этом успокоимся, ибо про его
цели (зачем ему результат) из наших D и FI нельзя сказать
НИ-ЧЕ-ГО. Они не наделены некоей "присущей" внешней семантикой,
они работают исключительно ВНУТРИ машины.
(Вот вам о "качествах вещей самих по себе". Может они и есть,
но из рамок машины их не видно).
А может и результата нет (если алгоритм невычислим),
тогда и гипотеза Бога не нужна:
1. наша машина (точнее программа) бессмысленна.
2. Бог не всемогущ, ибо пишет программы,
не выдающие результатов. Press ^C.
Мог бы заранее объять необъятное и предсказать,
что алгоритм - невычислимая функция! А Он не :-)
А может как раз специально?
Можно еще саму машину назвать Богом-исполнителем,
ибо это она выполняет программу и воплощает тем самым
законы Вселенной.
Final Remarks.
1.
Это всё - не теорема Гёделя, а вовсе даже
"гёделевская нумерация программ" и тезис Чёрча.
2.
С критерием вычислимости дела обстоят так (в математике) -
известен класс функций, про которые ЗАВЕДОМО известно,
что они вычислимы. Это так называемые "рекурсивные функции".
Известны методы построения таких функций из начального
множества. Определения опустим. Класс этот неплохо изучен.
3.
Про ОСТАЛЬНЫЕ функции НИЧЕГО сказать A PRIORI нельзя.
Нужен опыт. Ответ - только A POSTERIORI.
Опыт же может стать бесконечным.
Поэтому для остальных функций в целом задача
классификации неразрешима.
Единственное, что можно предложить, это для каждой функции
выделить свою машину и запустить все это счетное множество
машин и программ в параллель. Некоторые остановятся скоро.
Некоторые проработают долго. Третьи - будут работать вечно.
По крайней мере два исхода (death or eternity).
That's it.
Thank me very much :-)
P.S. Наука опирается на факты, а не на теории.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own