«останавливается ли данный алгоритм на данном входе»
Но нужно ведь представить общее решение проблемы останова (то есть представить один алгоритм, который эту задачу решает для всех случаев). Куда в Вашей формулировке все кванторы-то делись? В чем «неправильность формулировки» в статье по сравнению с Вашей формулировкой?
Про литературу вопрос сложный.
По алгоритмической теории информации ее много. Там сложность индивидуального объекта (строки) определяется как длина кратчайшей программы, которая печатает эту строку и останавливается.
Отсюда следует банальный вывод, что любая программа, которая печатает некоторый ответ и останавливается, не может породить строку, более сложную, чем она сама.
Интереснее рассмотреть вопрос, какой сложности строки может порождать безостановочная программа (и вот на этот счет с литературой как-то хуже). Очевидно, такая программа может порождать строки любой сложности!
Действительно, можно представить себе мата-алгоритм, который перебирает все прочие алгоритмы. Если такой мета-алгоритм должен остановиться, то в нем должен быть зашит некий критерий остановки, и чем сложнее тот алгоритм, который мы хотим породить на выходе, тем сложнее должен быть критерий остановки. В итоге все равно получим, что сложность ответа будет не выше сложности порождающего алгоритма с необходимым критерием. Скажем, если мы на выходе хотим получить алгоритм ИИ, то переборный останавливающийся алгоритм окажется не проще, чем этот самый ИИ!
Безостановочный же переборный алгоритм сможет породить все, что угодно на выходе, оставаясь при этом простым (естественно, останется вопрос, как из этого «всего, что угодно» будет выбираться «то, что нужно»).
Но это просто утрированный пример для демонстрации различий в сложности выхода, даваемого остановочными и безостановочными алгоритмами.
Ну, если читать только первый абзац статьи и выдирать фразу из контекста, то, конечно, найдется с чем спорить. Эта-то фраза в статье как раз и опровергается. Она здесь дается с ироническим оттенком и используется как антитезис.
Речь о том, что понятие аттракторов возникло для систем, описываемых дифференциальными уравнениями. Его расширение на дискретные системы возможно, но не особо интересно. Например, экспоненциальная расходимость для потоков — достаточно естественное представление, тогда как в случае алгоритмов оно весьма неестественно. Любой if...else… делает алгоритм «неустойчивым» с «мгновенной» расходимостью его ветвей. При куче if'ов у вас сразу будет существенная нелинейность (расходимость «почти в каждой точке») при том, что алгоритмический процесс будет «оставаться в ограниченной области фазового пространства». Для алгоритмов это достаточно банальная ситуация. Для любой сложной информационной системы это банальная ситуация. Странные аттракторы возникают даже в очень простых системах типа Лоренца. Поэтому описание работы мозга как странного аттрактора очень неспецифично… В этой связи и описание цели как аттрактора возможно, но не слишком продуктивно. В этом есть некоторый смысл, но не следует его слишком абсолютизировать. Однако это тоже тема для отдельного большого разговора.
>> Формальная математика не работает с реальным миром!!!
Мышлению просто не от чего отталкиваться, кроме как от реального мира. Даже если строится «экзотическая» система аксиом, она строится «в противовес» естественным свойствам.
Да Вы его сами и привели. Генератор псевдослучайных чисел — это простейший пример дискретной динамической системы, работающей в режиме странного (вернее, хаотического) аттрактора.
Вот видите, специалисты по функану в каждом конкретном случае для себя этот выбор делают. Этот выбор определяется контекстом применения соответствующей аксиоматики. Что Вам еще нужно?
Вовсе нет! Это как раз имеет прямую связь с сильным ИИ. Как раз простейшие расширения модели универсального алгоритмического интеллекта (типа AIXItl) что-то отдаленно похожее и делают.
Рассуждать же в терминах странных аттракторов, конечно, можно, но все же не слишком продуктивно. Эти странные аттракторы, которые в теории динамических систем выглядят почти что чудом, в теории алгоритмов достаточно заурядны (в силу существенной нелинейности алгоритмов).
Кое-что есть в книгах на нашем сайте ( aideus.ru/research/publications.html ), но там «много букв», и нет материала непосредственно в том виде, в котором есть желание об этом написать.
Чтобы говорить о памяти, нужно обсудить проблему универсального индуктивного вывода (и общее теоретическое решение проблемы машинного обучения). Тогда разговор о памяти будет гораздо более содержательным.
Мы планируем написать статьи на эти темы.
Пожалуйста и тоже спасибо.
Под программой в статье в основном понимается программа для машины Тьюринга, то есть тоже алгоритм.
Действительно, реальная работающая программа несводима к своей модели — алгоритму. В статье на это лишь намекается, но, возможно, следовало бы этот аспект обсудить в явном виде.
Что касается «хорошо проработанной теории алгоритмов», в действительности, это не совсем так (а, может, и далеко не так). Хорошо проработаны далеко не все ее аспекты. Кому надо переосмыслять эту теорию? Разработчикам моделей универсального ИИ. И некоторыми из них это, собственно, и делается. Особенно интересна связь теории алгоритмов и теории информации. Хотя алгоритмическая теория информации была развита Колмогоровым и Соломоновым достаточно давно, сейчас становится понятной необходимость обобщения алгоритмической сложности по Колмогорову с учетом вычислительной сложности (получается т.н. сложность по Левину)… В общем, тут масса всего интересного и еще непроработанного.
Так ведь не является аксиома выбора в ZF ни истинной, ни ложной. Добавлять ли ее или нет — вопрос полезности. Аксиоматика ZFC успешно применяется. Есть ли попытки рассмотреть, что получится в аксиоматике ZF!C? Может, там будет что-то интересное, как в неевклидовой геометрии или в интенсиональных логиках; а, может, ее следствия пока особо никуда не применимы?..
То, что ответ дается без счета, не значит, что он дается «за один такт». Память — это очень сложная система «кэширования», и поиск в памяти на подсознательном уровне требует большого числа операций.
(Но опять же про память — отдельный большой разговор)
Но нужно ведь представить общее решение проблемы останова (то есть представить один алгоритм, который эту задачу решает для всех случаев). Куда в Вашей формулировке все кванторы-то делись? В чем «неправильность формулировки» в статье по сравнению с Вашей формулировкой?
По алгоритмической теории информации ее много. Там сложность индивидуального объекта (строки) определяется как длина кратчайшей программы, которая печатает эту строку и останавливается.
Отсюда следует банальный вывод, что любая программа, которая печатает некоторый ответ и останавливается, не может породить строку, более сложную, чем она сама.
Интереснее рассмотреть вопрос, какой сложности строки может порождать безостановочная программа (и вот на этот счет с литературой как-то хуже). Очевидно, такая программа может порождать строки любой сложности!
Действительно, можно представить себе мата-алгоритм, который перебирает все прочие алгоритмы. Если такой мета-алгоритм должен остановиться, то в нем должен быть зашит некий критерий остановки, и чем сложнее тот алгоритм, который мы хотим породить на выходе, тем сложнее должен быть критерий остановки. В итоге все равно получим, что сложность ответа будет не выше сложности порождающего алгоритма с необходимым критерием. Скажем, если мы на выходе хотим получить алгоритм ИИ, то переборный останавливающийся алгоритм окажется не проще, чем этот самый ИИ!
Безостановочный же переборный алгоритм сможет породить все, что угодно на выходе, оставаясь при этом простым (естественно, останется вопрос, как из этого «всего, что угодно» будет выбираться «то, что нужно»).
Но это просто утрированный пример для демонстрации различий в сложности выхода, даваемого остановочными и безостановочными алгоритмами.
Мышлению просто не от чего отталкиваться, кроме как от реального мира. Даже если строится «экзотическая» система аксиом, она строится «в противовес» естественным свойствам.
Это серьезная проблема выбора, для выполнения которого нужно учесть весь контекст решаемой вами задачи.
Рассуждать же в терминах странных аттракторов, конечно, можно, но все же не слишком продуктивно. Эти странные аттракторы, которые в теории динамических систем выглядят почти что чудом, в теории алгоритмов достаточно заурядны (в силу существенной нелинейности алгоритмов).
Мы планируем написать статьи на эти темы.
Под программой в статье в основном понимается программа для машины Тьюринга, то есть тоже алгоритм.
Действительно, реальная работающая программа несводима к своей модели — алгоритму. В статье на это лишь намекается, но, возможно, следовало бы этот аспект обсудить в явном виде.
Что касается «хорошо проработанной теории алгоритмов», в действительности, это не совсем так (а, может, и далеко не так). Хорошо проработаны далеко не все ее аспекты. Кому надо переосмыслять эту теорию? Разработчикам моделей универсального ИИ. И некоторыми из них это, собственно, и делается. Особенно интересна связь теории алгоритмов и теории информации. Хотя алгоритмическая теория информации была развита Колмогоровым и Соломоновым достаточно давно, сейчас становится понятной необходимость обобщения алгоритмической сложности по Колмогорову с учетом вычислительной сложности (получается т.н. сложность по Левину)… В общем, тут масса всего интересного и еще непроработанного.
(Но опять же про память — отдельный большой разговор)