Пользователь
0,0
рейтинг
16 июня 2012 в 13:32

Алгоритмическая неразрешимость – это не препятствие для алгоритмического ИИ

В замечательном произведении Аркадия и Бориса Стругацких «Понедельник начинается в субботу» есть такой диалог:
– Голубчики, – сказал Фёдор Симеонович озабоченно, разобравшись в почерках. – Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.
– Мы сами знаем, что она не имеет решения, – сказал Хунта, немедленно ощетиниваясь. – Мы хотим знать, как её решать.
– Как-то странно ты рассуждаешь, Кристо… Как же искать решение, когда его нет? Бессмыслица какая-то…
– Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица – искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен.

Решение неразрешимых задач – это не просто художественная метафора. Поспорить здесь можно лишь с тем, что этот вопрос принципиален не в меньшей степени и для практики. Как это ни парадоксально, вся область искусственного интеллекта посвящена, по сути, решению неразрешимых и плохо поставленных задач. Но что это за задачи?
Первые выводы о неразрешимости некоторых математических проблем были получены Гёделем в 1931 г. Наиболее известными являются две теоремы Гёделя о неполноте формальной арифметики. Их сущность в следующем. Если мы возьмем набор непротиворечивых аксиом, описывающих свойства чисел и арифметических операций над ними, то будут существовать некоторые утверждения о числах, которые не могут быть ни доказаны, ни опровергнуты на основе выбранных аксиом (такие утверждения называются невыводимыми). Более того, некоторые из этих утверждений являются вполне естественными истинными (с точки зрения человека) утверждениями. Чтобы «доказать» эти утверждения, приходится вводить новые аксиомы. Но какую бы мы формальную систему ни взяли, всегда найдутся утверждения об объектах системы, истинность которых не может быть установлена в рамках самой системы. Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат. Что должно это значить? Некоторые мыслители делают вывод о невозможности формализации мышления, особенно его творческой составляющей. А поскольку машина Тьюринга – тоже формальная система, они полагают, будто мышление невозможно реализовать на компьютере.

Действительно, некоторые задачи не имеют полного алгоритмического решения. Наиболее широко известной является проблема останова. Задача останова заключается в том, что необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается» (работает бесконечно долго). Проблема же заключается в том, что доказано отсутствие алгоритма, который бы мог решить задачу останова для любой программы. Иными словами, задача останова является алгоритмически неразрешимой. Важность проблемы останова связана с тем, что, как принято считать, некоторый алгоритм решил некоторую задачу, если он остановился, когда состояние ленты соответствует ответу. Если останова не происходит, то считается, что задача не решена, поскольку не понятно, в какой момент времени на ленте оказывается решение. Алгоритм, который решает задачу останова, тоже должен останавливаться, на чем и основывается доказательство неразрешимости проблемы останова. В этом доказательстве используется аналог парадокса лжеца. Парадокс возникает, если составить утверждение, отсылающее к самому себе. Например, является ли ложным следующее высказывание лжеца: «Я всегда лгу, даже сейчас»? Как ту же хитрость использовать для проблемы останова?..
Рассмотрим идею доказательства неразрешимости проблемы останова от противного. Пусть она разрешима, то есть существует алгоритм T, которому на вход можно подать некоторую программу, и он напечатает 0, если программа «зацикливается», и 1 – если останавливается. Рассмотрим такую программу P, которая просто вызывает алгоритм T, передавая на вход свое описание T(P), и, если алгоритм T вернул 0, алгоритм P останавливается, а если алгоритм T вернул 1, алгоритм P преднамеренно «зацикливается», запуская бесконечный цикл. Для любого алгоритма T несложно составить программу P, которая, очевидно, существует. Но что будет, если эту программу запустить? Зациклится ли она или остановится? Если программа P останавливается, тогда алгоритм T, предположительно решающий проблему останова для любой программы, при вызове T(P) должен вернуть 1, но тогда программа P должна зациклиться. Если программа P зацикливается, тогда алгоритм T(P) должен вернуть 0, но тогда программа P должна была бы остановиться. Пришли к противоречию, то есть исходное допущение о существовании алгоритма T неверно.

Существует множество и других алгоритмически неразрешимых задач. В частности, алгоритмически неразрешимой является десятая проблема Гильберта о диофантовых уравнениях, доказательство чего в 1970 году было завершено советским математиком Юрием Владимировичем Матиясевичем. Оказывается, при наличии решения, его можно получить за конечное (но неограниченное) число шагов, но если решения нет, в произвольном случае ни один алгоритм это установить не может.
Решения некоторых проблем до сих пор не найдены, и неизвестно, являются ли эти проблемы неразрешимыми. Иногда у них удивительно простые формулировки. К одной из старейших таких проблем является проблема Эйлера середины XVIII века: любое четное число не меньше четырех можно представить в виде суммы двух простых чисел (4 = 2+2,… 18 = 5+13, …). Эту проблему Эйлер сформулировал в ответ на гипотезу Гольдбаха, согласно которой любое нечетное число не меньше семи можно представить в виде суммы трех простых чисел. Гипотеза Гольдбаха была не так давно доказана, тогда как проблема Эйлера до сих пор не решена. Вероятно, это не относится к проблеме Эйлера, но некоторые математические утверждения могут быть истинные, но недоказуемые (невыводимые, алгоритмически неразрешимые) в рамках данной аксиоматики, о чем и говорит теорема Гёделя.
Неужели возможности алгоритмов настолько ограничены, и на основе компьютеров можно создать только неуниверсальный, слабый ИИ? Значит ли это, что мышление действительно неалгоритмизуемо? Чтобы разобраться в этом, нужно учитывать ряд моментов.

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

Представьте себя в ситуации, аналогичной той, в которой оказывается программа T в нашем доказательстве. Пусть имеется автомат, который печатает 0, если вы говорите 1, и печатает 1, если вы говорите 0. И вас просят ответить на вопрос, что напечатает автомат. При этом вам разрешено сказать только 0 или 1. Естественно, автомат напечатает противоположное тому, что вы сказали, и вы об этом знаете, но ничего сделать не можете. Не кажется ли, что такая «задача» была бы просто издевательством над вами?
У такого эксперимента есть интересная практическая реализация: дело в том, что осознание многих решений происходит несколько позже (иногда более чем на полсекунды), чем это решение возникает в мозгу. Простейшие решения (выбор из двух альтернатив, скажем, поднятие правой или левой руки) можно детектировать в виде потенциала готовности еще до того, как они оказываются осознанными. В действительности, момент осознания соответствует не моменту принятия решения; он «откладывается» до момента совершения самого действия – именно поэтому мы не замечаем задержки в выполнении телом осознанных команд (у больных с нарушенным механизмом задержки может возникать впечатление, что ими управляют извне). Подобные эксперименты с использованием электромиографов, фиксирующих мышечные биотоки, а позднее – электроэнцефалографов, «считывающих» некоторую информацию прямо с мозга, проводились, начиная с 1970-х гг. Интересно, что человека просят самого выбирать, какую руку и в какой момент поднимать, оставляя ему полную свободу воли. И, тем не менее, машина, получающая ЭЭГ-сигнал, узнает о решении испытуемого до него самого. Пусть одна рука человека означает 0, а другая – 1, и пусть машина печатает число, противоположное числу, выбранному человеком. Если испытуемому нужно будет угадать, что печатает машина, он никогда не сможет правильно выбрать ответ, хотя автомат машина будет показывать ответ почти за секунду до того, как выбор человека будет возникать в его сознании. Эта проблема «человечески неразрешима».

А ведь алгоритм T находится именно в такой ситуации: с него считывается информация о выборе, как и с мозга в примере с человеком. Нельзя выбрать правильный ответ, когда правильность ответа меняется от самого выбора. Причем здесь мы требуем, чтобы алгоритм T обязательно напечатал 0 или 1, а в качестве входа у него выступала только программа P. Какой-нибудь другой алгоритм, «видя», что анализируемая программа сама его вызывает, мог бы напечатать и что-нибудь другое, скажем, 42. Даже если бы алгоритм T был сверхинтеллектуальным и полностью понимал ситуацию, он мог бы разве что описать экспериментаторам все, что о них думает, но правильный ответ о зацикливании программы P дать не смог бы. И дело тут вряд ли в ограниченности понятия алгоритма. Действительно, если предположить, что создано некоторое неалгоритмическое устройство, решающее проблему останова, к нему можно применить приведенные выше рассуждения, просто заменив термин «алгоритм» другим термином, например, «устройство неалгоритмического преобразования информации».
В действительности, такие гипотетические устройства Тьюрингом были рассмотрены еще в 1939 году. Это машины с оракулом. Под оракулом понимается некая сущность, способная «вычислять» невычислимые функции или решать алгоритмически неразрешимые проблемы. Тьюринг показал, что для таких машин проблемы, сформулированные относительно них самих (например, проблема останова машины с оракулом) ими же являются неразрешимыми. Это напоминает древний парадокс: может ли всемогущий бог создать камень, который сам не сможет поднять?.. Поэтому даже если сверхтьюринговые вычисления физически реализуемы, для них также найдутся неразрешимые проблемы. Видимо, что-то не так с самой формой постановки этих проблем, неразрешимых ни алгоритмически, ни божественно.

Следует иметь в виду, что доказательство алгоритмической неразрешимости некоторой задачи зачастую заключается в сведении задачи к проблеме останова, которая неразрешима просто в силу того, что любой фиксированный алгоритм не может быть сложнее самого себя. И, тем не менее, факт существования «алгоритмически неразрешимых» проблем остается; вопрос лишь в том, как его интерпретировать.
Вторым существенным моментом является то, что выполняемые компьютерные программы, хотя и имеют форму алгоритмических процессов, не являются формальными алгоритмами. Есть важное отличие реального компьютера от машины Тьюринга – это его взаимодействие с внешним миром. В машине Тьюринга содержимое ленты фиксировано и меняется только самой машиной. В компьютер могут поступать новые данные и даже программы в процессе его работы. Как человек выходит за рамки формальных систем, например, откуда он знает, какие утверждения, невыводимые в формальной арифметике, считать истинными, а какие – ложными? Ответ прост – из опыта. Для человека «входная лента» – потенциально вся Вселенная (где на некотором языке «записаны» алгоритмы мышления, которые мозгом, как универсальной машиной, лишь исполняются). Выбор аксиом в математике произволен, но интересные аксиомы выбираются так, чтобы описывать что-то в реальном мире. Дирак писал: «…те принципы, которые находит интересными математик, оказываются как раз теми, которые выбраны Природой». Но, по сути, математикам неоткуда брать свои аксиомы и принципы, кроме как из обобщения опыта. Более сложным является вопрос, каков алгоритм этого обобщения, и алгоритм ли это.

Искусственный интеллект, реализованный на компьютере, будет ограниченным только в том случае, если он будет полностью изолирован от мира. Тогда он действительно будет представлять собой формальную систему, к которой применим результат теоремы Гёделя, и уметь только то, что мы в него заложили. Если же для физически реализованного алгоритмического процесса «входной лентой» будет также вся Вселенная, то для него указанная постановка проблемы останова будет просто некорректной: на входной ленте у программной реализации алгоритма T кроме программы P будет еще и сам алгоритм T, и многое другое. Кроме того, программа P не сможет обратиться к работающей копии алгоритма T и только лишь вызовет другую его копию, тем самым парадокс будет снят! В этом случае выводы из неразрешимости проблемы останова, равно как выводы из теоремы Гёделя к такой программе будут просто неприменимы. Хотя это вовсе не доказывает алгоритмическую разрешимость проблемы останова, но устраняет разницу между компьютером и человеком, когда они поставлены в одинаковые условия.

Третий момент заключается в требовании к останову алгоритма. Конечно, требовать от алгоритмов остановки с выдачей результата вполне естественно для классических алгоритмов, однако нелепо требовать от искусственного интеллекта того, чтобы он спустя ограниченное время останавливался и выдавал какой-то конечный результат. Безостановочные алгоритмы обладают большей мощностью, чем классические алгоритмы и тоже могут быть вполне полезны. К примеру, такой «алгоритм» может выдать какой-то результат и продолжить работать. Многим ученым не нравится идея безостановочных алгоритмов, поскольку для них остается вопрос, когда считать, что ответ сформирован, поэтому свойства таких алгоритмов в математике исследованы меньше. Но для них можно ввести понятие «вычислимости в пределе»: если на каком-то шаге формируется ответ, который не меняется в процессе последующей работы безостановочной программы, то полагается, что задача решена. К сожалению, мало известен тот факт, что классическая проблема останова является разрешимой в пределе. Таким образом, безостановочность алгоритма потенциального искусственного интеллекта – это не плохое, а принципиально необходимое его свойство. Дело в том, что сложность безостановочных алгоритмов может неограниченно возрастать, в то время как алгоритмы, от которых требуется остановка за заранее определенное (в самом алгоритме или исходных данных) число шагов, действительно обладают ограниченными возможностями.

Итак, существование алгоритмически неразрешимых проблем и ограничения, накладываемые теоремой Гёделя на формальные системы, по-видимому, не являются бесспорным аргументом против возможности реализации сильного искусственного интеллекта как физической реализации некоторого алгоритмического процесса, но процесса безостановочного и открытого.
Имеются и другие «аргументы» против алгоритмизуемости мышления. К примеру, часто говорится, что результат работы алгоритма полностью и однозначно определяется начальными данными, в то время как человек обладает «свободой воли». Однако детерминированность не является ключевым свойством алгоритма. Существуют вероятностные и недетерминированные машины Тьюринга, результат работы которых неоднозначен. Однако установлено, что они не расширяют понятия алгоритма в смысле алгоритмической разрешимости задач. И хотя некий источник хаоса может быть важен для реализации мышления, идею алгоритмичности это не опровергает. Кроме того, существенной неопределенностью обладают данные, поступающие в программу из внешнего мира.
Интереснее другое: механическое применение известного алгоритма для нас не выглядит проявлением умственной деятельности. Если мы не знаем алгоритма умножения двух чисел «в столбик», то умножение каждой конкретной пары чисел для нас будет требовать интеллектуального напряжения. Но как только алгоритм известен, умножение любых двух чисел становится малоинтеллектуальной задачей. Может, мышление – это процесс построения новых алгоритмов в случаях, когда способ решения некоторой массовой проблемы еще неизвестен?
Поиск алгоритма, решающего проблему останова и ряда других проблем в общем случае невыполним. Но это не мешает исследовать алгоритмы решения этих задач при некоторых естественных ограничениях. Зачастую поиск этих ограничений и составляет основную часть решения реальной «неразрешимой» задачи. Не зря говорят, что правильная постановка задачи составляет уже половину ее решения. Хотя пока не ясно, как реализовать приближенное решение алгоритмически неразрешимых задач, по крайней мере, теорема Гёделя не накладывает ограничений на возможность этого.
@aideus
карма
63,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (167)

  • –5
    кстати, утверждение о том, то решивший проблему алгоритм останавливается, совсем неверно. Например, любой калькулятор, решив задачу, продолжает работать. Это касается как железных, так и программных калькуляторов.
    • +2
      Ну здесь получаются разные задачи, и потому все остается правильным :-)
      • 0
        Я хочу сказать, что требование «остановки приложения» по достижению ответа, мне не представляется естественным. Во времена Тьюринга, возможно, это было очевидным (зачем машине с шестерёнками крутиться, когда задача решена?), однако, опыт практической реализации вычислительных систем, говорит, что остановка машины, это скорее аварийная ситуация, чем признак решения задачи.

        Почему это важно? Потому что это формулирует очень важное условие алгоритма — «правильными» алгоритмами считаются те, которые останавливаются.

        А как насчёт алгоритма, который приходит к решению и продолжает его генерировать? Простейший пример — построение асимптотической линии. Достигли неразличимости с тому, к чему стремимся? Достигли. Останавливаться? Нет — так как линия продолжается в бесконечность. При этом практическая ценность решения вполне очевидна.
        • +9
          Мне кажется не стоит воспринимать остановку программы так буквально. Остановка программы в данном случае — момент, в который программа перестает генерировать результат.
          • +1
            Ну, в блок-схемах есть же специальные элементы — «Начало» и «Конец»
          • 0
            Тут важно — можно ли определить, что программа завершила работу (и содержимое данной ячейки ленты больше меняться не будет). Если можно — то мы не получаем увеличения вычислительной мощности. Если же требовать только чтобы каждая ячейка стабилизировалась, но не требовать вычислимости момента стабилизации — то мы получаем некоторое расширение вычислительных возможностей (вроде бы, примерно равное оракулу останова).
          • 0
            Я же специально привёл случай, когда программа «вроде бы не остановилась», но её результаты уже применимы к жизни.

            Причём, может быть так, что мы не можем рассчитать расстояние до ответа (допустим, это трудная задача). В этом случае мы уже имеем ответ неполный ответ, который постепенно уточняется. Формально, алгоритм не имеет решения, фактически — им можно пользоваться.

            Да что там изобретать. Алгоритм рассчёта ПИ в десятичной системе счисления. Формально — нерешаемая задача, алгоритм никогда не остановится.

            И кому это мешало использовать пи в рассчётах?
            • +1
              Тут немного другое. Задача, которую решает алгоритм — это не «нахождение десятичной записи числа пи», это «нахождение первых N знаков десятичной записи числа пи» (ну или нахождение N-го знака, или еще что-то аналогичное).

              Возникает вопрос о модели формализации. Калькулятор, завершив рассчет, переходит в некоторое особое состояние, легко отличимое от возникающих в ходе вычисления состояний. Если мы будем требовать такого поведения — то расширения вычислительных возможностей по сравнению с обычной МТ мы не получим.
        • +1
          Думается, Вы повторили часть статьи про «предельные» алгоритмы. Которые, кстати, легко останавливаются условием «погрешность меньше заданной величины».

          Вообще, каждый алгоритм, дополненый условием «работать не дольше», «на вход подается вывод, который уже подавался» может быть остановлен. Но, поскольку математически требуется ответ «остановится ли где-то в бесконечности, для общего случая, включая самое себя» — это неразрешимая проблема.
          • 0
            Это если мы можем рассчитать погрешность. А теперь, что делать, если рассчёт погрешности, в свою очередь, задача труднорешаемая?

            Просто мне кажется, что рассмотрение теории алгоритмов в модели «до остановки», возможно, не лучший вариант. (Как лучше — не знаю).
            • 0
              Не могли бы Вы привести пример такой задачи? Я не очень представляю, как такое может быть.
              • 0
                Ну, например, задача о вычислении числа, в двоичной записи которого стоят единицы на позициях, номера которых соответствуют останавливающимся машинам Тьюринга. Задача о вычислении этого числа с произвольной точностью алгоритмически неразрешима.
              • 0
                Предположим, у нас задача слежения: мы удерживаем фокус за двигающимся объектом. Когда алгоритм должен сказать «стоп»?
                • +1
                  Когда объект сфокусирован?
                  • 0
                    Он двигается.
                    • +1
                      Когда он находится в определенном секторе обзора, к примеру зависящего от шага сервопривода или размера пекселей фотоэлемента. Навелся на него — стоп, он выехал из сектора — перенавёлся.

                      Но если объект слежения закреплен на самой камере — происходит зацикливание как у осла с морковкой на палочке.
                  • 0
                    И вообще множество реальных алгоритмов успешно работают по принципу бесконечного цикла с выходом по внешнему условию — внешнее условие не наступило и алгоритм не останавливается.
                    • 0
                      Зачем рассматривать бесконечный цикл в качестве части алгоритма, алгоритм просто запускается в бесконечном цикле когда выполняются определенные условия, если условия не выполняются — алгоритм «спит». В примере с фокусом на объекте, вполне возможна ситуация, когда работа алгоритма не требуется, но бесконечный цикл будет работать, например, когда объект неподвижен.
                      • 0
                        Ну вот алгоритм слежения работающий по схеме бесконечного цила:
                        1. получить картинку с камеры
                        2. распознать объект и его положение на картинке
                        3. вычислить необходимый угол отклонения оси камеры от «нейтрального»
                        4. дать команду сервоприводу отклонить ось камеры на вычисленный угол
                        5. перейти к 1.

                        Работа шага 1 требуется постоянно, шага 2 если картинка изменилась (на практике — всегда: изменение освещенности, шумы и т. п.), только шаги 3 и 4 не задействуются если положение объекта не изменилось. И то шаг 4 можно пропустить при условии что камера управляется только этим объектом. То есть алгоритм должен работать постоянно если требуется отслеживать ASAP, а не периодически
                        • 0
                          Шаги 1-4 составляют алгоритм(в данном случае он никогда не пропускается), шаг 5 — бесконечный цикл, внешний по отношению к алгоритму. Проблема с бесконечным циклом в том, что он может быть один, поэтому если нужно будет выполнять несколько алгоритмов, то их нужно будет помещать последовательно внутри бесконечного цикла.
                          • 0
                            Но соглашусь с вами, что бесконечный алгоритм возможен. Более того, скорее всего, именно такой алгоритм будет реализовывать сильный ИИ. Бесконечную программу должен кто-то дописывать по мере исполнения. Более того, если рассматривать весь цикл как один шаг некоторой виртуальной машины, мы увидим линейно бесконечную программу вместо зацикленной. Причем писаться такая программа будет внешней средой.
                            В случае слежения за объектом главным «программистом» виртуальной машины будет объект, за которым она следит, т.к. именно он определяет угол поворота камеры. Если объект совершает периодическое движение так, что угол поворота камеры меняется циклически, получим цикл второго уровня. На первом уровне цикл задан жестко внутри, на втором — также жестко снаружи. Очевидно, что для сильного ИИ потребуется нечто среднее, т.е. среда должна иметь возможность влиять на первый уровень, а программа — на второй. Что-то не могу придумать третьего уровня, но вероятно, более сложные системы будут многоуровневыми в этом плане.
                            • 0
                              Третий уровень — человек, который заставил объект двигаться периодически. А над ним — человек, который дал ему приказ обеспечить циклическое действие, а над ним… А вообще может быть не человек, а другой ИИ.
                              • 0
                                Этот вариант третьего уровня не совсем подходит. Во-первых, человека в систему лучше не включать(предпочту не объяснять, но можно придумать множество причин). Во-вторых, человек только заставил двигаться периодически, т.е. программа уже первого человека состоит из однократной команды, т.е. его виртуальная машина вырожденная. В-третьих, тут плохо просматривается связь: что программа на более высоком уровне является данными на более низком. Программа высокого уровня пишется в данных низкого. Иначе «виртуализация» получится неполной, т.е. начнет превращаться в обычную иерархию.
                              • 0
                                Решил продолжить ваши рассуждения: «а над ним…» идея(по Гегелю).
                  • 0
                    … то следует перерассчёт снова и снова.

                    Хотите ещё менее конечную задачу — корректировка курса ракеты в режиме погони. Ну там, правда, есть останов, который уж всем остановам останов, если догнали.
  • 0
    Я бы сказал, что и человеческая «свободная воля» детерминирована в окружающем конкретную личность пространстве-времени. Просто факторов очень много, которые не могуи быть проигнорированы в силу «эффекта бабочки».
    Более того, число факторов возрастает в связи с тем, что еще не ясно, является ли Вселенная замкнутой, а потому «изолированной системой»

    Касаемо ограниченности, согласен — ни алгоритм, ни компьютер, ни Тьюринг-автомат, ни человек — не может «познать» себя.

    И да, касательно аксиом. Они также прочно формируют базис теории, как и легко могут быть заменены другим базисом, и в этом случае получаем другую теорию.
  • 0
    Насчёт необходимости ИИ взаимодействовать с окружающей средой (получать информацию, ставить эксперименты) я сам додумался, вот до безостановочных алгоритмов как-то нет. Надо будет подумать над ними.
  • +4
    Поставил задачу дочитать до конца. Неразрешимо…
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Вероятностные алгоритмы не расширяют вычислительных возможностей, т.к. можно просто перебрать результаты выпадения монетки.
    • +1
      Про вероятностные в статье упоминается.
      Насчет аксиоматики. Алгоритмически неразрешимые задачи разрешимы с помощью сверхтьюринговых вычислений. Но для таких «вычислений» будут свои неразрешимые задачи. Об этом тоже упоминается.
      Но дело даже не в этом. Самое главное то, что алгоритмы описывают операции над конструктивными объектами. Это можно четко понять по статьям Колмогорова. Колмогоров пытался дать (и дал) наиболее общее понятие конструктивного объекта и для таких объектов предложил свою формализацию понятия алгоритма, после чего со своим учеником доказал, что эта формализация эквивалентна другим существующим формализациям. То есть алгоритмы — это максимум, что можно сделать конструктивного. Сверхтьюринговые системы гипотетически возможны, но они неконструктивны (нефинитны), то есть абсолютно неясно, как и можно реализовать. Если будут открыты физические системы, реализующие инфинитные процесс, и человек научится этими процессами управлять, тогда будет иметь смысл говорить о конструктивных неалгоритмических системах. Пока же максимальное конструктивное расширение понятия алгоритма — это его расширение на открытые алгоритмические процессы.
      • НЛО прилетело и опубликовало эту надпись здесь
        • +1
          А.Н. Колмогоров. Избранные труды, том 3: Теория информации и теория алгоритмов
          Вроде, в Интернете можно найти для скачивания. Про теорию алгоритмов там ближе к концу (хотя стоит сразу предупредить, что книга сугубо математическая).
  • +1
    А можно сжать суть статьи до двух предложений? Потому что на данный момент она мне кажется довольно странной, может, я чего недопонимаю.

    Вы ссылаетесь на каких-то неназванных мыслителей, которые «делают вывод о невозможности формализации мышления», а потом доказываете им (!), что их позиция слаба.

    В то же время можно сослаться на кучу других мыслителей (начиная с того же Тьюринга и кончая, например, Хофштадтером), которые не видят никаких противоречий между существованием неразрешимых задач и теоретической возможностью создания «сильного ИИ».
  • –1
    Но какую бы мы формальную систему ни взяли, всегда найдутся утверждения об объектах системы, истинность которых не может быть установлена в рамках самой системы. Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат

    Круто. Скажите, пожалуйста, истинны или ложны в ZF гипотеза континуума и аксиома выбора?
    • +2
      Э… Если не изменяет память, считается, что континуум-гипотеза и аксиома выбора не противоречат аксиоматике ZF. Если их принять за истинные, получается аксиоматика ZFC. Но неконструктивные объекты нас меньше интересуют, поэтому можем ошибаться…
      Если же ставить вопрос, является ли эта гипотеза в принципе истинной, то вопрос будет бессмысленным. Уменьшение числа аксиом позволяет рассматривать более общий класс моделей, увеличение — позволяет обогащать выводимые свойства для более узкого класса. В каких-то случаях удобнее евклидова геометрия, а каких-то — неевклидова. Кому-то нравится закон исключенного третьего, а кто-то предпочитает интенсиональные логики. Можно, конечно, думать, что в мире идей есть какое-то истинное понятие континуума. Но на наш взгляд, те аксиоматические системы, которые производят впечатление такой абсолютной истины, являются все же просто очень эффективным индуктивным обобщением свойств реальности.
      • 0
        Стоп. Вы утверждаете, что человек может мистическим образом определить, должны ли эти утверждения быть истинными или ложными. Определитесь, пожалуйста:)

        считается

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

        Кстати, в каком смысле ZF неконструктивна? Вы можете доказать, что у нее нету счетной разрешимой модели? (может быть это и правда, я не знаю; но это вроде бы неочевидно)
        • 0
          Про ZF это и имелось в виду, просто на память не было уверенности в том, что это строго доказано, а проверять было лень; отсюда и взялось «считается».
          А откуда следует, что «человек может мистическим образом определить, должны ли эти утверждения быть истинными или ложными»? Вовсе не мистическим, а индуктивно.
          Насчет неконструктивности, опять же, это смутные воспоминания, подкрепленные интуицией о том, что аксиома выбора для континуумов не имеет алгоритмического воплощения. Если это вдруг не доказано, то, вероятно, это не так сложно сделать исходя из понятия алгоритмической сложности.
          • 0
            А откуда следует, что «человек может мистическим образом определить, должны ли эти утверждения быть истинными или ложными»?

            Вопрос к Вам — Вы же это написали.

            А " алгоритмическое вополщение аксиомы выбора для континуальных множеств" осложняется тем, что не очень понятно, что такое континуальное множество в контексте алгоритмов. Причем тут алгоритмическая сложность — не понимаю.
            • 0
              Тогда ответ на вопрос был дан: нет, человек определяет это вовсе не мистическим образом.
              Насчет осложнения — именно; поэтому континуальные множества и не являются конструктивными объектами.
              • 0
                Слово «мистическим» употребили Вы…
                Хорошо, определите мне хоть индуктивным. хоть каким образом истинность аксиомы выбора в ZF.

                Ну да, только зачем рассматривать континуальные множества? Если ZF непротиворечива, то у нее есть модель; можно доказать, что всякая модель ZF бесконечна; тогда по теореме о понижении мощности у нее есть счетная модель.
                • 0
                  Так ведь не является аксиома выбора в ZF ни истинной, ни ложной. Добавлять ли ее или нет — вопрос полезности. Аксиоматика ZFC успешно применяется. Есть ли попытки рассмотреть, что получится в аксиоматике ZF!C? Может, там будет что-то интересное, как в неевклидовой геометрии или в интенсиональных логиках; а, может, ее следствия пока особо никуда не применимы?..
                  • 0
                    Безусловно, не является.
                    Но какую бы мы формальную систему ни взяли, всегда найдутся утверждения об объектах системы, истинность которых не может быть установлена в рамках самой системы.

                    Но раз Вы — человек, а не машина, то сделайте то, на что, согласно Вашему следующему утверждению способен человек:)
                    Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат.


                    Насчет аксиомы выбора — не знаю. Но в функане в последнее время модно неявно использовать как гипотезу континуума, так и ее отрицание.
                    • 0
                      Вот видите, специалисты по функану в каждом конкретном случае для себя этот выбор делают. Этот выбор определяется контекстом применения соответствующей аксиоматики. Что Вам еще нужно?
                      • 0
                        Мне нужно мистическим образом определить, должны лы быть эти утверждения истинными или ложными:)
                        • 0
                          Можно только посочувствовать ))
                          Это серьезная проблема выбора, для выполнения которого нужно учесть весь контекст решаемой вами задачи.
                        • 0
                          Мистическим образом вы можете для себя решить считать их истинными или ложными.

                          Существование абсолютной, объективной истины не доказано :) Человек же оперирует истинностью относительной. Какие-то утверждения, как правило не противоречащие субъективной картине мира данной в ощущениях, принимаются за истину. Мистически. Остальные утверждения проверяются на соответствие им, не соответствие или ортогональность. Более того, на практике часто применяются в качестве истинных утверждения заведомо ложные, лишь бы они приводили к практически приемлемому, пускай и не точному результату. Скажем, кратчайшим расстоянием между двумя точками на поверхности Земли зачастую считают длину кратчайшей линии на (апроксимации) этой поверхности, а не отрезок прямой, соединяющий эти точки в пространстве — рыть математически (по Евклиду) кратчайший тоннель из Нью-Йорка в Москву не практично.
                          • 0
                            Вы вообще с чем спорите? Вы, вроде, говорите практически то же самое, что и мы. Или это у Вас такой способ соглашаться?
                            • 0
                              Я поясняю mihaild, что нельзя определить истинно какое-то утверждение или ложно. Ни мистически нельзя, ни логически. Можно только решить считать истинно оно или нет. (В случае логического вывода — истинны ли изначальные посылки и сами правила логики).
                              • 0
                                Да я в курсе, что нельзя, это в тексте статьи утверждается, что можно:)
                          • 0
                            Просто автор указывал превосходство человека перед формальными системами — он способен определить, должно ли независимое от формальной системы утверждение быть истинным или ложным.
                            Исходя из этого и последующей дискуссиии, автора следует счесть формальной системой, а не человеком:)

                            Что же касается тоннелей — в этом случае мы просто работаем в другой многообразии — не трехмерное евклидово пространство, а поверхность Земли. На которой есть своя метрика, отличная от метрики объемлющего пространства (хотя и индуцированная ей).
                            • 0
                              Автор ошибается, человек может решить считать утверждение истинным и свои дальнейшие рассуждения и/или действия строить от этого «факта». А потом передумать и считать его ложным. Или считать истинным только в каких-то частных случаях.
                              • 0
                                Так об этом и речь. В чем ошибка-то?
                                • 0
                                  Может просто фразу «Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными» неудачно сформулировали?
                                  • 0
                                    Ну, если читать только первый абзац статьи и выдирать фразу из контекста, то, конечно, найдется с чем спорить. Эта-то фраза в статье как раз и опровергается. Она здесь дается с ироническим оттенком и используется как антитезис.
        • 0
          >В математике не принято «считать», в математике принято доказывать.

          Вообще в математике «считается» довольно распространенное явление: «Аксиома — утверждение, не требующее доказательств.»
          • 0
            Аксиома — просто замкнутая формула. Теория — множество аксиом.
            И все выводы происходят в той или иной теории.
            Никаких «требует доказательств», «не требует доказательств» нету. Есть «выводится из аксиом», «отрицание выводится из аксиом», «не зависит от аксиом».
      • 0
        >> Но на наш взгляд, те аксиоматические системы, которые производят впечатление такой абсолютной истины, являются все же просто очень эффективным индуктивным обобщением свойств реальности.

        Вы как-то пишите, что пытаетесь ввести в заблуждение себя или других (не совсем понятно). Формальная математика не работает с реальным миром!!! Это вопрос философии насколько она применима и вопрос физиков насколько математическая модель подходит к наблюдаемым эффектам, ни больше.

        >> Человек же каким-то «мистическим» образом определяет, должны ли эти утверждения быть истинными или ложными, и может расширить формальную систему так, чтобы получить желаемый результат.
        Опять же что такое желаемый результат!? Я не знаю верна ли теорема Эйлера или нет, так что мне ее добавлять в аксиомы? (Хотя с гипотезой Римана так и пытаются делать, но это неправильно).

        То что вы пишите, что кто-то использует меньший набор аксиом, а кто-то больший — сильно зависит от среды. Например функциональном анализе по сути дела все равно, на сколько верна аксиома выбора, потому что она дает мощный и хороший апарат для использования в теории вероятностей. Даже если окажется, что она не верна, большинство результатов останутся, потому что они проверены в реальных моделях, соответственно найдется некоторое верное сужение аксиомы выбора. А сужают те люди, которые хотят найти и показать минимальный набор аксиом, который бы удовлетворял некоторой модели. Чем-то напоминает программирование, чем более абстрактный фреймворк напишешь, тем в больших местах он пригодится, но если совсем абстрактный вообще нигде толком пользы и не принесет.

        Вы не заметили, что Эйлер не пользовался формальными доказательствами, но не сделал никакой ошибки. Он даже умудрялся сумировать расходящиеся ряды без формальных определений например
        1 — 1 + 1 — 1 + 1 — 1… = 1/2
        :)

        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            В свое время преподаватель математики жаловался, что физики берут их формализмы и оперируют ими, никак не доказывая, что это допустимо. Это возможно только в силу гиперуниверсальности и интуитивной ясности математических абстракций, но логически неверно. Как и на выбор фреймворка, на выбор математического аппарата теории могут оказывать влияние личные предпочтения, хотя и в значительно меньшей степени. Аксиом в природе не существует, аксиомы формализуют точку зрения, а не реальность(в широком смысле).
            • НЛО прилетело и опубликовало эту надпись здесь
              • +3
                На эту тему Вигнер когда-то прочитал лекцию «Непостижимая эффективность математики в естественных науках» (текст легко можно найти).
                Нобелевский лауреат, автор теории слабого взаимодействия, рассказывал, что на момент формулировки теории у них было восемь экспериментов, ей противоречащих. Но математический аппарат теории был столь красив, что она просто не могла оказаться неверной — и впоследствии нашлись ошибки во всех восьми результатах.
                И так далее.
              • 0
                Абстракция. Счет необходим человеку, который применяет его к реальному(в широком смысле) миру. Следовательно, счет связан с реальным миром, правда связь односторонняя.
                То, что в природе нет слов можно принять в качестве аксиомы.
                Если в природе нет слов, то нет и чисел, значит в природе нет счета.
                Никакого совпадения тут нет: в природе счета нет, а у человека он есть.
                • 0
                  Тем не менее, многие физические величины ведут себя как вещественные и комплексные числа, вектора, тензоры, операторы и т.д.
                  • 0
                    Это скорее человек нашёл удобный способ описания физических состояний и процессов.
                    • 0
                      Тем не менее нередко появление математического аппарата предшествовало нахождению физического смысла. И, если математика для описания того или иного явления — просто изобретение человека — то не очень понятно, почему один и тот же аппарат прекрасно применим к очень разным на первый взгляд явлениям.
                      • 0
                        потому что его создавали гениальные люди, опережающие свое время.
                        • 0
                          Вот лекция, о которой я писал чуть выше: www.youtube.com/watch?v=UuRxRGR3VpM
                          «Красота — очень удачный критерий для выбора правильной теории»
                          «Теория является красивой, если она может быть кратко изложена в терминах уже существующей математики»
                          Если предположить, что математика — не абсолют, а творение человека, то совершенно непонятно, почему она так тесно связана с законами природы.
                          • +1
                            Математика создавалась, чтобы описывать законы природу и она хорошо справляется со своей задачей. Также как алфавит создавался, чтобы записывать слова. Также можно удивляться и красоте букв. Буквы можно применять в самых разных словах. И конечно, новые слова должны быть записываемыми с помощью уже существующего алфавита. Но не из чего не следует, что никогда не понадобится новая буква или какая то буква станет ненужной, просто уже существующий алфавит прошел долгий отбор и вероятность изменения стремится к нулю.
                            Если кто не понял буквы — это разделы математики, слова — теории, описывающие природу.
                            • 0
                              Во-первых, слова искусственны, и крайне маловероятно, что человек, не знающий слова для описания данного явления придумает именно то слово, которое придумали до него. В то время как многие понятия в математике нередко возникали в самых разных областях а потом кто-то замечал, что это одно и то же.
                              Во-вторых, было бы довольно странным, если бы для описания чего-то, о чем раньше никто не задумывался, подходило существующее слово.
                              • 0
                                «Во-вторых, было бы довольно странным, если бы для описания чего-то, о чем раньше никто не задумывался, подходило существующее слово.»
                                У меня выше со словами ассоциируются теории(возможны вы имели ввиду буквы?). В этом контексте вы утверждаете примерно следующее: было бы странно, если бы для описания чего-то нового подходила существующая теория. Ничего странного ни в том, ни другом случае нет. Если найдут новый вид животного, то к нему вполне будет подходить слово «животное». Если обнаружат белые дыры, то существующая теория гравитации для них вполне подходит.

                                «Во-первых, слова искусственны, и крайне маловероятно, что человек, не знающий слова для описания данного явления придумает именно то слово, которое придумали до него.» Да слова искусственны, но теории тоже. Все зависит от контекста, в рамках бытового сленга вполне возможно, что, например, новое устройство для сушки чего-либо назовут сушилка независимо друг от друга множество, если не все, кто им начнет пользоваться. В тоже время, в неопределенных случаях для описания одного и того же явления разные исследователи выдвинут разные теории и будут при этом опираться на различные(или даже одинаковые) разделы математики.

                                «В то время как многие понятия в математике нередко возникали в самых разных областях а потом кто-то замечал, что это одно и то же.» — Многие буквы возникали в самых разных словах, а потом кто-то видел, что это одинаковые буквы(и начинал их записывать одинаково, так мы и пришли к единообразному алфавиту).
                                • 0
                                  «чего-то, о чем раньше никто не задумывался» — привести подходящий пример несколько затруднительно
                                • 0
                                  P.S. Я не зря привел пример с алфавитом, так как человечеству известно несколько алфавитов, но одна математика.
                                • 0
                                  «Если найдут новый вид животного, то к нему вполне будет подходить слово «животное»»
                                  Но если обнаружат некую непонятную хрень то очень вряд ли найдется существующее слово, ее обозначающее.
                                  Слова всегда возникали после возникновения (быть может, умозрительного) обозначаемого ими предмета. Математический аппарат же иногда опережал открытие соответствующих явлений в природе.

                                  «новое устройство для сушки чего-либо назовут сушилка независимо друг от друга множество, если не все, кто им начнет пользоваться»
                                  Потому что это достаточно близко к уже существующему. И то — это описание будет неточным. А математика дает точные описания природных явлений.

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

                                  «Многие буквы возникали в самых разных словах, а потом кто-то видел, что это одинаковые буквы»
                                  У букв нет самостоятельного смысла, в отличии от разделов математики.
                                  • 0
                                    «У букв нет самостоятельного смысла, в отличии от разделов математики.»
                                    У них есть смысл — только из них можно составлять слова. Никакой другой смысл не имеет значения для данной аналогии.
                                    «Слова всегда возникали после возникновения (быть может, умозрительного) обозначаемого ими предмета. Математический аппарат же иногда опережал открытие соответствующих явлений в природе.» Еще раз математический аппарат — множество разделов математики у меня в тексте ассоциируется с алфавитом. Конечно же, алфавит опережает многие слова из него составленные.
                                    З.Ы. Ничего внутри вселенной, кроме эго не имеет самостоятельного смысла. Это точка смысловой сингулярности.:)
                                    • 0
                                      вы же удивляетесь, что слова произносятся так, как будто они состоят из букв
                                      • 0
                                        Представьте, что Вы придумали буквы. А потом обнаружился язык, о котором Вы и не слышали, придумывая буквы, слова в котором составляются именно из этих букв.
                                        Слова суть изобретение человека, буквы — тоже.
                                        Законы природы — не изобретение человека. Гравитационные линзы существуют объективно, а не потому, что их придумал Эйнштейн.

                                        «только из них можно составлять слова»
                                        Буквы, которые не используются при составлении слов — бессмысленны. Разделы математики, не использующиеся на текущий момент в физике — не бессмысленны.
                                        • 0
                                          Законы природы — не изобретение человека. Конечно, но описания этих законов — изобретение, и средство описания — изобретение.

                                          «Разделы математики, не использующиеся на текущий момент в физике — не бессмысленны.» Для физики — бессмысленны.
                      • 0
                        Потому что они очень разные только на первый взгляд? Казалось бы что общего между морской волной, светом и звуком… Кстати, лично я считаю, что схожесть математических описаний разных процессов говорит о возможности создания «единой теории поля (всего)» и подозреваю, что когда (если) она будет создана, то будет довольно компактной и красивой.
                        • +1
                          Я подозреваю, что эта теория будет выглядеть как одно уравнение из трех символов и десяти томов, объясняющих, что значат эти символы.
                        • 0
                          Точнее даже как-то так
                      • 0
                        Уходите в метафизику, друг мой ) Это старая дилемма — что является первоначалом, математика или физика. Наша наука построена таким образом, что мы вкладываем в природу математический смысл, описываем ее на языке уравнений. Но и напротив, не реже приписываем природе свойства наших уравнений, трактуя наблюдения так, как это удобно нам. Здесь, по моему мнению, следует рассмотреть вопрос истории математики начиная с самых начал. Определенные попытки такого анализа были у Лебега, хотя даже он не смог удержаться от доли метафизичности.
                        • 0
                          На эту тему есть замечательная книжка Клайна «Математика. Утрата определенности», где в том числе рассматривается история развития.
                          Оба варианта были довольно часто — иногда сначала обнаруживали явления, а потом создавали мат. аппарат для их описания, иногда — наоборот. Вопрос о том, абсолютна ли на самом деле математика остается открытым и вряд ли мы в данной дискуссии его решим.
                          Чудесная
                          загадка соответствия математического языка законам физики является
                          удивительным даром, который мы не в состоянии понять и которого мы,
                          возможно, недостойны. Мы должны испытывать чувство благодарности
                          за этот дар. Следует надеяться, что он не покинет нас и в будущих иссле-
                          дованиях и что он будет — хорошо это или плохо — развиваться к наше-
                          му большому удовлетворению, а быть может, и к нарастающему беспокой-
                          ству, расширяя область познания окружающего нас мира.

                          Вигнер
                  • НЛО прилетело и опубликовало эту надпись здесь
                • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          >> Формальная математика не работает с реальным миром!!!

          Мышлению просто не от чего отталкиваться, кроме как от реального мира. Даже если строится «экзотическая» система аксиом, она строится «в противовес» естественным свойствам.
          • 0
            Я не говорю, что аксиомы или теоремы берутся не из реального мира, как раз наоборот :) Только из необходимостей реального мира, но момент когда они переносятся в формальную математику они теряют эту связь. Связь остается только на уровне аксиом и каждый, кто применяет математическую модель по-хорошему должен фальсифицировать верность аксиом на некоторой реальной или опять же абстрактной моделе.
          • 0
            Аксиома о существовании бога(ов) ортогональна реальному миру.
        • 0
          Ну да, но Эйлеру везло. Формализм же позволяет, не будучи гением, строить правильные выводы (или хотя бы проверять чужие выводы на правильность).
  • –12
    Хунта. Прочитал как ХУNТА.
  • +2
    Вспомним Тьюринговскую трясину. В примере один простой алгоритм применяется для решения всех однотипных задач, и мы убеждаемся в заведомой невозможности правильного ответа. Создав же отдельные алгоритмы для частных случаев мы находим выход из положения.
    • 0
      Ну да, даже знаменитая Великая Теорема Ферма была доказана сначала для случаев 3,4, затем с помощью ЭВМ проверена до 100, и только в 95ом году была доказана для общего случая.

      В случае же человеческого мышления, с ошибками — я полагаю, используется интер -и экстраполяция, т.е. человек склонен наблюдать частный случай и делать вывод из частного в общее. Неудивительно, что ошибок оказывается намного больше ожидаемого…
  • –1
    Алгоритм нахождения алгоритма?
    • 0
      Алгоритм классификации алгоритма, с паразитным влиянием на объект классификации.
  • 0
    Проблема тьюринговых машин заключается не в алгоритмической неразрешимости. Это как вобщем-то правильно подмечено в статье обходится предоставлением алгоритму возможности наблюдать за миром, и введением нескольких параллельных процессов.

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

    И именно этого и не хватает для решения AI-полных задач.
    • 0
      >… а это означает, что мы не можем её решение получить быстрее…
      Т.е. исходя из этого, можно предположить, что алгоритм таки решает задачу, но за бесконечное время?
      Тогда да, можно решить любую задачу брутфорсом: пробовать все варианты из некоторого счетного множества…
      • –1
        Чтобы убрать не нужную терминологию, поясню, чтобы все поняли :)

        Примером задачи класса P является к примеру сложение 10 чисел. Это можно сделать не быстрее, чем за 10 тактов. Делай ты это последовательно или параллельно.

        Человек же это может сделать быстрее — если ему говорят сложи 1+1+1+1 — он за один такт скажет =4. А компьютер будет все время складывать 1+1+1+1
        • 0
          Пример все же не очень удачный. Человек это не делает «за один такт». Ему все равно нужно посчитать сначала число единиц. Кроме того, сложить N чисел на параллельной машине можно за logN тактов.
          • –1
            Ну, я не согласен. Возьмем к примеру сложение чисел до 10. Скажем 2+2, 3+4 — вы ответ даете сразу? У меня дочка учится в школе, т.к. у них как раз требование — отвечать не считая! Не это ли требование одного такта?

            А теперь перейдем к схемотехнике, сколько единичных тактов потребуется сумматору, чтобы осуществить такое сложение?

            Далее давайте возьмем т.н. задачу (предикат) четность. Имеем скажем шахматную доску — как долго вы будете думать клеточек на доске четное число или нет? А есть ли у компьютера способ не считать клеточки?

            сложить N чисел на параллельной машине можно за logN тактов — расскажите конкретный алгоритм который это сделает? Сомнительно для практики.

            • 0
              Впрочем, нашел, видимо имеется введу алгоритмы каскадного суммирования
              • 0
                да
            • 0
              То, что ответ дается без счета, не значит, что он дается «за один такт». Память — это очень сложная система «кэширования», и поиск в памяти на подсознательном уровне требует большого числа операций.
              (Но опять же про память — отдельный большой разговор)
              • 0
                > поиск в памяти на подсознательном уровне требует большого числа операций

                большого, но меньшего !, но хорошо, давайте вернем к этому, когда будем говорить о памяти
            • 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+1.

          Кроме того, согласен, бывают задачи, решение которых нельзя получить быстрее, чем за полиномиальное время. С учетом того, что f(x) = 0 — вполне себе полином, то это утверждение следует из того, что существуют задачи, которые нельзя решить за отрицательное время.
          • –2
            Знаете как это делается? считаете 10 единиц, а дальше выравниваете по длине — получаете все меньше, чем полиномиальное время.
            • 0
              Для справки: ru.wikipedia.org/wiki/Многочлен
              0 и 1 — это вырожденные полиномы.

              Полиномиальное время — время f(x) — где f — некоторый полином.
              • 0
                и?
                • 0
                  Реквестирую решение какой-нибудь задачи за время быстрее полинома P(x) = 0.
                  • 0
                    ну скорее всего он имел в виду «меньше, чем за O(N)» операций, где N — число единичек
                    • 0
                      И не O, а Ω, ибо 0 \in O(N).
                      Но тут возникает вопрос — как считать время? Во всех классических моделях нам понадобится линейное время уже на то, чтобы прочитать вход.
                    • 0
                      Уже ближе.

                      Если для функции f существует машина Тьюринга M такая, что Cm(n) < n^c для некоторого числа c и достаточно больших n, то говорят, что она принадлежит классу P, или полиномиальна по времени. Cm(n) — сложность функции, зависящая от длины входного слова.
          • +4
            Очень метко замечено что такое «один такт» у человека )). Вообще рассуждать о процессах мышления часто начинают мыслить компьютероморфно. Что вряд ли правильно. Но tac правильно подметил — просто дело в том, что разум не решает задачи на которые он знает (помнит) ответ (если только разум не задался целью решить эту задачу еще раз). Дваждыдвачетыре для нас это не математическая задача с решением. Математической эта задача была наверное пару раз, когда родители нас учили складывать. Потом мы поимели некую связь нейронов, по которой постоянно бегает возбуждение и которая тут же отзывается на любые Дваждыдва, будь то увиденные или услышанные и мы думаем Четыре. И таких дваждыдва очень много и не только в математике. 254778+35678 это не сработает, для решения нужен будет алгоритм.
            С другой стороны, заставь человека складывать эти два числа изо дня в день и он перестанет решать эту задачу математически
            • 0
              Об этом и речь.
              • +1
                Да, дальше надо говорить о памяти. Подождем подходящий пост )
                • +1
                  Чтобы говорить о памяти, нужно обсудить проблему универсального индуктивного вывода (и общее теоретическое решение проблемы машинного обучения). Тогда разговор о памяти будет гораздо более содержательным.
                  Мы планируем написать статьи на эти темы.
                  • 0
                    Было бы очень интересно прочитать
                    • 0
                      Кое-что есть в книгах на нашем сайте ( aideus.ru/research/publications.html ), но там «много букв», и нет материала непосредственно в том виде, в котором есть желание об этом написать.
            • +1
              Да пожалуйста, вот Вам аналог такого подхода в виде программы:)
              def sum(a, b):
                if a == 2 and b == 2:
                  return 4
                return a+b
              


              Все эти хитрости с памятью и т.д. работают только для задач небольшого (ограниченного некоторой константой) размера. Так что выигрыш получается максимум константым (может быть, константа мультипликативная, неважно).
              • 0
                Скорее как-то так:
                def sum(a, b, cache=dict()):
                  key = "{}+{}".format(a, b)
                  if key not in cache:
                    cache[key] = a + b
                  return cache[key]
                


                TTL лень было расписывать :)
                • 0
                  Хотя по хорошему не a+b должно быть, а два цикла (по a и b) с инкрментирующимся аккумулятором.
                  • 0
                    Ну человек всё же складывает в столбик, а не по единичкам. И, насколько я знаю, схемы складывают примерно так же.
                    • 0
                      Не видели как дети складывают 3 и 4? Загибают последовательно три пальца, потом ещё четыре, а потом считают сколько получилось всего. Когда они начинают складывать в столбик, то сложение однозначных чисел должно быть уже у них «закэшеровано», иначе придётся складывая многозначные числа в столбик «на бумажке», цифры всё равно складывать «на пальцах».

                      Это не говоря о том, что сложение в столбик возможно только в позиционных системах счисления, а, например, европейская цивилизация до неё не додумалась, заимствовала у азиатов в Средние века, до этого пользовались неудобными греческой и римской.
                      • 0
                        Суммы однозначных — да, должны быть «закешированы».

                        Вспомнился рассказ Азимова: lib.ru/FOUNDATION/feelpowr.txt
                        • 0
                          :) Не попадался как-то раньше, спасибо за наводку.
                  • 0
                    какой алгоритм будет использован тут для прочтения? где проще ошибку заметить?
                    берем достотачно простое слово с ошибкой, ведь ее не заметно?
                    lets take pretty simple word with an error, noticaeble?
                    • 0
                      Вообще не понял о чём вы.
                • 0
                  #!/usr/bin/python3
                  from functools import lru_cache
                  <hh user=lru_cache>
                  def sum(a, b):
                    return a+b
                  
                  • НЛО прилетело и опубликовало эту надпись здесь
        • +6
          Человек, скажу по секрету, за много-много тактов проделывает нетривиальные вещи, как-то:
          — прочитать (распознать буквы) формулировку задачи
          — осознать ее
          — решить, стоит ли это делать вообще
          — выбрать алгоритм алгоритма
          — подумать «что за фигня»
          — сбиться со счету
          — пересчитать
          — позлиться, что задача для детей 1-ого класса
          — посчитать
          — подумать, писать ли ответ, или это унижает
          — написать комментарий
          — пойти выпить чаю.
    • +1
      Проблема все-же в NP-полных задачах. Задачи класса P как раз считаются «легкими». Но это отдельный длинный разговор.
      • +1
        Нет, проблема именно в задачах P. Почему-то все зациклились на задачах NP. Но никто почему то не ставит задачи БЫСТРЕЕ решать задачи P (вплоть до мгновенного ответа)… и в этой связи мне понравилось ваше вступление «Бессмыслица – искать решение, если оно и так есть.»
        • 0
          Спасибо. Интересное замечание, весьма подходит к разрабатываемой сейчас нами теории самооптимизирующегося универсального алгоритмического интеллекта.
          Но все же если методично идти от рассмотрения алгоритмически неразрешимых задач (как их превращать в задачи NP), то потом нужно рассмотреть NP-полные задачи (как их превращать в задачи P), а только потом рассмотреть задачи класса P (как их решать максимально быстро).
          • 0
            Методически у вас получается вначале решить что-то более сложное вначале? Или используя найденное решение применить его для более сложной задачи?
            • 0
              Имелось в виду, что данная статья про алгоритмически неразрешимые задачи, поэтому сразу перескакивать на класс P немного непоследовательно.
  • 0
    Как-то у вас смешаны понятия алгоритма и работающей программы (системы). Алгоритм — это последовательность действий, служащая для преобразования входных данных в выходные, и когда данные преобразованы, алгоритм заканчивает свою работу. С другой стороны, программа — это работающая система, которая может реагировать на «внешние раздражители», обрабатывать полученную информацию с помощью алгоритмов и продолжать работать. Вы же не назовёте веб-сервер алгоритмом, веб-сервер — это система, взаимодействующая с пользователями через сеть (хотя обработчик запроса — это уже алгоритм). И тут уже можно провести чёткую аналогию с человеком: человек — это тоже система, которая может реагировать на внешние раздражители и применять алгоритмы для решения конкретных задач (умножение чисел в столбик), но это никак не сам алгоритм, предназначенный для решения конкретной задачи (цели жизни). Я не имею ничего против рассуждений о программах, работающих без остановки, но теория алгоритмов уже довольно хорошо проработана, и расширение её ключевого понятия требует переосмысления всей теории, а кому оно надо.

    А в целом за статью спасибо, приятно было вспомнить такие фундаментальные вопросы как неполнота формальных систем :)
    • 0
      Пожалуйста и тоже спасибо.
      Под программой в статье в основном понимается программа для машины Тьюринга, то есть тоже алгоритм.
      Действительно, реальная работающая программа несводима к своей модели — алгоритму. В статье на это лишь намекается, но, возможно, следовало бы этот аспект обсудить в явном виде.
      Что касается «хорошо проработанной теории алгоритмов», в действительности, это не совсем так (а, может, и далеко не так). Хорошо проработаны далеко не все ее аспекты. Кому надо переосмыслять эту теорию? Разработчикам моделей универсального ИИ. И некоторыми из них это, собственно, и делается. Особенно интересна связь теории алгоритмов и теории информации. Хотя алгоритмическая теория информации была развита Колмогоровым и Соломоновым достаточно давно, сейчас становится понятной необходимость обобщения алгоритмической сложности по Колмогорову с учетом вычислительной сложности (получается т.н. сложность по Левину)… В общем, тут масса всего интересного и еще непроработанного.
  • 0
    Я имею ввиду, что есть ряд техник, практик и теорий, опирающиеся на «классические» определения алгоритма (например то, которое приводит Кнут). Возьмём тот же вопрос об окончании работы алогиртма и простой пример — рекурсивную функцию факториала. Классическая теория алгоритмов чётко говорит: алгоритм всегда должен иметь окончание, а во время выполнения должен сохранять некоторые инварианты. Если человек, проектирующий алгоритм рекурсивного вычисления факториала, знаком с этой теорией, для него структура функции будет очевидна — сначала проверить на условие окончания, потом вызвать функцию рекурсивно, при этом проверив, что инварианты при рекурсивном вызове сохранены. Если отменить условие конечности алгоритма. теоретическая база проверки корректности просто развалится. Придётся придумать какие-то новые условия, сохраняющиеся как для конечных, так и для бесконечных алгоритмов. А представьте какой это вызовет разброс в литературе, где половина книг будет использовать одно определение термина, другая половина — другое определение. Поэтому на мой взгляд гораздо проще и правельней будет просто ввести новое понятие (будь то «работающая система», «неконечные алгоритмы», «надалгоритмы» или что угодно),
    • 0
      Да, это безусловно. Никто не предлагает переделывать классическую теорию алгоритмов.
  • 0
    Непонятно, зачем сначала составлять алгоритм, а только потом проверять, остановится он или нет, когда можно сразу составлять алгоритм так, чтоб он останавливался.
    Время выполнения алгоритма не менее важно, чем его программа. Возможно следует рассматривать подмножество алгоритмов, время выполнения(максимальное, минимальное) которых можно легко(за малое почти постоянное время) вычислить или оценить не выполняя самого алгоритма t_алгоритма=алгоритм_расчета_времени(входные_данные).
    Для этого достаточно дополнить каждый алгоритм временем его выполнения и использовать правила составления алгоритмов, сохраняющие легкость алгоритма_расчета_времени.
    Очевидно, что любой алгоритм подмножества остановится, если алгоритм_расчета_времени выдает значение меньшее бесконечности. Это похоже на синтезируемое в кремний подмножество программ, только для времени, а не пространства.
    Да это подмножество всегда можно расширить, изменив правила комбинации алгоритмов или добавив новую пару (t_алгоритма, программа_алгоритма), но такое ограничение как минимум позволяет осуществлять эффективное распараллеливание и прозрачное многоуровневое планирование собственной деятельности. К тому же, раз это подмножество всегда можно расширить, то его ограниченность не столь существенна. Алгоритм составления алгоритма решения какой-либо задачи все еще может не остановится, а полученный алгоритм быть неоптимальным. Зато можно быть уверенным, что он решает задачу за определенное время.
    P.S. Все вышесказанное имеет очень отдаленную связь с сильным ИИ, сознание можно рассматривать как странный аттрактор, отсюда сложности его алгоритмизируемости.
  • 0
    Вовсе нет! Это как раз имеет прямую связь с сильным ИИ. Как раз простейшие расширения модели универсального алгоритмического интеллекта (типа AIXItl) что-то отдаленно похожее и делают.
    Рассуждать же в терминах странных аттракторов, конечно, можно, но все же не слишком продуктивно. Эти странные аттракторы, которые в теории динамических систем выглядят почти что чудом, в теории алгоритмов достаточно заурядны (в силу существенной нелинейности алгоритмов).
    • 0
      странный аттрактор программы, а не данных.
      • 0
        что-то вроде jmp random(). Не совсем понял, что значит «в теории алгоритмов достаточно заурядны», можно какой-нибудь пример.
        • 0
          Да Вы его сами и привели. Генератор псевдослучайных чисел — это простейший пример дискретной динамической системы, работающей в режиме странного (вернее, хаотического) аттрактора.
          • 0
            Если бы этот пример много прояснял, я бы не просил привести еще. Реализация аттрактора это не то. Аттрактор относится состоянию системы(управляющей программе)+внешней среды. Разница такая же как между тем, чтобы испытывать какую-то эмоцию(аттрактор) и описывать. Некоторые участки странного аттрактора образуют эвристические правила, применимые только к текущей ситуации. Цель можно рассматривать как искусственный аттрактор.
            Если задать в качестве цели самосохранение и размножение, получим искусственную живую особь. Если наделить агента способностью моделировать окружающую среду, то получим сознательную особь. Если добавить способность моделировать других агентов — разумную с их точки зрения особь.
            Уместно вспомнить о законах робототехники, т.е. нужно заранее моделировать все важные возможные последствия достижения целей.
            • 0
              Речь о том, что понятие аттракторов возникло для систем, описываемых дифференциальными уравнениями. Его расширение на дискретные системы возможно, но не особо интересно. Например, экспоненциальная расходимость для потоков — достаточно естественное представление, тогда как в случае алгоритмов оно весьма неестественно. Любой if...else… делает алгоритм «неустойчивым» с «мгновенной» расходимостью его ветвей. При куче if'ов у вас сразу будет существенная нелинейность (расходимость «почти в каждой точке») при том, что алгоритмический процесс будет «оставаться в ограниченной области фазового пространства». Для алгоритмов это достаточно банальная ситуация. Для любой сложной информационной системы это банальная ситуация. Странные аттракторы возникают даже в очень простых системах типа Лоренца. Поэтому описание работы мозга как странного аттрактора очень неспецифично… В этой связи и описание цели как аттрактора возможно, но не слишком продуктивно. В этом есть некоторый смысл, но не следует его слишком абсолютизировать. Однако это тоже тема для отдельного большого разговора.
              • 0
                «Поэтому описание работы мозга как странного аттрактора очень неспецифично.» Не согласен, вполне логично рассматривать мозг как динамическую систему. А так как такой подход более общий(алгоритмический процесс слишком уж привязан к языковому описанию), то возможно именно он позволит решить алгоритмические трудности.
                Но спасибо за разъяснение.
  • 0
    Дело в том, что сложность безостановочных алгоритмов может неограниченно возрастать, в то время как алгоритмы, от которых требуется остановка за заранее определенное (в самом алгоритме или исходных данных) число шагов, действительно обладают ограниченными возможностями.

    А вот про эти вещи есть какая-нибудь литература. Очень интересный тезис.

    P.S. Статья супер, яростно плюсую. Вообще, можно ещё добавить то, что обычно критика компьютерного ИИ основывается именно на модели классического алгоритма, машина Тьюринга и т.д. Но тонкость в том, что компьютер умет не только выполнять алгоритмы, но ещё и получать данные извне, и влиять на свой вход (допустим, робот), и это тоже может быть дополнительным источником (в терминах процитированного) увеличения сложности и самоорганизации.
    • 0
      Про литературу вопрос сложный.
      По алгоритмической теории информации ее много. Там сложность индивидуального объекта (строки) определяется как длина кратчайшей программы, которая печатает эту строку и останавливается.
      Отсюда следует банальный вывод, что любая программа, которая печатает некоторый ответ и останавливается, не может породить строку, более сложную, чем она сама.
      Интереснее рассмотреть вопрос, какой сложности строки может порождать безостановочная программа (и вот на этот счет с литературой как-то хуже). Очевидно, такая программа может порождать строки любой сложности!
      Действительно, можно представить себе мата-алгоритм, который перебирает все прочие алгоритмы. Если такой мета-алгоритм должен остановиться, то в нем должен быть зашит некий критерий остановки, и чем сложнее тот алгоритм, который мы хотим породить на выходе, тем сложнее должен быть критерий остановки. В итоге все равно получим, что сложность ответа будет не выше сложности порождающего алгоритма с необходимым критерием. Скажем, если мы на выходе хотим получить алгоритм ИИ, то переборный останавливающийся алгоритм окажется не проще, чем этот самый ИИ!
      Безостановочный же переборный алгоритм сможет породить все, что угодно на выходе, оставаясь при этом простым (естественно, останется вопрос, как из этого «всего, что угодно» будет выбираться «то, что нужно»).
      Но это просто утрированный пример для демонстрации различий в сложности выхода, даваемого остановочными и безостановочными алгоритмами.
  • 0
    А вы бы не могли дать ссылку на работу, доказывающую гипотезу Гольдбаха? Мне казалось, что доказано только слабое утверждение Гольбаха, его еще Виноградов доказал, для очень больших чисел.

    Заранее благодарен!
    • 0
      Если Вы о проблеме Эйлера (бинарной или сильной гипотезе Гольдбаха), так она еще не доказана.
  • 0
    Одному мне показалось, что в приведенной формулировке задачи об остановке не все в порядке?
    Алгоритм-то должен не доказывать факт остановки при конкретных данных, а проверять возмонжость не остановки при любых данных.
    При этом он, как я понимаю, может работать с входным алгоритмом как с белым ящиком.

    Я не утверждаю, что разработка такого алгоритма возможна, просто показываю, что доказательство, приведенное в статье явно упрощено до некорректности.
    • 0
      Нет, в статье неправильно сформулирована проблема останова:)
      На самом деле она заключается в вопросе «останавливается ли данный алгоритм на пустом входе» (или в эквивалентной ей «останавливается ли данный алгоритм на данном входе»). Эта задача даже проще, чем «останавливается ли данный алгоритм на любом входе».
      • 0
        «останавливается ли данный алгоритм на данном входе»

        Но нужно ведь представить общее решение проблемы останова (то есть представить один алгоритм, который эту задачу решает для всех случаев). Куда в Вашей формулировке все кванторы-то делись? В чем «неправильность формулировки» в статье по сравнению с Вашей формулировкой?
        • 0
          Формулировка проблемы останова: по T и Y определить, существует ли X — протокол для машины T на входе Y.
          Ваша формулировка: по T определить, верно ли, что для любого входа Y существует X — протокол для машины T на входе Y.
          • 0
            Хорошо, в тексте статьи написано немного неаккуратно. Но суть-то в том, что неразрешимой является данная проблема в общем виде, то есть когда необходимо построить алгоритм, который для любого T и для любого Y позволяет определить существование X. Поскольку «для любого Y» при постановке этой проблемы все равно появляется, то абсолютно не важно, трактовать ли задачу останова для конкретного Y или сразу для любого. Вы же вообще не формулирует ту проблему, которая является неразрешимой. В формулировке «останавливается ли данный алгоритм на данном входе» не подразумевается, что «данный алгоритм» и «данный вход» могут быть любыми. Для «данного алгоритма и данного входа» может существовать такой алгоритм, который правильно отвечает на поставленный вопрос.
            • 0
              Почитайте, что ли, википедию про кванторы, формальные теории и машину Тьюринга…

              Проблема останова: функция f:(машины Тьюринга)x(входы) -> {0, 1}. f(T, Y) = 1 тогда и только тогда, когда T останавливается на входе Y.
              Ваша формулировка: функция g: (машины Тьюринга) -> {0, 1}. g(T) = 1 тогда и только тогда, когда T останавливается на любом входе.
              Машина с оракулом g способна вычислить f.
              Машина с оракулом f неспособна вычислить g.

              Нумерация предполагается главной.
              • 0
                Вы опять кванторы потеряли. Верните их и все поймете. Если википедия в этом Вам не поможет, можно почитать и нормальные учебники.
                • 0
                  Так, мне надоело.

                  Пусть 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. При разговоре о разрешимости задача вычислимость всегда подразумевается равномерной (т.е. один алгоритм для всех входов). Потому что если разрешить алгоритму зависеть от входа (невычислимым образом), то любая функция становится вычислимой.
                  • 0
                    О, это уже ближе к правде. Только с чего Вы взяли, что «Сформулированная Вами проблема — задача о вычислении g.». Откуда там пустой вход-то взялся?
                    Или Вы не про фразу «Проблема же заключается в том, что доказано отсутствие алгоритма, который бы мог решить задачу останова для любой программы.» (создавалось впечатление, что про нее), а про описанную на пальцах идею доказательства? Так она и не претендует на строгость, но саму идею-то передает верно. Еще нигде не встречалось популярное изложение какой-то проблемы, которое не было бы упрощено до некорректности, как выразился Fahrenheit.
                    • 0
                      Ой-ой-ой, у меня лишний сдвиг по буквам обозначений. Проблема останова — это задача о вычислении g, сформулированная Вами задача — это задача о вычислении k.
                      • 0
                        В формулировке: «Задача останова заключается в том, что необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается» (работает бесконечно долго)» — написано «в некоторых случаях», а не «по крайней мере в одном». Надеюсь, Вы не будете придираться еще к тому, что если в этой фразе «ИЛИ» считать логическим, то в такой формулировке задача станет очевидно разрешимой? ))
                        Вроде, достаточно очевидно, что нас интересует не то, что для всех m f(n,m)==1, а то, что его можно определить для всех m. Для практике же важно установить не просто вычислимость f, но и то, какие именно значения она принимает, поэтому здесь и есть некий уклон в сторону останавливаемости при любых исходных данных. Так что в этой формулировке (с точностью до ее нестрогости, вытекающей из неопределенности естественного языка) ошибки нет.

                        • 0
                          необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается»

                          Т.е. Вы хотите по программе определить, существует ли вход, на котором она зависает.
                          Это — не проблема останова. Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данном входе.

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

                            Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данном входе.
                            Три раза прочитал, так и не понял разницы в этих двух задачах. Действительно, эквивалентные задачи…
                            Последний раз хочется спросить: когда Вас просят решить задачу «зависает ли данная программа на данном входе» в общем виде, что это, по-Вашему, означает? Вы же сами написали, что для любой программы и для любого входа существует алгоритм, который правильно отвечает на вопрос о том, зависает ли данный алгоритм на данном входе.
                            Короче, вообще непонятно, о чем весь этот разговор, кроме как о неоднозначности естественного языка.
                            Второй раз разговариваем, и второй раз Вы воюете с ветряными мельницами, превратно интерпретируя слова (или это банальный троллинг?).
                            • 0
                              Опечатался.
                              Проблема останова — зависает ли данная программа на данном входе. Эквивалентная ей (эти задачи сводятся друг к другу в обе стороны) — зависает ли данная программа на данномпустом входе.


                              когда Вас просят решить задачу «зависает ли данная программа на данном входе» в общем виде, что это, по-Вашему, означает?

                              Предъявить алгоритм, который, получив на вход программу T и вход X скажет, останавливается ли T на X.

                              необходимо определить, останавливается ли некоторая программа при любых исходных данных, или в некоторых случаях «зацикливается»

                              Вроде бы довольно четко указано, что мы разделяем программы на всегда останавливающиеся и на иногда зависающие.
                              • 0
                                Предъявить алгоритм, который, получив на вход программу T и вход X скажет, останавливается ли T на X.

                                Значит, мы все-таки одинаково понимаем проблему останова.
  • 0
    Я знаю звучит как бред) но может расстройства психики как раз и есть алгоритмическая неразрешимость у человека. Если предположить что это так, то мышление поддается алгоритмизации, просто на данном этапе не хватает данных и мощности (как мне кажется Google будет первым кто создаст ИИ)

    А если мышление можно описать алгоритмом, то все что нужно для решения любой неразрешимой задачи, дополнительные данные.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.