Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 167
кстати, утверждение о том, то решивший проблему алгоритм останавливается, совсем неверно. Например, любой калькулятор, решив задачу, продолжает работать. Это касается как железных, так и программных калькуляторов.
Ну здесь получаются разные задачи, и потому все остается правильным :-)
Я хочу сказать, что требование «остановки приложения» по достижению ответа, мне не представляется естественным. Во времена Тьюринга, возможно, это было очевидным (зачем машине с шестерёнками крутиться, когда задача решена?), однако, опыт практической реализации вычислительных систем, говорит, что остановка машины, это скорее аварийная ситуация, чем признак решения задачи.
Почему это важно? Потому что это формулирует очень важное условие алгоритма — «правильными» алгоритмами считаются те, которые останавливаются.
А как насчёт алгоритма, который приходит к решению и продолжает его генерировать? Простейший пример — построение асимптотической линии. Достигли неразличимости с тому, к чему стремимся? Достигли. Останавливаться? Нет — так как линия продолжается в бесконечность. При этом практическая ценность решения вполне очевидна.
Почему это важно? Потому что это формулирует очень важное условие алгоритма — «правильными» алгоритмами считаются те, которые останавливаются.
А как насчёт алгоритма, который приходит к решению и продолжает его генерировать? Простейший пример — построение асимптотической линии. Достигли неразличимости с тому, к чему стремимся? Достигли. Останавливаться? Нет — так как линия продолжается в бесконечность. При этом практическая ценность решения вполне очевидна.
Мне кажется не стоит воспринимать остановку программы так буквально. Остановка программы в данном случае — момент, в который программа перестает генерировать результат.
Ну, в блок-схемах есть же специальные элементы — «Начало» и «Конец»
Тут важно — можно ли определить, что программа завершила работу (и содержимое данной ячейки ленты больше меняться не будет). Если можно — то мы не получаем увеличения вычислительной мощности. Если же требовать только чтобы каждая ячейка стабилизировалась, но не требовать вычислимости момента стабилизации — то мы получаем некоторое расширение вычислительных возможностей (вроде бы, примерно равное оракулу останова).
Я же специально привёл случай, когда программа «вроде бы не остановилась», но её результаты уже применимы к жизни.
Причём, может быть так, что мы не можем рассчитать расстояние до ответа (допустим, это трудная задача). В этом случае мы уже имеем ответ неполный ответ, который постепенно уточняется. Формально, алгоритм не имеет решения, фактически — им можно пользоваться.
Да что там изобретать. Алгоритм рассчёта ПИ в десятичной системе счисления. Формально — нерешаемая задача, алгоритм никогда не остановится.
И кому это мешало использовать пи в рассчётах?
Причём, может быть так, что мы не можем рассчитать расстояние до ответа (допустим, это трудная задача). В этом случае мы уже имеем ответ неполный ответ, который постепенно уточняется. Формально, алгоритм не имеет решения, фактически — им можно пользоваться.
Да что там изобретать. Алгоритм рассчёта ПИ в десятичной системе счисления. Формально — нерешаемая задача, алгоритм никогда не остановится.
И кому это мешало использовать пи в рассчётах?
Тут немного другое. Задача, которую решает алгоритм — это не «нахождение десятичной записи числа пи», это «нахождение первых N знаков десятичной записи числа пи» (ну или нахождение N-го знака, или еще что-то аналогичное).
Возникает вопрос о модели формализации. Калькулятор, завершив рассчет, переходит в некоторое особое состояние, легко отличимое от возникающих в ходе вычисления состояний. Если мы будем требовать такого поведения — то расширения вычислительных возможностей по сравнению с обычной МТ мы не получим.
Возникает вопрос о модели формализации. Калькулятор, завершив рассчет, переходит в некоторое особое состояние, легко отличимое от возникающих в ходе вычисления состояний. Если мы будем требовать такого поведения — то расширения вычислительных возможностей по сравнению с обычной МТ мы не получим.
Думается, Вы повторили часть статьи про «предельные» алгоритмы. Которые, кстати, легко останавливаются условием «погрешность меньше заданной величины».
Вообще, каждый алгоритм, дополненый условием «работать не дольше», «на вход подается вывод, который уже подавался» может быть остановлен. Но, поскольку математически требуется ответ «остановится ли где-то в бесконечности, для общего случая, включая самое себя» — это неразрешимая проблема.
Вообще, каждый алгоритм, дополненый условием «работать не дольше», «на вход подается вывод, который уже подавался» может быть остановлен. Но, поскольку математически требуется ответ «остановится ли где-то в бесконечности, для общего случая, включая самое себя» — это неразрешимая проблема.
Это если мы можем рассчитать погрешность. А теперь, что делать, если рассчёт погрешности, в свою очередь, задача труднорешаемая?
Просто мне кажется, что рассмотрение теории алгоритмов в модели «до остановки», возможно, не лучший вариант. (Как лучше — не знаю).
Просто мне кажется, что рассмотрение теории алгоритмов в модели «до остановки», возможно, не лучший вариант. (Как лучше — не знаю).
Не могли бы Вы привести пример такой задачи? Я не очень представляю, как такое может быть.
Ну, например, задача о вычислении числа, в двоичной записи которого стоят единицы на позициях, номера которых соответствуют останавливающимся машинам Тьюринга. Задача о вычислении этого числа с произвольной точностью алгоритмически неразрешима.
Предположим, у нас задача слежения: мы удерживаем фокус за двигающимся объектом. Когда алгоритм должен сказать «стоп»?
Когда объект сфокусирован?
Он двигается.
И вообще множество реальных алгоритмов успешно работают по принципу бесконечного цикла с выходом по внешнему условию — внешнее условие не наступило и алгоритм не останавливается.
Зачем рассматривать бесконечный цикл в качестве части алгоритма, алгоритм просто запускается в бесконечном цикле когда выполняются определенные условия, если условия не выполняются — алгоритм «спит». В примере с фокусом на объекте, вполне возможна ситуация, когда работа алгоритма не требуется, но бесконечный цикл будет работать, например, когда объект неподвижен.
Ну вот алгоритм слежения работающий по схеме бесконечного цила:
1. получить картинку с камеры
2. распознать объект и его положение на картинке
3. вычислить необходимый угол отклонения оси камеры от «нейтрального»
4. дать команду сервоприводу отклонить ось камеры на вычисленный угол
5. перейти к 1.
Работа шага 1 требуется постоянно, шага 2 если картинка изменилась (на практике — всегда: изменение освещенности, шумы и т. п.), только шаги 3 и 4 не задействуются если положение объекта не изменилось. И то шаг 4 можно пропустить при условии что камера управляется только этим объектом. То есть алгоритм должен работать постоянно если требуется отслеживать ASAP, а не периодически
1. получить картинку с камеры
2. распознать объект и его положение на картинке
3. вычислить необходимый угол отклонения оси камеры от «нейтрального»
4. дать команду сервоприводу отклонить ось камеры на вычисленный угол
5. перейти к 1.
Работа шага 1 требуется постоянно, шага 2 если картинка изменилась (на практике — всегда: изменение освещенности, шумы и т. п.), только шаги 3 и 4 не задействуются если положение объекта не изменилось. И то шаг 4 можно пропустить при условии что камера управляется только этим объектом. То есть алгоритм должен работать постоянно если требуется отслеживать ASAP, а не периодически
Шаги 1-4 составляют алгоритм(в данном случае он никогда не пропускается), шаг 5 — бесконечный цикл, внешний по отношению к алгоритму. Проблема с бесконечным циклом в том, что он может быть один, поэтому если нужно будет выполнять несколько алгоритмов, то их нужно будет помещать последовательно внутри бесконечного цикла.
Но соглашусь с вами, что бесконечный алгоритм возможен. Более того, скорее всего, именно такой алгоритм будет реализовывать сильный ИИ. Бесконечную программу должен кто-то дописывать по мере исполнения. Более того, если рассматривать весь цикл как один шаг некоторой виртуальной машины, мы увидим линейно бесконечную программу вместо зацикленной. Причем писаться такая программа будет внешней средой.
В случае слежения за объектом главным «программистом» виртуальной машины будет объект, за которым она следит, т.к. именно он определяет угол поворота камеры. Если объект совершает периодическое движение так, что угол поворота камеры меняется циклически, получим цикл второго уровня. На первом уровне цикл задан жестко внутри, на втором — также жестко снаружи. Очевидно, что для сильного ИИ потребуется нечто среднее, т.е. среда должна иметь возможность влиять на первый уровень, а программа — на второй. Что-то не могу придумать третьего уровня, но вероятно, более сложные системы будут многоуровневыми в этом плане.
В случае слежения за объектом главным «программистом» виртуальной машины будет объект, за которым она следит, т.к. именно он определяет угол поворота камеры. Если объект совершает периодическое движение так, что угол поворота камеры меняется циклически, получим цикл второго уровня. На первом уровне цикл задан жестко внутри, на втором — также жестко снаружи. Очевидно, что для сильного ИИ потребуется нечто среднее, т.е. среда должна иметь возможность влиять на первый уровень, а программа — на второй. Что-то не могу придумать третьего уровня, но вероятно, более сложные системы будут многоуровневыми в этом плане.
Третий уровень — человек, который заставил объект двигаться периодически. А над ним — человек, который дал ему приказ обеспечить циклическое действие, а над ним… А вообще может быть не человек, а другой ИИ.
Этот вариант третьего уровня не совсем подходит. Во-первых, человека в систему лучше не включать(предпочту не объяснять, но можно придумать множество причин). Во-вторых, человек только заставил двигаться периодически, т.е. программа уже первого человека состоит из однократной команды, т.е. его виртуальная машина вырожденная. В-третьих, тут плохо просматривается связь: что программа на более высоком уровне является данными на более низком. Программа высокого уровня пишется в данных низкого. Иначе «виртуализация» получится неполной, т.е. начнет превращаться в обычную иерархию.
Решил продолжить ваши рассуждения: «а над ним…» идея(по Гегелю).
… то следует перерассчёт снова и снова.
Хотите ещё менее конечную задачу — корректировка курса ракеты в режиме погони. Ну там, правда, есть останов, который уж всем остановам останов, если догнали.
Хотите ещё менее конечную задачу — корректировка курса ракеты в режиме погони. Ну там, правда, есть останов, который уж всем остановам останов, если догнали.
Я бы сказал, что и человеческая «свободная воля» детерминирована в окружающем конкретную личность пространстве-времени. Просто факторов очень много, которые не могуи быть проигнорированы в силу «эффекта бабочки».
Более того, число факторов возрастает в связи с тем, что еще не ясно, является ли Вселенная замкнутой, а потому «изолированной системой»
Касаемо ограниченности, согласен — ни алгоритм, ни компьютер, ни Тьюринг-автомат, ни человек — не может «познать» себя.
И да, касательно аксиом. Они также прочно формируют базис теории, как и легко могут быть заменены другим базисом, и в этом случае получаем другую теорию.
Более того, число факторов возрастает в связи с тем, что еще не ясно, является ли Вселенная замкнутой, а потому «изолированной системой»
Касаемо ограниченности, согласен — ни алгоритм, ни компьютер, ни Тьюринг-автомат, ни человек — не может «познать» себя.
И да, касательно аксиом. Они также прочно формируют базис теории, как и легко могут быть заменены другим базисом, и в этом случае получаем другую теорию.
Насчёт необходимости ИИ взаимодействовать с окружающей средой (получать информацию, ставить эксперименты) я сам додумался, вот до безостановочных алгоритмов как-то нет. Надо будет подумать над ними.
Поставил задачу дочитать до конца. Неразрешимо…
Вероятностные алгоритмы не расширяют вычислительных возможностей, т.к. можно просто перебрать результаты выпадения монетки.
Про вероятностные в статье упоминается.
Насчет аксиоматики. Алгоритмически неразрешимые задачи разрешимы с помощью сверхтьюринговых вычислений. Но для таких «вычислений» будут свои неразрешимые задачи. Об этом тоже упоминается.
Но дело даже не в этом. Самое главное то, что алгоритмы описывают операции над конструктивными объектами. Это можно четко понять по статьям Колмогорова. Колмогоров пытался дать (и дал) наиболее общее понятие конструктивного объекта и для таких объектов предложил свою формализацию понятия алгоритма, после чего со своим учеником доказал, что эта формализация эквивалентна другим существующим формализациям. То есть алгоритмы — это максимум, что можно сделать конструктивного. Сверхтьюринговые системы гипотетически возможны, но они неконструктивны (нефинитны), то есть абсолютно неясно, как и можно реализовать. Если будут открыты физические системы, реализующие инфинитные процесс, и человек научится этими процессами управлять, тогда будет иметь смысл говорить о конструктивных неалгоритмических системах. Пока же максимальное конструктивное расширение понятия алгоритма — это его расширение на открытые алгоритмические процессы.
Насчет аксиоматики. Алгоритмически неразрешимые задачи разрешимы с помощью сверхтьюринговых вычислений. Но для таких «вычислений» будут свои неразрешимые задачи. Об этом тоже упоминается.
Но дело даже не в этом. Самое главное то, что алгоритмы описывают операции над конструктивными объектами. Это можно четко понять по статьям Колмогорова. Колмогоров пытался дать (и дал) наиболее общее понятие конструктивного объекта и для таких объектов предложил свою формализацию понятия алгоритма, после чего со своим учеником доказал, что эта формализация эквивалентна другим существующим формализациям. То есть алгоритмы — это максимум, что можно сделать конструктивного. Сверхтьюринговые системы гипотетически возможны, но они неконструктивны (нефинитны), то есть абсолютно неясно, как и можно реализовать. Если будут открыты физические системы, реализующие инфинитные процесс, и человек научится этими процессами управлять, тогда будет иметь смысл говорить о конструктивных неалгоритмических системах. Пока же максимальное конструктивное расширение понятия алгоритма — это его расширение на открытые алгоритмические процессы.
А можно сжать суть статьи до двух предложений? Потому что на данный момент она мне кажется довольно странной, может, я чего недопонимаю.
Вы ссылаетесь на каких-то неназванных мыслителей, которые «делают вывод о невозможности формализации мышления», а потом доказываете им (!), что их позиция слаба.
В то же время можно сослаться на кучу других мыслителей (начиная с того же Тьюринга и кончая, например, Хофштадтером), которые не видят никаких противоречий между существованием неразрешимых задач и теоретической возможностью создания «сильного ИИ».
Вы ссылаетесь на каких-то неназванных мыслителей, которые «делают вывод о невозможности формализации мышления», а потом доказываете им (!), что их позиция слаба.
В то же время можно сослаться на кучу других мыслителей (начиная с того же Тьюринга и кончая, например, Хофштадтером), которые не видят никаких противоречий между существованием неразрешимых задач и теоретической возможностью создания «сильного ИИ».
Но какую бы мы формальную систему ни взяли, всегда найдутся утверждения об объектах системы, истинность которых не может быть установлена в рамках самой системы. Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат
Круто. Скажите, пожалуйста, истинны или ложны в ZF гипотеза континуума и аксиома выбора?
Э… Если не изменяет память, считается, что континуум-гипотеза и аксиома выбора не противоречат аксиоматике ZF. Если их принять за истинные, получается аксиоматика ZFC. Но неконструктивные объекты нас меньше интересуют, поэтому можем ошибаться…
Если же ставить вопрос, является ли эта гипотеза в принципе истинной, то вопрос будет бессмысленным. Уменьшение числа аксиом позволяет рассматривать более общий класс моделей, увеличение — позволяет обогащать выводимые свойства для более узкого класса. В каких-то случаях удобнее евклидова геометрия, а каких-то — неевклидова. Кому-то нравится закон исключенного третьего, а кто-то предпочитает интенсиональные логики. Можно, конечно, думать, что в мире идей есть какое-то истинное понятие континуума. Но на наш взгляд, те аксиоматические системы, которые производят впечатление такой абсолютной истины, являются все же просто очень эффективным индуктивным обобщением свойств реальности.
Если же ставить вопрос, является ли эта гипотеза в принципе истинной, то вопрос будет бессмысленным. Уменьшение числа аксиом позволяет рассматривать более общий класс моделей, увеличение — позволяет обогащать выводимые свойства для более узкого класса. В каких-то случаях удобнее евклидова геометрия, а каких-то — неевклидова. Кому-то нравится закон исключенного третьего, а кто-то предпочитает интенсиональные логики. Можно, конечно, думать, что в мире идей есть какое-то истинное понятие континуума. Но на наш взгляд, те аксиоматические системы, которые производят впечатление такой абсолютной истины, являются все же просто очень эффективным индуктивным обобщением свойств реальности.
Стоп. Вы утверждаете, что человек может мистическим образом определить, должны ли эти утверждения быть истинными или ложными. Определитесь, пожалуйста:)
В математике не принято «считать», в математике принято доказывать. В частности, в данном случае доказано следующее: ZF с добавлением гипотезы континуума либо ее отрицания, а также с добавлением аксиомы выбора либо ее отрицания, равнонепротиворечива с исходной ZF.
Кстати, в каком смысле ZF неконструктивна? Вы можете доказать, что у нее нету счетной разрешимой модели? (может быть это и правда, я не знаю; но это вроде бы неочевидно)
считается
В математике не принято «считать», в математике принято доказывать. В частности, в данном случае доказано следующее: ZF с добавлением гипотезы континуума либо ее отрицания, а также с добавлением аксиомы выбора либо ее отрицания, равнонепротиворечива с исходной ZF.
Кстати, в каком смысле ZF неконструктивна? Вы можете доказать, что у нее нету счетной разрешимой модели? (может быть это и правда, я не знаю; но это вроде бы неочевидно)
Про ZF это и имелось в виду, просто на память не было уверенности в том, что это строго доказано, а проверять было лень; отсюда и взялось «считается».
А откуда следует, что «человек может мистическим образом определить, должны ли эти утверждения быть истинными или ложными»? Вовсе не мистическим, а индуктивно.
Насчет неконструктивности, опять же, это смутные воспоминания, подкрепленные интуицией о том, что аксиома выбора для континуумов не имеет алгоритмического воплощения. Если это вдруг не доказано, то, вероятно, это не так сложно сделать исходя из понятия алгоритмической сложности.
А откуда следует, что «человек может мистическим образом определить, должны ли эти утверждения быть истинными или ложными»? Вовсе не мистическим, а индуктивно.
Насчет неконструктивности, опять же, это смутные воспоминания, подкрепленные интуицией о том, что аксиома выбора для континуумов не имеет алгоритмического воплощения. Если это вдруг не доказано, то, вероятно, это не так сложно сделать исходя из понятия алгоритмической сложности.
А откуда следует, что «человек может мистическим образом определить, должны ли эти утверждения быть истинными или ложными»?
Вопрос к Вам — Вы же это написали.
А " алгоритмическое вополщение аксиомы выбора для континуальных множеств" осложняется тем, что не очень понятно, что такое континуальное множество в контексте алгоритмов. Причем тут алгоритмическая сложность — не понимаю.
Тогда ответ на вопрос был дан: нет, человек определяет это вовсе не мистическим образом.
Насчет осложнения — именно; поэтому континуальные множества и не являются конструктивными объектами.
Насчет осложнения — именно; поэтому континуальные множества и не являются конструктивными объектами.
Слово «мистическим» употребили Вы…
Хорошо, определите мне хоть индуктивным. хоть каким образом истинность аксиомы выбора в ZF.
Ну да, только зачем рассматривать континуальные множества? Если ZF непротиворечива, то у нее есть модель; можно доказать, что всякая модель ZF бесконечна; тогда по теореме о понижении мощности у нее есть счетная модель.
Хорошо, определите мне хоть индуктивным. хоть каким образом истинность аксиомы выбора в ZF.
Ну да, только зачем рассматривать континуальные множества? Если ZF непротиворечива, то у нее есть модель; можно доказать, что всякая модель ZF бесконечна; тогда по теореме о понижении мощности у нее есть счетная модель.
Так ведь не является аксиома выбора в ZF ни истинной, ни ложной. Добавлять ли ее или нет — вопрос полезности. Аксиоматика ZFC успешно применяется. Есть ли попытки рассмотреть, что получится в аксиоматике ZF!C? Может, там будет что-то интересное, как в неевклидовой геометрии или в интенсиональных логиках; а, может, ее следствия пока особо никуда не применимы?..
Безусловно, не является.
Но раз Вы — человек, а не машина, то сделайте то, на что, согласно Вашему следующему утверждению способен человек:)
Насчет аксиомы выбора — не знаю. Но в функане в последнее время модно неявно использовать как гипотезу континуума, так и ее отрицание.
Но какую бы мы формальную систему ни взяли, всегда найдутся утверждения об объектах системы, истинность которых не может быть установлена в рамках самой системы.
Но раз Вы — человек, а не машина, то сделайте то, на что, согласно Вашему следующему утверждению способен человек:)
Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат.
Насчет аксиомы выбора — не знаю. Но в функане в последнее время модно неявно использовать как гипотезу континуума, так и ее отрицание.
Вот видите, специалисты по функану в каждом конкретном случае для себя этот выбор делают. Этот выбор определяется контекстом применения соответствующей аксиоматики. Что Вам еще нужно?
Мне нужно мистическим образом определить, должны лы быть эти утверждения истинными или ложными:)
Можно только посочувствовать ))
Это серьезная проблема выбора, для выполнения которого нужно учесть весь контекст решаемой вами задачи.
Это серьезная проблема выбора, для выполнения которого нужно учесть весь контекст решаемой вами задачи.
Мистическим образом вы можете для себя решить считать их истинными или ложными.
Существование абсолютной, объективной истины не доказано :) Человек же оперирует истинностью относительной. Какие-то утверждения, как правило не противоречащие субъективной картине мира данной в ощущениях, принимаются за истину. Мистически. Остальные утверждения проверяются на соответствие им, не соответствие или ортогональность. Более того, на практике часто применяются в качестве истинных утверждения заведомо ложные, лишь бы они приводили к практически приемлемому, пускай и не точному результату. Скажем, кратчайшим расстоянием между двумя точками на поверхности Земли зачастую считают длину кратчайшей линии на (апроксимации) этой поверхности, а не отрезок прямой, соединяющий эти точки в пространстве — рыть математически (по Евклиду) кратчайший тоннель из Нью-Йорка в Москву не практично.
Существование абсолютной, объективной истины не доказано :) Человек же оперирует истинностью относительной. Какие-то утверждения, как правило не противоречащие субъективной картине мира данной в ощущениях, принимаются за истину. Мистически. Остальные утверждения проверяются на соответствие им, не соответствие или ортогональность. Более того, на практике часто применяются в качестве истинных утверждения заведомо ложные, лишь бы они приводили к практически приемлемому, пускай и не точному результату. Скажем, кратчайшим расстоянием между двумя точками на поверхности Земли зачастую считают длину кратчайшей линии на (апроксимации) этой поверхности, а не отрезок прямой, соединяющий эти точки в пространстве — рыть математически (по Евклиду) кратчайший тоннель из Нью-Йорка в Москву не практично.
Вы вообще с чем спорите? Вы, вроде, говорите практически то же самое, что и мы. Или это у Вас такой способ соглашаться?
Я поясняю mihaild, что нельзя определить истинно какое-то утверждение или ложно. Ни мистически нельзя, ни логически. Можно только решить считать истинно оно или нет. (В случае логического вывода — истинны ли изначальные посылки и сами правила логики).
Просто автор указывал превосходство человека перед формальными системами — он способен определить, должно ли независимое от формальной системы утверждение быть истинным или ложным.
Исходя из этого и последующей дискуссиии, автора следует счесть формальной системой, а не человеком:)
Что же касается тоннелей — в этом случае мы просто работаем в другой многообразии — не трехмерное евклидово пространство, а поверхность Земли. На которой есть своя метрика, отличная от метрики объемлющего пространства (хотя и индуцированная ей).
Исходя из этого и последующей дискуссиии, автора следует счесть формальной системой, а не человеком:)
Что же касается тоннелей — в этом случае мы просто работаем в другой многообразии — не трехмерное евклидово пространство, а поверхность Земли. На которой есть своя метрика, отличная от метрики объемлющего пространства (хотя и индуцированная ей).
Автор ошибается, человек может решить считать утверждение истинным и свои дальнейшие рассуждения и/или действия строить от этого «факта». А потом передумать и считать его ложным. Или считать истинным только в каких-то частных случаях.
>В математике не принято «считать», в математике принято доказывать.
Вообще в математике «считается» довольно распространенное явление: «Аксиома — утверждение, не требующее доказательств.»
Вообще в математике «считается» довольно распространенное явление: «Аксиома — утверждение, не требующее доказательств.»
>> Но на наш взгляд, те аксиоматические системы, которые производят впечатление такой абсолютной истины, являются все же просто очень эффективным индуктивным обобщением свойств реальности.
Вы как-то пишите, что пытаетесь ввести в заблуждение себя или других (не совсем понятно). Формальная математика не работает с реальным миром!!! Это вопрос философии насколько она применима и вопрос физиков насколько математическая модель подходит к наблюдаемым эффектам, ни больше.
>> Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат.
Опять же что такое желаемый результат!? Я не знаю верна ли теорема Эйлера или нет, так что мне ее добавлять в аксиомы? (Хотя с гипотезой Римана так и пытаются делать, но это неправильно).
То что вы пишите, что кто-то использует меньший набор аксиом, а кто-то больший — сильно зависит от среды. Например функциональном анализе по сути дела все равно, на сколько верна аксиома выбора, потому что она дает мощный и хороший апарат для использования в теории вероятностей. Даже если окажется, что она не верна, большинство результатов останутся, потому что они проверены в реальных моделях, соответственно найдется некоторое верное сужение аксиомы выбора. А сужают те люди, которые хотят найти и показать минимальный набор аксиом, который бы удовлетворял некоторой модели. Чем-то напоминает программирование, чем более абстрактный фреймворк напишешь, тем в больших местах он пригодится, но если совсем абстрактный вообще нигде толком пользы и не принесет.
Вы не заметили, что Эйлер не пользовался формальными доказательствами, но не сделал никакой ошибки. Он даже умудрялся сумировать расходящиеся ряды без формальных определений например
1 — 1 + 1 — 1 + 1 — 1… = 1/2
:)
Вы как-то пишите, что пытаетесь ввести в заблуждение себя или других (не совсем понятно). Формальная математика не работает с реальным миром!!! Это вопрос философии насколько она применима и вопрос физиков насколько математическая модель подходит к наблюдаемым эффектам, ни больше.
>> Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат.
Опять же что такое желаемый результат!? Я не знаю верна ли теорема Эйлера или нет, так что мне ее добавлять в аксиомы? (Хотя с гипотезой Римана так и пытаются делать, но это неправильно).
То что вы пишите, что кто-то использует меньший набор аксиом, а кто-то больший — сильно зависит от среды. Например функциональном анализе по сути дела все равно, на сколько верна аксиома выбора, потому что она дает мощный и хороший апарат для использования в теории вероятностей. Даже если окажется, что она не верна, большинство результатов останутся, потому что они проверены в реальных моделях, соответственно найдется некоторое верное сужение аксиомы выбора. А сужают те люди, которые хотят найти и показать минимальный набор аксиом, который бы удовлетворял некоторой модели. Чем-то напоминает программирование, чем более абстрактный фреймворк напишешь, тем в больших местах он пригодится, но если совсем абстрактный вообще нигде толком пользы и не принесет.
Вы не заметили, что Эйлер не пользовался формальными доказательствами, но не сделал никакой ошибки. Он даже умудрялся сумировать расходящиеся ряды без формальных определений например
1 — 1 + 1 — 1 + 1 — 1… = 1/2
:)
В свое время преподаватель математики жаловался, что физики берут их формализмы и оперируют ими, никак не доказывая, что это допустимо. Это возможно только в силу гиперуниверсальности и интуитивной ясности математических абстракций, но логически неверно. Как и на выбор фреймворка, на выбор математического аппарата теории могут оказывать влияние личные предпочтения, хотя и в значительно меньшей степени. Аксиом в природе не существует, аксиомы формализуют точку зрения, а не реальность(в широком смысле).
На эту тему Вигнер когда-то прочитал лекцию «Непостижимая эффективность математики в естественных науках» (текст легко можно найти).
Нобелевский лауреат, автор теории слабого взаимодействия, рассказывал, что на момент формулировки теории у них было восемь экспериментов, ей противоречащих. Но математический аппарат теории был столь красив, что она просто не могла оказаться неверной — и впоследствии нашлись ошибки во всех восьми результатах.
И так далее.
Нобелевский лауреат, автор теории слабого взаимодействия, рассказывал, что на момент формулировки теории у них было восемь экспериментов, ей противоречащих. Но математический аппарат теории был столь красив, что она просто не могла оказаться неверной — и впоследствии нашлись ошибки во всех восьми результатах.
И так далее.
Абстракция. Счет необходим человеку, который применяет его к реальному(в широком смысле) миру. Следовательно, счет связан с реальным миром, правда связь односторонняя.
То, что в природе нет слов можно принять в качестве аксиомы.
Если в природе нет слов, то нет и чисел, значит в природе нет счета.
Никакого совпадения тут нет: в природе счета нет, а у человека он есть.
То, что в природе нет слов можно принять в качестве аксиомы.
Если в природе нет слов, то нет и чисел, значит в природе нет счета.
Никакого совпадения тут нет: в природе счета нет, а у человека он есть.
Тем не менее, многие физические величины ведут себя как вещественные и комплексные числа, вектора, тензоры, операторы и т.д.
Это скорее человек нашёл удобный способ описания физических состояний и процессов.
Тем не менее нередко появление математического аппарата предшествовало нахождению физического смысла. И, если математика для описания того или иного явления — просто изобретение человека — то не очень понятно, почему один и тот же аппарат прекрасно применим к очень разным на первый взгляд явлениям.
потому что его создавали гениальные люди, опережающие свое время.
Вот лекция, о которой я писал чуть выше: www.youtube.com/watch?v=UuRxRGR3VpM
«Красота — очень удачный критерий для выбора правильной теории»
«Теория является красивой, если она может быть кратко изложена в терминах уже существующей математики»
Если предположить, что математика — не абсолют, а творение человека, то совершенно непонятно, почему она так тесно связана с законами природы.
«Красота — очень удачный критерий для выбора правильной теории»
«Теория является красивой, если она может быть кратко изложена в терминах уже существующей математики»
Если предположить, что математика — не абсолют, а творение человека, то совершенно непонятно, почему она так тесно связана с законами природы.
Математика создавалась, чтобы описывать законы природу и она хорошо справляется со своей задачей. Также как алфавит создавался, чтобы записывать слова. Также можно удивляться и красоте букв. Буквы можно применять в самых разных словах. И конечно, новые слова должны быть записываемыми с помощью уже существующего алфавита. Но не из чего не следует, что никогда не понадобится новая буква или какая то буква станет ненужной, просто уже существующий алфавит прошел долгий отбор и вероятность изменения стремится к нулю.
Если кто не понял буквы — это разделы математики, слова — теории, описывающие природу.
Если кто не понял буквы — это разделы математики, слова — теории, описывающие природу.
Во-первых, слова искусственны, и крайне маловероятно, что человек, не знающий слова для описания данного явления придумает именно то слово, которое придумали до него. В то время как многие понятия в математике нередко возникали в самых разных областях а потом кто-то замечал, что это одно и то же.
Во-вторых, было бы довольно странным, если бы для описания чего-то, о чем раньше никто не задумывался, подходило существующее слово.
Во-вторых, было бы довольно странным, если бы для описания чего-то, о чем раньше никто не задумывался, подходило существующее слово.
«Во-вторых, было бы довольно странным, если бы для описания чего-то, о чем раньше никто не задумывался, подходило существующее слово.»
У меня выше со словами ассоциируются теории(возможны вы имели ввиду буквы?). В этом контексте вы утверждаете примерно следующее: было бы странно, если бы для описания чего-то нового подходила существующая теория. Ничего странного ни в том, ни другом случае нет. Если найдут новый вид животного, то к нему вполне будет подходить слово «животное». Если обнаружат белые дыры, то существующая теория гравитации для них вполне подходит.
«Во-первых, слова искусственны, и крайне маловероятно, что человек, не знающий слова для описания данного явления придумает именно то слово, которое придумали до него.» Да слова искусственны, но теории тоже. Все зависит от контекста, в рамках бытового сленга вполне возможно, что, например, новое устройство для сушки чего-либо назовут сушилка независимо друг от друга множество, если не все, кто им начнет пользоваться. В тоже время, в неопределенных случаях для описания одного и того же явления разные исследователи выдвинут разные теории и будут при этом опираться на различные(или даже одинаковые) разделы математики.
«В то время как многие понятия в математике нередко возникали в самых разных областях а потом кто-то замечал, что это одно и то же.» — Многие буквы возникали в самых разных словах, а потом кто-то видел, что это одинаковые буквы(и начинал их записывать одинаково, так мы и пришли к единообразному алфавиту).
У меня выше со словами ассоциируются теории(возможны вы имели ввиду буквы?). В этом контексте вы утверждаете примерно следующее: было бы странно, если бы для описания чего-то нового подходила существующая теория. Ничего странного ни в том, ни другом случае нет. Если найдут новый вид животного, то к нему вполне будет подходить слово «животное». Если обнаружат белые дыры, то существующая теория гравитации для них вполне подходит.
«Во-первых, слова искусственны, и крайне маловероятно, что человек, не знающий слова для описания данного явления придумает именно то слово, которое придумали до него.» Да слова искусственны, но теории тоже. Все зависит от контекста, в рамках бытового сленга вполне возможно, что, например, новое устройство для сушки чего-либо назовут сушилка независимо друг от друга множество, если не все, кто им начнет пользоваться. В тоже время, в неопределенных случаях для описания одного и того же явления разные исследователи выдвинут разные теории и будут при этом опираться на различные(или даже одинаковые) разделы математики.
«В то время как многие понятия в математике нередко возникали в самых разных областях а потом кто-то замечал, что это одно и то же.» — Многие буквы возникали в самых разных словах, а потом кто-то видел, что это одинаковые буквы(и начинал их записывать одинаково, так мы и пришли к единообразному алфавиту).
«чего-то, о чем раньше никто не задумывался» — привести подходящий пример несколько затруднительно
P.S. Я не зря привел пример с алфавитом, так как человечеству известно несколько алфавитов, но одна математика.
«Если найдут новый вид животного, то к нему вполне будет подходить слово «животное»»
Но если обнаружат некую непонятную хрень то очень вряд ли найдется существующее слово, ее обозначающее.
Слова всегда возникали после возникновения (быть может, умозрительного) обозначаемого ими предмета. Математический аппарат же иногда опережал открытие соответствующих явлений в природе.
«новое устройство для сушки чего-либо назовут сушилка независимо друг от друга множество, если не все, кто им начнет пользоваться»
Потому что это достаточно близко к уже существующему. И то — это описание будет неточным. А математика дает точные описания природных явлений.
Существует множество разных языков. Но альтернативных математических теорий пока нет, и вряд ли будут (да, я знаю про интуиционизм, про нестандартный анализ и т.д. — но они все эквивалентны классическим).
«Многие буквы возникали в самых разных словах, а потом кто-то видел, что это одинаковые буквы»
У букв нет самостоятельного смысла, в отличии от разделов математики.
Но если обнаружат некую непонятную хрень то очень вряд ли найдется существующее слово, ее обозначающее.
Слова всегда возникали после возникновения (быть может, умозрительного) обозначаемого ими предмета. Математический аппарат же иногда опережал открытие соответствующих явлений в природе.
«новое устройство для сушки чего-либо назовут сушилка независимо друг от друга множество, если не все, кто им начнет пользоваться»
Потому что это достаточно близко к уже существующему. И то — это описание будет неточным. А математика дает точные описания природных явлений.
Существует множество разных языков. Но альтернативных математических теорий пока нет, и вряд ли будут (да, я знаю про интуиционизм, про нестандартный анализ и т.д. — но они все эквивалентны классическим).
«Многие буквы возникали в самых разных словах, а потом кто-то видел, что это одинаковые буквы»
У букв нет самостоятельного смысла, в отличии от разделов математики.
«У букв нет самостоятельного смысла, в отличии от разделов математики.»
У них есть смысл — только из них можно составлять слова. Никакой другой смысл не имеет значения для данной аналогии.
«Слова всегда возникали после возникновения (быть может, умозрительного) обозначаемого ими предмета. Математический аппарат же иногда опережал открытие соответствующих явлений в природе.» Еще раз математический аппарат — множество разделов математики у меня в тексте ассоциируется с алфавитом. Конечно же, алфавит опережает многие слова из него составленные.
З.Ы. Ничего внутри вселенной, кроме эго не имеет самостоятельного смысла. Это точка смысловой сингулярности.:)
У них есть смысл — только из них можно составлять слова. Никакой другой смысл не имеет значения для данной аналогии.
«Слова всегда возникали после возникновения (быть может, умозрительного) обозначаемого ими предмета. Математический аппарат же иногда опережал открытие соответствующих явлений в природе.» Еще раз математический аппарат — множество разделов математики у меня в тексте ассоциируется с алфавитом. Конечно же, алфавит опережает многие слова из него составленные.
З.Ы. Ничего внутри вселенной, кроме эго не имеет самостоятельного смысла. Это точка смысловой сингулярности.:)
вы же удивляетесь, что слова произносятся так, как будто они состоят из букв
Представьте, что Вы придумали буквы. А потом обнаружился язык, о котором Вы и не слышали, придумывая буквы, слова в котором составляются именно из этих букв.
Слова суть изобретение человека, буквы — тоже.
Законы природы — не изобретение человека. Гравитационные линзы существуют объективно, а не потому, что их придумал Эйнштейн.
«только из них можно составлять слова»
Буквы, которые не используются при составлении слов — бессмысленны. Разделы математики, не использующиеся на текущий момент в физике — не бессмысленны.
Слова суть изобретение человека, буквы — тоже.
Законы природы — не изобретение человека. Гравитационные линзы существуют объективно, а не потому, что их придумал Эйнштейн.
«только из них можно составлять слова»
Буквы, которые не используются при составлении слов — бессмысленны. Разделы математики, не использующиеся на текущий момент в физике — не бессмысленны.
Потому что они очень разные только на первый взгляд? Казалось бы что общего между морской волной, светом и звуком… Кстати, лично я считаю, что схожесть математических описаний разных процессов говорит о возможности создания «единой теории поля (всего)» и подозреваю, что когда (если) она будет создана, то будет довольно компактной и красивой.
Уходите в метафизику, друг мой ) Это старая дилемма — что является первоначалом, математика или физика. Наша наука построена таким образом, что мы вкладываем в природу математический смысл, описываем ее на языке уравнений. Но и напротив, не реже приписываем природе свойства наших уравнений, трактуя наблюдения так, как это удобно нам. Здесь, по моему мнению, следует рассмотреть вопрос истории математики начиная с самых начал. Определенные попытки такого анализа были у Лебега, хотя даже он не смог удержаться от доли метафизичности.
На эту тему есть замечательная книжка Клайна «Математика. Утрата определенности», где в том числе рассматривается история развития.
Оба варианта были довольно часто — иногда сначала обнаруживали явления, а потом создавали мат. аппарат для их описания, иногда — наоборот. Вопрос о том, абсолютна ли на самом деле математика остается открытым и вряд ли мы в данной дискуссии его решим.
Вигнер
Оба варианта были довольно часто — иногда сначала обнаруживали явления, а потом создавали мат. аппарат для их описания, иногда — наоборот. Вопрос о том, абсолютна ли на самом деле математика остается открытым и вряд ли мы в данной дискуссии его решим.
Чудесная
загадка соответствия математического языка законам физики является
удивительным даром, который мы не в состоянии понять и которого мы,
возможно, недостойны. Мы должны испытывать чувство благодарности
за этот дар. Следует надеяться, что он не покинет нас и в будущих иссле-
дованиях и что он будет — хорошо это или плохо — развиваться к наше-
му большому удовлетворению, а быть может, и к нарастающему беспокой-
ству, расширяя область познания окружающего нас мира.
Вигнер
>> Формальная математика не работает с реальным миром!!!
Мышлению просто не от чего отталкиваться, кроме как от реального мира. Даже если строится «экзотическая» система аксиом, она строится «в противовес» естественным свойствам.
Мышлению просто не от чего отталкиваться, кроме как от реального мира. Даже если строится «экзотическая» система аксиом, она строится «в противовес» естественным свойствам.
Я не говорю, что аксиомы или теоремы берутся не из реального мира, как раз наоборот :) Только из необходимостей реального мира, но момент когда они переносятся в формальную математику они теряют эту связь. Связь остается только на уровне аксиом и каждый, кто применяет математическую модель по-хорошему должен фальсифицировать верность аксиом на некоторой реальной или опять же абстрактной моделе.
Аксиома о существовании бога(ов) ортогональна реальному миру.
Ну да, но Эйлеру везло. Формализм же позволяет, не будучи гением, строить правильные выводы (или хотя бы проверять чужие выводы на правильность).
Хунта. Прочитал как ХУNТА.
Вспомним Тьюринговскую трясину. В примере один простой алгоритм применяется для решения всех однотипных задач, и мы убеждаемся в заведомой невозможности правильного ответа. Создав же отдельные алгоритмы для частных случаев мы находим выход из положения.
Ну да, даже знаменитая Великая Теорема Ферма была доказана сначала для случаев 3,4, затем с помощью ЭВМ проверена до 100, и только в 95ом году была доказана для общего случая.
В случае же человеческого мышления, с ошибками — я полагаю, используется интер -и экстраполяция, т.е. человек склонен наблюдать частный случай и делать вывод из частного в общее. Неудивительно, что ошибок оказывается намного больше ожидаемого…
В случае же человеческого мышления, с ошибками — я полагаю, используется интер -и экстраполяция, т.е. человек склонен наблюдать частный случай и делать вывод из частного в общее. Неудивительно, что ошибок оказывается намного больше ожидаемого…
Алгоритм нахождения алгоритма?
Проблема тьюринговых машин заключается не в алгоритмической неразрешимости. Это как вобщем-то правильно подмечено в статье обходится предоставлением алгоритму возможности наблюдать за миром, и введением нескольких параллельных процессов.
Но существует т.н. задачи класса Р, а это означает, что мы не можем её решение получить быстрее, чем за полиномиальное время, как на детерминированной машине Тьюринга (т.е. последовательно), так и на недетерминированной машине Тьюринга (т.е. параллельно).
И именно этого и не хватает для решения AI-полных задач.
Но существует т.н. задачи класса Р, а это означает, что мы не можем её решение получить быстрее, чем за полиномиальное время, как на детерминированной машине Тьюринга (т.е. последовательно), так и на недетерминированной машине Тьюринга (т.е. параллельно).
И именно этого и не хватает для решения AI-полных задач.
>… а это означает, что мы не можем её решение получить быстрее…
Т.е. исходя из этого, можно предположить, что алгоритм таки решает задачу, но за бесконечное время?
Тогда да, можно решить любую задачу брутфорсом: пробовать все варианты из некоторого счетного множества…
Т.е. исходя из этого, можно предположить, что алгоритм таки решает задачу, но за бесконечное время?
Тогда да, можно решить любую задачу брутфорсом: пробовать все варианты из некоторого счетного множества…
Чтобы убрать не нужную терминологию, поясню, чтобы все поняли :)
Примером задачи класса P является к примеру сложение 10 чисел. Это можно сделать не быстрее, чем за 10 тактов. Делай ты это последовательно или параллельно.
Человек же это может сделать быстрее — если ему говорят сложи 1+1+1+1 — он за один такт скажет =4. А компьютер будет все время складывать 1+1+1+1
Примером задачи класса P является к примеру сложение 10 чисел. Это можно сделать не быстрее, чем за 10 тактов. Делай ты это последовательно или параллельно.
Человек же это может сделать быстрее — если ему говорят сложи 1+1+1+1 — он за один такт скажет =4. А компьютер будет все время складывать 1+1+1+1
Пример все же не очень удачный. Человек это не делает «за один такт». Ему все равно нужно посчитать сначала число единиц. Кроме того, сложить N чисел на параллельной машине можно за logN тактов.
Ну, я не согласен. Возьмем к примеру сложение чисел до 10. Скажем 2+2, 3+4 — вы ответ даете сразу? У меня дочка учится в школе, т.к. у них как раз требование — отвечать не считая! Не это ли требование одного такта?
А теперь перейдем к схемотехнике, сколько единичных тактов потребуется сумматору, чтобы осуществить такое сложение?
Далее давайте возьмем т.н. задачу (предикат) четность. Имеем скажем шахматную доску — как долго вы будете думать клеточек на доске четное число или нет? А есть ли у компьютера способ не считать клеточки?
сложить N чисел на параллельной машине можно за logN тактов — расскажите конкретный алгоритм который это сделает? Сомнительно для практики.
А теперь перейдем к схемотехнике, сколько единичных тактов потребуется сумматору, чтобы осуществить такое сложение?
Далее давайте возьмем т.н. задачу (предикат) четность. Имеем скажем шахматную доску — как долго вы будете думать клеточек на доске четное число или нет? А есть ли у компьютера способ не считать клеточки?
сложить N чисел на параллельной машине можно за logN тактов — расскажите конкретный алгоритм который это сделает? Сомнительно для практики.
Впрочем, нашел, видимо имеется введу алгоритмы каскадного суммирования
То, что ответ дается без счета, не значит, что он дается «за один такт». Память — это очень сложная система «кэширования», и поиск в памяти на подсознательном уровне требует большого числа операций.
(Но опять же про память — отдельный большой разговор)
(Но опять же про память — отдельный большой разговор)
>У меня дочка учится в школе, т.к. у них как раз требование — отвечать не считая!
Требуют кэшировать расчёты :) Таблица сложения — кэш для инкремента, таблица умножения — для сложения и т. п.
Требуют кэшировать расчёты :) Таблица сложения — кэш для инкремента, таблица умножения — для сложения и т. п.
Что такое «один такт» для человека?)
Посчитайте, пожалуйста, за «один такт» 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1.
Кроме того, согласен, бывают задачи, решение которых нельзя получить быстрее, чем за полиномиальное время. С учетом того, что f(x) = 0 — вполне себе полином, то это утверждение следует из того, что существуют задачи, которые нельзя решить за отрицательное время.
Посчитайте, пожалуйста, за «один такт» 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1.
Кроме того, согласен, бывают задачи, решение которых нельзя получить быстрее, чем за полиномиальное время. С учетом того, что f(x) = 0 — вполне себе полином, то это утверждение следует из того, что существуют задачи, которые нельзя решить за отрицательное время.
Знаете как это делается? считаете 10 единиц, а дальше выравниваете по длине — получаете все меньше, чем полиномиальное время.
Для справки: ru.wikipedia.org/wiki/Многочлен
0 и 1 — это вырожденные полиномы.
Полиномиальное время — время f(x) — где f — некоторый полином.
0 и 1 — это вырожденные полиномы.
Полиномиальное время — время f(x) — где f — некоторый полином.
и?
Реквестирую решение какой-нибудь задачи за время быстрее полинома P(x) = 0.
ну скорее всего он имел в виду «меньше, чем за O(N)» операций, где N — число единичек
И не O, а Ω, ибо 0 \in O(N).
Но тут возникает вопрос — как считать время? Во всех классических моделях нам понадобится линейное время уже на то, чтобы прочитать вход.
Но тут возникает вопрос — как считать время? Во всех классических моделях нам понадобится линейное время уже на то, чтобы прочитать вход.
Уже ближе.
Если для функции f существует машина Тьюринга M такая, что Cm(n) < n^c для некоторого числа c и достаточно больших n, то говорят, что она принадлежит классу P, или полиномиальна по времени. Cm(n) — сложность функции, зависящая от длины входного слова.
Очень метко замечено что такое «один такт» у человека )). Вообще рассуждать о процессах мышления часто начинают мыслить компьютероморфно. Что вряд ли правильно. Но tac правильно подметил — просто дело в том, что разум не решает задачи на которые он знает (помнит) ответ (если только разум не задался целью решить эту задачу еще раз). Дваждыдвачетыре для нас это не математическая задача с решением. Математической эта задача была наверное пару раз, когда родители нас учили складывать. Потом мы поимели некую связь нейронов, по которой постоянно бегает возбуждение и которая тут же отзывается на любые Дваждыдва, будь то увиденные или услышанные и мы думаем Четыре. И таких дваждыдва очень много и не только в математике. 254778+35678 это не сработает, для решения нужен будет алгоритм.
С другой стороны, заставь человека складывать эти два числа изо дня в день и он перестанет решать эту задачу математически
С другой стороны, заставь человека складывать эти два числа изо дня в день и он перестанет решать эту задачу математически
Об этом и речь.
Да, дальше надо говорить о памяти. Подождем подходящий пост )
Чтобы говорить о памяти, нужно обсудить проблему универсального индуктивного вывода (и общее теоретическое решение проблемы машинного обучения). Тогда разговор о памяти будет гораздо более содержательным.
Мы планируем написать статьи на эти темы.
Мы планируем написать статьи на эти темы.
Было бы очень интересно прочитать
Кое-что есть в книгах на нашем сайте ( aideus.ru/research/publications.html ), но там «много букв», и нет материала непосредственно в том виде, в котором есть желание об этом написать.
Да пожалуйста, вот Вам аналог такого подхода в виде программы:)
Все эти хитрости с памятью и т.д. работают только для задач небольшого (ограниченного некоторой константой) размера. Так что выигрыш получается максимум константым (может быть, константа мультипликативная, неважно).
def sum(a, b):
if a == 2 and b == 2:
return 4
return a+b
Все эти хитрости с памятью и т.д. работают только для задач небольшого (ограниченного некоторой константой) размера. Так что выигрыш получается максимум константым (может быть, константа мультипликативная, неважно).
Скорее как-то так:
TTL лень было расписывать :)
def sum(a, b, cache=dict()):
key = "{}+{}".format(a, b)
if key not in cache:
cache[key] = a + b
return cache[key]
TTL лень было расписывать :)
Хотя по хорошему не a+b должно быть, а два цикла (по a и b) с инкрментирующимся аккумулятором.
Ну человек всё же складывает в столбик, а не по единичкам. И, насколько я знаю, схемы складывают примерно так же.
Не видели как дети складывают 3 и 4? Загибают последовательно три пальца, потом ещё четыре, а потом считают сколько получилось всего. Когда они начинают складывать в столбик, то сложение однозначных чисел должно быть уже у них «закэшеровано», иначе придётся складывая многозначные числа в столбик «на бумажке», цифры всё равно складывать «на пальцах».
Это не говоря о том, что сложение в столбик возможно только в позиционных системах счисления, а, например, европейская цивилизация до неё не додумалась, заимствовала у азиатов в Средние века, до этого пользовались неудобными греческой и римской.
Это не говоря о том, что сложение в столбик возможно только в позиционных системах счисления, а, например, европейская цивилизация до неё не додумалась, заимствовала у азиатов в Средние века, до этого пользовались неудобными греческой и римской.
Суммы однозначных — да, должны быть «закешированы».
Вспомнился рассказ Азимова: lib.ru/FOUNDATION/feelpowr.txt
Вспомнился рассказ Азимова: lib.ru/FOUNDATION/feelpowr.txt
какой алгоритм будет использован тут для прочтения? где проще ошибку заметить?
берем достотачно простое слово с ошибкой, ведь ее не заметно?
lets take pretty simple word with an error, noticaeble?
берем достотачно простое слово с ошибкой, ведь ее не заметно?
lets take pretty simple word with an error, noticaeble?
#!/usr/bin/python3
from functools import lru_cache
<hh user=lru_cache>
def sum(a, b):
return a+b
Человек, скажу по секрету, за много-много тактов проделывает нетривиальные вещи, как-то:
— прочитать (распознать буквы) формулировку задачи
— осознать ее
— решить, стоит ли это делать вообще
— выбрать алгоритм алгоритма
— подумать «что за фигня»
— сбиться со счету
— пересчитать
— позлиться, что задача для детей 1-ого класса
— посчитать
— подумать, писать ли ответ, или это унижает
— написать комментарий
— пойти выпить чаю.
— прочитать (распознать буквы) формулировку задачи
— осознать ее
— решить, стоит ли это делать вообще
— выбрать алгоритм алгоритма
— подумать «что за фигня»
— сбиться со счету
— пересчитать
— позлиться, что задача для детей 1-ого класса
— посчитать
— подумать, писать ли ответ, или это унижает
— написать комментарий
— пойти выпить чаю.
Проблема все-же в NP-полных задачах. Задачи класса P как раз считаются «легкими». Но это отдельный длинный разговор.
Нет, проблема именно в задачах P. Почему-то все зациклились на задачах NP. Но никто почему то не ставит задачи БЫСТРЕЕ решать задачи P (вплоть до мгновенного ответа)… и в этой связи мне понравилось ваше вступление «Бессмыслица – искать решение, если оно и так есть.»
Спасибо. Интересное замечание, весьма подходит к разрабатываемой сейчас нами теории самооптимизирующегося универсального алгоритмического интеллекта.
Но все же если методично идти от рассмотрения алгоритмически неразрешимых задач (как их превращать в задачи NP), то потом нужно рассмотреть NP-полные задачи (как их превращать в задачи P), а только потом рассмотреть задачи класса P (как их решать максимально быстро).
Но все же если методично идти от рассмотрения алгоритмически неразрешимых задач (как их превращать в задачи NP), то потом нужно рассмотреть NP-полные задачи (как их превращать в задачи P), а только потом рассмотреть задачи класса P (как их решать максимально быстро).
Как-то у вас смешаны понятия алгоритма и работающей программы (системы). Алгоритм — это последовательность действий, служащая для преобразования входных данных в выходные, и когда данные преобразованы, алгоритм заканчивает свою работу. С другой стороны, программа — это работающая система, которая может реагировать на «внешние раздражители», обрабатывать полученную информацию с помощью алгоритмов и продолжать работать. Вы же не назовёте веб-сервер алгоритмом, веб-сервер — это система, взаимодействующая с пользователями через сеть (хотя обработчик запроса — это уже алгоритм). И тут уже можно провести чёткую аналогию с человеком: человек — это тоже система, которая может реагировать на внешние раздражители и применять алгоритмы для решения конкретных задач (умножение чисел в столбик), но это никак не сам алгоритм, предназначенный для решения конкретной задачи (цели жизни). Я не имею ничего против рассуждений о программах, работающих без остановки, но теория алгоритмов уже довольно хорошо проработана, и расширение её ключевого понятия требует переосмысления всей теории, а кому оно надо.
А в целом за статью спасибо, приятно было вспомнить такие фундаментальные вопросы как неполнота формальных систем :)
А в целом за статью спасибо, приятно было вспомнить такие фундаментальные вопросы как неполнота формальных систем :)
Пожалуйста и тоже спасибо.
Под программой в статье в основном понимается программа для машины Тьюринга, то есть тоже алгоритм.
Действительно, реальная работающая программа несводима к своей модели — алгоритму. В статье на это лишь намекается, но, возможно, следовало бы этот аспект обсудить в явном виде.
Что касается «хорошо проработанной теории алгоритмов», в действительности, это не совсем так (а, может, и далеко не так). Хорошо проработаны далеко не все ее аспекты. Кому надо переосмыслять эту теорию? Разработчикам моделей универсального ИИ. И некоторыми из них это, собственно, и делается. Особенно интересна связь теории алгоритмов и теории информации. Хотя алгоритмическая теория информации была развита Колмогоровым и Соломоновым достаточно давно, сейчас становится понятной необходимость обобщения алгоритмической сложности по Колмогорову с учетом вычислительной сложности (получается т.н. сложность по Левину)… В общем, тут масса всего интересного и еще непроработанного.
Под программой в статье в основном понимается программа для машины Тьюринга, то есть тоже алгоритм.
Действительно, реальная работающая программа несводима к своей модели — алгоритму. В статье на это лишь намекается, но, возможно, следовало бы этот аспект обсудить в явном виде.
Что касается «хорошо проработанной теории алгоритмов», в действительности, это не совсем так (а, может, и далеко не так). Хорошо проработаны далеко не все ее аспекты. Кому надо переосмыслять эту теорию? Разработчикам моделей универсального ИИ. И некоторыми из них это, собственно, и делается. Особенно интересна связь теории алгоритмов и теории информации. Хотя алгоритмическая теория информации была развита Колмогоровым и Соломоновым достаточно давно, сейчас становится понятной необходимость обобщения алгоритмической сложности по Колмогорову с учетом вычислительной сложности (получается т.н. сложность по Левину)… В общем, тут масса всего интересного и еще непроработанного.
Я имею ввиду, что есть ряд техник, практик и теорий, опирающиеся на «классические» определения алгоритма (например то, которое приводит Кнут). Возьмём тот же вопрос об окончании работы алогиртма и простой пример — рекурсивную функцию факториала. Классическая теория алгоритмов чётко говорит: алгоритм всегда должен иметь окончание, а во время выполнения должен сохранять некоторые инварианты. Если человек, проектирующий алгоритм рекурсивного вычисления факториала, знаком с этой теорией, для него структура функции будет очевидна — сначала проверить на условие окончания, потом вызвать функцию рекурсивно, при этом проверив, что инварианты при рекурсивном вызове сохранены. Если отменить условие конечности алгоритма. теоретическая база проверки корректности просто развалится. Придётся придумать какие-то новые условия, сохраняющиеся как для конечных, так и для бесконечных алгоритмов. А представьте какой это вызовет разброс в литературе, где половина книг будет использовать одно определение термина, другая половина — другое определение. Поэтому на мой взгляд гораздо проще и правельней будет просто ввести новое понятие (будь то «работающая система», «неконечные алгоритмы», «надалгоритмы» или что угодно),
Непонятно, зачем сначала составлять алгоритм, а только потом проверять, остановится он или нет, когда можно сразу составлять алгоритм так, чтоб он останавливался.
Время выполнения алгоритма не менее важно, чем его программа. Возможно следует рассматривать подмножество алгоритмов, время выполнения(максимальное, минимальное) которых можно легко(за малое почти постоянное время) вычислить или оценить не выполняя самого алгоритма t_алгоритма=алгоритм_расчета_времени(входные_данные).
Для этого достаточно дополнить каждый алгоритм временем его выполнения и использовать правила составления алгоритмов, сохраняющие легкость алгоритма_расчета_времени.
Очевидно, что любой алгоритм подмножества остановится, если алгоритм_расчета_времени выдает значение меньшее бесконечности. Это похоже на синтезируемое в кремний подмножество программ, только для времени, а не пространства.
Да это подмножество всегда можно расширить, изменив правила комбинации алгоритмов или добавив новую пару (t_алгоритма, программа_алгоритма), но такое ограничение как минимум позволяет осуществлять эффективное распараллеливание и прозрачное многоуровневое планирование собственной деятельности. К тому же, раз это подмножество всегда можно расширить, то его ограниченность не столь существенна. Алгоритм составления алгоритма решения какой-либо задачи все еще может не остановится, а полученный алгоритм быть неоптимальным. Зато можно быть уверенным, что он решает задачу за определенное время.
P.S. Все вышесказанное имеет очень отдаленную связь с сильным ИИ, сознание можно рассматривать как странный аттрактор, отсюда сложности его алгоритмизируемости.
Время выполнения алгоритма не менее важно, чем его программа. Возможно следует рассматривать подмножество алгоритмов, время выполнения(максимальное, минимальное) которых можно легко(за малое почти постоянное время) вычислить или оценить не выполняя самого алгоритма t_алгоритма=алгоритм_расчета_времени(входные_данные).
Для этого достаточно дополнить каждый алгоритм временем его выполнения и использовать правила составления алгоритмов, сохраняющие легкость алгоритма_расчета_времени.
Очевидно, что любой алгоритм подмножества остановится, если алгоритм_расчета_времени выдает значение меньшее бесконечности. Это похоже на синтезируемое в кремний подмножество программ, только для времени, а не пространства.
Да это подмножество всегда можно расширить, изменив правила комбинации алгоритмов или добавив новую пару (t_алгоритма, программа_алгоритма), но такое ограничение как минимум позволяет осуществлять эффективное распараллеливание и прозрачное многоуровневое планирование собственной деятельности. К тому же, раз это подмножество всегда можно расширить, то его ограниченность не столь существенна. Алгоритм составления алгоритма решения какой-либо задачи все еще может не остановится, а полученный алгоритм быть неоптимальным. Зато можно быть уверенным, что он решает задачу за определенное время.
P.S. Все вышесказанное имеет очень отдаленную связь с сильным ИИ, сознание можно рассматривать как странный аттрактор, отсюда сложности его алгоритмизируемости.
Вовсе нет! Это как раз имеет прямую связь с сильным ИИ. Как раз простейшие расширения модели универсального алгоритмического интеллекта (типа AIXItl) что-то отдаленно похожее и делают.
Рассуждать же в терминах странных аттракторов, конечно, можно, но все же не слишком продуктивно. Эти странные аттракторы, которые в теории динамических систем выглядят почти что чудом, в теории алгоритмов достаточно заурядны (в силу существенной нелинейности алгоритмов).
Рассуждать же в терминах странных аттракторов, конечно, можно, но все же не слишком продуктивно. Эти странные аттракторы, которые в теории динамических систем выглядят почти что чудом, в теории алгоритмов достаточно заурядны (в силу существенной нелинейности алгоритмов).
странный аттрактор программы, а не данных.
что-то вроде jmp random(). Не совсем понял, что значит «в теории алгоритмов достаточно заурядны», можно какой-нибудь пример.
Да Вы его сами и привели. Генератор псевдослучайных чисел — это простейший пример дискретной динамической системы, работающей в режиме странного (вернее, хаотического) аттрактора.
Если бы этот пример много прояснял, я бы не просил привести еще. Реализация аттрактора это не то. Аттрактор относится состоянию системы(управляющей программе)+внешней среды. Разница такая же как между тем, чтобы испытывать какую-то эмоцию(аттрактор) и описывать. Некоторые участки странного аттрактора образуют эвристические правила, применимые только к текущей ситуации. Цель можно рассматривать как искусственный аттрактор.
Если задать в качестве цели самосохранение и размножение, получим искусственную живую особь. Если наделить агента способностью моделировать окружающую среду, то получим сознательную особь. Если добавить способность моделировать других агентов — разумную с их точки зрения особь.
Уместно вспомнить о законах робототехники, т.е. нужно заранее моделировать все важные возможные последствия достижения целей.
Если задать в качестве цели самосохранение и размножение, получим искусственную живую особь. Если наделить агента способностью моделировать окружающую среду, то получим сознательную особь. Если добавить способность моделировать других агентов — разумную с их точки зрения особь.
Уместно вспомнить о законах робототехники, т.е. нужно заранее моделировать все важные возможные последствия достижения целей.
Речь о том, что понятие аттракторов возникло для систем, описываемых дифференциальными уравнениями. Его расширение на дискретные системы возможно, но не особо интересно. Например, экспоненциальная расходимость для потоков — достаточно естественное представление, тогда как в случае алгоритмов оно весьма неестественно. Любой if...else… делает алгоритм «неустойчивым» с «мгновенной» расходимостью его ветвей. При куче if'ов у вас сразу будет существенная нелинейность (расходимость «почти в каждой точке») при том, что алгоритмический процесс будет «оставаться в ограниченной области фазового пространства». Для алгоритмов это достаточно банальная ситуация. Для любой сложной информационной системы это банальная ситуация. Странные аттракторы возникают даже в очень простых системах типа Лоренца. Поэтому описание работы мозга как странного аттрактора очень неспецифично… В этой связи и описание цели как аттрактора возможно, но не слишком продуктивно. В этом есть некоторый смысл, но не следует его слишком абсолютизировать. Однако это тоже тема для отдельного большого разговора.
«Поэтому описание работы мозга как странного аттрактора очень неспецифично.» Не согласен, вполне логично рассматривать мозг как динамическую систему. А так как такой подход более общий(алгоритмический процесс слишком уж привязан к языковому описанию), то возможно именно он позволит решить алгоритмические трудности.
Но спасибо за разъяснение.
Но спасибо за разъяснение.
Дело в том, что сложность безостановочных алгоритмов может неограниченно возрастать, в то время как алгоритмы, от которых требуется остановка за заранее определенное (в самом алгоритме или исходных данных) число шагов, действительно обладают ограниченными возможностями.
А вот про эти вещи есть какая-нибудь литература. Очень интересный тезис.
P.S. Статья супер, яростно плюсую. Вообще, можно ещё добавить то, что обычно критика компьютерного ИИ основывается именно на модели классического алгоритма, машина Тьюринга и т.д. Но тонкость в том, что компьютер умет не только выполнять алгоритмы, но ещё и получать данные извне, и влиять на свой вход (допустим, робот), и это тоже может быть дополнительным источником (в терминах процитированного) увеличения сложности и самоорганизации.
А вот про эти вещи есть какая-нибудь литература. Очень интересный тезис.
P.S. Статья супер, яростно плюсую. Вообще, можно ещё добавить то, что обычно критика компьютерного ИИ основывается именно на модели классического алгоритма, машина Тьюринга и т.д. Но тонкость в том, что компьютер умет не только выполнять алгоритмы, но ещё и получать данные извне, и влиять на свой вход (допустим, робот), и это тоже может быть дополнительным источником (в терминах процитированного) увеличения сложности и самоорганизации.
Про литературу вопрос сложный.
По алгоритмической теории информации ее много. Там сложность индивидуального объекта (строки) определяется как длина кратчайшей программы, которая печатает эту строку и останавливается.
Отсюда следует банальный вывод, что любая программа, которая печатает некоторый ответ и останавливается, не может породить строку, более сложную, чем она сама.
Интереснее рассмотреть вопрос, какой сложности строки может порождать безостановочная программа (и вот на этот счет с литературой как-то хуже). Очевидно, такая программа может порождать строки любой сложности!
Действительно, можно представить себе мата-алгоритм, который перебирает все прочие алгоритмы. Если такой мета-алгоритм должен остановиться, то в нем должен быть зашит некий критерий остановки, и чем сложнее тот алгоритм, который мы хотим породить на выходе, тем сложнее должен быть критерий остановки. В итоге все равно получим, что сложность ответа будет не выше сложности порождающего алгоритма с необходимым критерием. Скажем, если мы на выходе хотим получить алгоритм ИИ, то переборный останавливающийся алгоритм окажется не проще, чем этот самый ИИ!
Безостановочный же переборный алгоритм сможет породить все, что угодно на выходе, оставаясь при этом простым (естественно, останется вопрос, как из этого «всего, что угодно» будет выбираться «то, что нужно»).
Но это просто утрированный пример для демонстрации различий в сложности выхода, даваемого остановочными и безостановочными алгоритмами.
По алгоритмической теории информации ее много. Там сложность индивидуального объекта (строки) определяется как длина кратчайшей программы, которая печатает эту строку и останавливается.
Отсюда следует банальный вывод, что любая программа, которая печатает некоторый ответ и останавливается, не может породить строку, более сложную, чем она сама.
Интереснее рассмотреть вопрос, какой сложности строки может порождать безостановочная программа (и вот на этот счет с литературой как-то хуже). Очевидно, такая программа может порождать строки любой сложности!
Действительно, можно представить себе мата-алгоритм, который перебирает все прочие алгоритмы. Если такой мета-алгоритм должен остановиться, то в нем должен быть зашит некий критерий остановки, и чем сложнее тот алгоритм, который мы хотим породить на выходе, тем сложнее должен быть критерий остановки. В итоге все равно получим, что сложность ответа будет не выше сложности порождающего алгоритма с необходимым критерием. Скажем, если мы на выходе хотим получить алгоритм ИИ, то переборный останавливающийся алгоритм окажется не проще, чем этот самый ИИ!
Безостановочный же переборный алгоритм сможет породить все, что угодно на выходе, оставаясь при этом простым (естественно, останется вопрос, как из этого «всего, что угодно» будет выбираться «то, что нужно»).
Но это просто утрированный пример для демонстрации различий в сложности выхода, даваемого остановочными и безостановочными алгоритмами.
А вы бы не могли дать ссылку на работу, доказывающую гипотезу Гольдбаха? Мне казалось, что доказано только слабое утверждение Гольбаха, его еще Виноградов доказал, для очень больших чисел.
Заранее благодарен!
Заранее благодарен!
Одному мне показалось, что в приведенной формулировке задачи об остановке не все в порядке?
Алгоритм-то должен не доказывать факт остановки при конкретных данных, а проверять возмонжость не остановки при любых данных.
При этом он, как я понимаю, может работать с входным алгоритмом как с белым ящиком.
Я не утверждаю, что разработка такого алгоритма возможна, просто показываю, что доказательство, приведенное в статье явно упрощено до некорректности.
Алгоритм-то должен не доказывать факт остановки при конкретных данных, а проверять возмонжость не остановки при любых данных.
При этом он, как я понимаю, может работать с входным алгоритмом как с белым ящиком.
Я не утверждаю, что разработка такого алгоритма возможна, просто показываю, что доказательство, приведенное в статье явно упрощено до некорректности.
Нет, в статье неправильно сформулирована проблема останова:)
На самом деле она заключается в вопросе «останавливается ли данный алгоритм на пустом входе» (или в эквивалентной ей «останавливается ли данный алгоритм на данном входе»). Эта задача даже проще, чем «останавливается ли данный алгоритм на любом входе».
На самом деле она заключается в вопросе «останавливается ли данный алгоритм на пустом входе» (или в эквивалентной ей «останавливается ли данный алгоритм на данном входе»). Эта задача даже проще, чем «останавливается ли данный алгоритм на любом входе».
«останавливается ли данный алгоритм на данном входе»
Но нужно ведь представить общее решение проблемы останова (то есть представить один алгоритм, который эту задачу решает для всех случаев). Куда в Вашей формулировке все кванторы-то делись? В чем «неправильность формулировки» в статье по сравнению с Вашей формулировкой?
Но нужно ведь представить общее решение проблемы останова (то есть представить один алгоритм, который эту задачу решает для всех случаев). Куда в Вашей формулировке все кванторы-то делись? В чем «неправильность формулировки» в статье по сравнению с Вашей формулировкой?
Формулировка проблемы останова: по T и Y определить, существует ли X — протокол для машины T на входе Y.
Ваша формулировка: по T определить, верно ли, что для любого входа Y существует X — протокол для машины T на входе Y.
Ваша формулировка: по T определить, верно ли, что для любого входа Y существует X — протокол для машины T на входе Y.
Хорошо, в тексте статьи написано немного неаккуратно. Но суть-то в том, что неразрешимой является данная проблема в общем виде, то есть когда необходимо построить алгоритм, который для любого T и для любого Y позволяет определить существование X. Поскольку «для любого Y» при постановке этой проблемы все равно появляется, то абсолютно не важно, трактовать ли задачу останова для конкретного Y или сразу для любого. Вы же вообще не формулирует ту проблему, которая является неразрешимой. В формулировке «останавливается ли данный алгоритм на данном входе» не подразумевается, что «данный алгоритм» и «данный вход» могут быть любыми. Для «данного алгоритма и данного входа» может существовать такой алгоритм, который правильно отвечает на поставленный вопрос.
Почитайте, что ли, википедию про кванторы, формальные теории и машину Тьюринга…
Проблема останова: функция f:(машины Тьюринга)x(входы) -> {0, 1}. f(T, Y) = 1 тогда и только тогда, когда T останавливается на входе Y.
Ваша формулировка: функция g: (машины Тьюринга) -> {0, 1}. g(T) = 1 тогда и только тогда, когда T останавливается на любом входе.
Машина с оракулом g способна вычислить f.
Машина с оракулом f неспособна вычислить g.
Нумерация предполагается главной.
Проблема останова: функция f:(машины Тьюринга)x(входы) -> {0, 1}. f(T, Y) = 1 тогда и только тогда, когда T останавливается на входе Y.
Ваша формулировка: функция g: (машины Тьюринга) -> {0, 1}. g(T) = 1 тогда и только тогда, когда T останавливается на любом входе.
Машина с оракулом g способна вычислить f.
Машина с оракулом f неспособна вычислить g.
Нумерация предполагается главной.
Вы опять кванторы потеряли. Верните их и все поймете. Если википедия в этом Вам не поможет, можно почитать и нормальные учебники.
Так, мне надоело.
Пусть b — главная нумерация машин Тьюринга.
f: NxN -> N, f(n, m) = (останавливается МТ b(n) на входе m? 1: 0)
g: N -> N, g(n) = f(n, 0)
k: N -> N, k(n) = (\forall m f(n, m) == 1? 1: 0)
Проблема останова — это задача о вычислении f. Сформулированная Вами проблема — задача о вычислении g.
Пусть S(n, m, k) — результат работы МТ b(n) с функцией k в качестве оракула на входе m.
Утверждение 1. \exists n \forall m S(n, m, k) = g(m)
Утверждение 2. \forall n \exists m S(n, m, g) != k(m)
Утверждение 3. Человек, рассуждающий о теории алгоритмов, должен иметь объем знаний в этой области не меньший, чем содержится в википедии. Лучше — больший.
Утверждение 4. При разговоре о разрешимости задача вычислимость всегда подразумевается равномерной (т.е. один алгоритм для всех входов). Потому что если разрешить алгоритму зависеть от входа (невычислимым образом), то любая функция становится вычислимой.
Пусть b — главная нумерация машин Тьюринга.
f: NxN -> N, f(n, m) = (останавливается МТ b(n) на входе m? 1: 0)
g: N -> N, g(n) = f(n, 0)
k: N -> N, k(n) = (\forall m f(n, m) == 1? 1: 0)
Проблема останова — это задача о вычислении f. Сформулированная Вами проблема — задача о вычислении g.
Пусть S(n, m, k) — результат работы МТ b(n) с функцией k в качестве оракула на входе m.
Утверждение 1. \exists n \forall m S(n, m, k) = g(m)
Утверждение 2. \forall n \exists m S(n, m, g) != k(m)
Утверждение 3. Человек, рассуждающий о теории алгоритмов, должен иметь объем знаний в этой области не меньший, чем содержится в википедии. Лучше — больший.
Утверждение 4. При разговоре о разрешимости задача вычислимость всегда подразумевается равномерной (т.е. один алгоритм для всех входов). Потому что если разрешить алгоритму зависеть от входа (невычислимым образом), то любая функция становится вычислимой.
О, это уже ближе к правде. Только с чего Вы взяли, что «Сформулированная Вами проблема — задача о вычислении g.». Откуда там пустой вход-то взялся?
Или Вы не про фразу «Проблема же заключается в том, что доказано отсутствие алгоритма, который бы мог решить задачу останова для любой программы.» (создавалось впечатление, что про нее), а про описанную на пальцах идею доказательства? Так она и не претендует на строгость, но саму идею-то передает верно. Еще нигде не встречалось популярное изложение какой-то проблемы, которое не было бы упрощено до некорректности, как выразился Fahrenheit.
Или Вы не про фразу «Проблема же заключается в том, что доказано отсутствие алгоритма, который бы мог решить задачу останова для любой программы.» (создавалось впечатление, что про нее), а про описанную на пальцах идею доказательства? Так она и не претендует на строгость, но саму идею-то передает верно. Еще нигде не встречалось популярное изложение какой-то проблемы, которое не было бы упрощено до некорректности, как выразился Fahrenheit.
Ой-ой-ой, у меня лишний сдвиг по буквам обозначений. Проблема останова — это задача о вычислении g, сформулированная Вами задача — это задача о вычислении k.
В формулировке: «Задача останова заключается в том, что необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается» (работает бесконечно долго)» — написано «в некоторых случаях», а не «по крайней мере в одном». Надеюсь, Вы не будете придираться еще к тому, что если в этой фразе «ИЛИ» считать логическим, то в такой формулировке задача станет очевидно разрешимой? ))
Вроде, достаточно очевидно, что нас интересует не то, что для всех m f(n,m)==1, а то, что его можно определить для всех m. Для практике же важно установить не просто вычислимость f, но и то, какие именно значения она принимает, поэтому здесь и есть некий уклон в сторону останавливаемости при любых исходных данных. Так что в этой формулировке (с точностью до ее нестрогости, вытекающей из неопределенности естественного языка) ошибки нет.
Вроде, достаточно очевидно, что нас интересует не то, что для всех m f(n,m)==1, а то, что его можно определить для всех m. Для практике же важно установить не просто вычислимость f, но и то, какие именно значения она принимает, поэтому здесь и есть некий уклон в сторону останавливаемости при любых исходных данных. Так что в этой формулировке (с точностью до ее нестрогости, вытекающей из неопределенности естественного языка) ошибки нет.
необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается»
Т.е. Вы хотите по программе определить, существует ли вход, на котором она зависает.
Это — не проблема останова. Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данном входе.
Сформулированная Вами задача сложнее проблемы останова в том смысле, что проблема останова к ней сводится, обратное неверно.
Т.е. Вы хотите по программе определить, существует ли вход, на котором она зависает.
Нет. Ставится вопрос, существует ли алгоритм, который может проверить для любого данного входа, зависает или останавливается другой алгоритм на данном входе.
Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данном входе.
Три раза прочитал, так и не понял разницы в этих двух задачах. Действительно, эквивалентные задачи…
Последний раз хочется спросить: когда Вас просят решить задачу «зависает ли данная программа на данном входе» в общем виде, что это, по-Вашему, означает? Вы же сами написали, что для любой программы и для любого входа существует алгоритм, который правильно отвечает на вопрос о том, зависает ли данный алгоритм на данном входе.
Короче, вообще непонятно, о чем весь этот разговор, кроме как о неоднозначности естественного языка.
Второй раз разговариваем, и второй раз Вы воюете с ветряными мельницами, превратно интерпретируя слова (или это банальный троллинг?).
Нет. Ставится вопрос, существует ли алгоритм, который может проверить для любого данного входа, зависает или останавливается другой алгоритм на данном входе.
Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данном входе.
Три раза прочитал, так и не понял разницы в этих двух задачах. Действительно, эквивалентные задачи…
Последний раз хочется спросить: когда Вас просят решить задачу «зависает ли данная программа на данном входе» в общем виде, что это, по-Вашему, означает? Вы же сами написали, что для любой программы и для любого входа существует алгоритм, который правильно отвечает на вопрос о том, зависает ли данный алгоритм на данном входе.
Короче, вообще непонятно, о чем весь этот разговор, кроме как о неоднозначности естественного языка.
Второй раз разговариваем, и второй раз Вы воюете с ветряными мельницами, превратно интерпретируя слова (или это банальный троллинг?).
Опечатался.
Предъявить алгоритм, который, получив на вход программу T и вход X скажет, останавливается ли T на X.
Вроде бы довольно четко указано, что мы разделяем программы на всегда останавливающиеся и на иногда зависающие.
Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа наданномпустом входе.
когда Вас просят решить задачу «зависает ли данная программа на данном входе» в общем виде, что это, по-Вашему, означает?
Предъявить алгоритм, который, получив на вход программу T и вход X скажет, останавливается ли T на X.
необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается»
Вроде бы довольно четко указано, что мы разделяем программы на всегда останавливающиеся и на иногда зависающие.
Я знаю звучит как бред) но может расстройства психики как раз и есть алгоритмическая неразрешимость у человека. Если предположить что это так, то мышление поддается алгоритмизации, просто на данном этапе не хватает данных и мощности (как мне кажется Google будет первым кто создаст ИИ)
А если мышление можно описать алгоритмом, то все что нужно для решения любой неразрешимой задачи, дополнительные данные.
А если мышление можно описать алгоритмом, то все что нужно для решения любой неразрешимой задачи, дополнительные данные.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмическая неразрешимость – это не препятствие для алгоритмического ИИ