Проблема останова, ее неразрешимость
Оценка 4.7

Проблема останова, ее неразрешимость

Оценка 4.7
Научно-исследовательская работа +4
docx
информатика
Взрослым
17.02.2017
Проблема останова, ее неразрешимость
Формулировка проблемы остановки Пусть у нас есть строка с закодированной функцией A (всё равно на каком языке, это не принципиально). Требуется создать функцию F, которая определит, будет ли функция A выполняться вечно или нет (зависнет или не зависнет). Естественно, работа A зависит от входных данных D. Соответственно F должна принимать на вход две переменных: код функции A и входные параметры D. А возвращатьF(A, D) будет логическое значение: True — A(D) остановится, False — A(D) будет работать вечно. По сути, F(A, D) должна проанализировать строки. Зачем решать задачу остановки? Приведу один пример. Всем, кто знаком с задачами криптографии, известно, какую важную роль в этой дисциплине играют простые числа Мерсенна. Человечество прилагает множество усилий по поиску этих чисел. Последнее (пока самое больше) было обнаружено 6 сентября 2008 года и насчитывало 11185272 десятичных знаков. И прямо сейчас десятки тысяч процессоров работают над поиском новых чисел. Числа Мерсенна напрямую связаны с совершенными числами. Все эти числа пока таят множество загадок (во многом поэтому они и используются для шифрования и сокрытия информации), но мне хотелось бы остановиться только на совершенных числах. Совершенные числа — это такие числа, сумма всех делителей которых равна самому числу. Например 6 делится на 1, 2 и 3; 1+2+3=6. 6 — совершенное число. 28 тоже совершенное число. Не смотря на то, что эти числа активно изучаются теоретиками и на их поиски брошены колоссальные вычислительные мощности, пока так и не понятно, сколько этих чисел, ограниченно ли их количество и существуют ли нечётные совершенные числа. Гипотезы о не-существовании нечётных совершенных чисел и о бесконечном их количестве считаются одними из гипотез, особо остро требующих доказательства или опровержений. Программу, которая ищет совершенные числа написать очень просто. Вот пример кода на Python: def perfect_number(): for n in xrange(1, 500): if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n: print "%5d is perfect number" % n perfect_number()
Проблема останова.docx
Проблема останова, ее неразрешимость Формулировка проблемы остановки Пусть у нас есть строка с закодированной функцией A (всё равно на каком языке, это не  принципиально). Требуется создать функцию F, которая определит, будет ли  функция A выполняться вечно или нет (зависнет или не зависнет). Естественно, работа A зависит от входных данных D. Соответственно F должна принимать  на вход две переменных: код функции A и входные параметры D. А возвращатьF(A,  D) будет логическое значение: True — A(D) остановится, False — A(D) будет работать  вечно. По сути, F(A, D) должна проанализировать строки. Зачем решать задачу остановки? Приведу один пример. Всем, кто знаком с задачами криптографии, известно, какую важную роль в этой  дисциплине играют простые числа Мерсенна. Человечество прилагает множество усилий  по поиску этих чисел. Последнее (пока самое больше) было обнаружено 6 сентября 2008  года и насчитывало 11185272 десятичных знаков. И прямо сейчас десятки тысяч  процессоров работают над поиском новых чисел. Числа Мерсенна напрямую связаны с совершенными числами. Все эти числа пока таят  множество загадок (во многом поэтому они и используются для шифрования и сокрытия  информации), но мне хотелось бы остановиться только на совершенных числах. Совершенные числа — это такие числа, сумма всех делителей которых равна самому  числу. Например 6 делится на 1, 2 и 3; 1+2+3=6. 6 — совершенное число. 28 тоже  совершенное число. Не смотря на то, что эти числа активно изучаются теоретиками и на их поиски брошены колоссальные вычислительные мощности, пока так и не понятно, сколько  этих чисел, ограниченно ли их количество и существуют ли нечётные совершенные числа. Гипотезы о не­существовании нечётных совершенных чисел и о бесконечном их количестве  считаются одними из гипотез, особо остро требующих доказательства или опровержений. Программу, которая ищет совершенные числа написать очень просто. Вот пример кода на  Python: def perfect_number():     for n in xrange(1, 500):         if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n:             print "%5d is perfect number" % n perfect_number() Строго говоря, искать совершенные числа можно и более рациональными способами, но все они сводятся к перебору. Просто можно перебирать не все подряд числа. Можно написать функцию, которая ищет совершенное число среди нечётных. Сделать это  очень просто: def odd_perfect_number():     n = 1     while True:         if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n:             return "OK! I FIND IT!"         n += 2 Эта функция завершит работу только если найдётся нечётное совершенное число. Теперь, если бы у нас была волшебная функция F, мы могли бы ей «скормить» наш не  хитрый код и она выдала бы нам результат: остановится наша функция или зависнет. Если  окажется, что функция зависнет, значит нечётных совершенных чисел просто не  существует. Если не зависнет — можно смело начинать поиск. На сегодняшний день доказано, что первое нечётное совершенное число должно быть  больше, чем 10300. Перебор не обнаружил таких чисел, дойдя до 10500. Это далеко не единственный вопрос, который легко решился бы сразу, как только мы  получили бы решение проблемы остановки. Точно таким же способом можно было бы доказать или опровергнуть очень многие  гипотезы современной математики. Например, гипотезу Биля, за которую даже назначена  награда в 100000 долларов США. Но(!) проблема остановки неразрешима. Доказательство неразрешимости проблемы остановки На мой взгляд, программист, на каком бы языке он не программировал бы и какие задачи  бы не решал, проходит в своём развитии три стадии. На первой он умеет очень мало и  большинство задач кажутся ему запредельно сложными. На этом этапе он слеп. Он не  видит решений, даже если они лежат на виду. Когда он набирается опыта у него появляется определённый кураж и он начинает считать все задачи разрешимыми. Он видит до самого  горизонта и ему кажется, что он видит всё, знает всё и может всё. Я много раз видел, как  программисты берутся за задачи, которые либо нельзя решить вовсе, либо нельзя решить  теми средствами, которые они собираются применять. Но когда он набирается не только  опыта, но и знаний, он начинает понимать как велик мир. В нём есть залитые светом  равнины и пещеры в которые никогда не проникает солнце... Неразрешимость проблемы остановки имеет много доказательств. В терминах функций её  очень просто доказать от противного. Допустим, у нас уже есть решение — функция F, которая принимает на вход некую  функцию (вернее строку с текстом функции, байт­кодом или иной записью функции) и  некие данные и отвечает на вопрос: «остановится ли функция­первый­аргумент, при работе с данными­вторым­аргументом, или будет работать вечно?» Давайте создадим функцию P(x), такого вида (на C­образном языке): P(x) {   if F(x,x) then { for(;;) } } Строку, которая кодирует эту функцию обозначим p. Что будет, если мы вызовем  функцию F(p,p)? Возможны два исхода:  True, если если P останавливается. Но при этом P(p) как раз не останавливается,  если F(p,p)=True, то запускается бесконечный цикл.  False, если P зависает. Но, как не трудно видеть, именно в этом случае P(p) не  зависнет. Мы получили противоречие потому, что наша начальная посылка о существовании  магической функции F была не правильной. Получается, что задача останова неразрешима. Вернее, нельзя написать программу,  которая бы решала эту задачу. Иными словами, нельзя написать парсер программного кода, который бы мог оценить, зависнет разбираемый код или нет. Неразрешимость проблемы остановки была впервые доказана в 1936 году Аланом  Матисоном Тьюрингом (Alan Mathison Turing; 1912­1954). Проблем, подобных проблеме остановки, великое множество Проблема остановки только одна из множества так называемых массовых проблем. Эти  проблемы существуют не только в теории алгоритмов, но и в математической логике. В  алгебре такой проблемой является например проблема Туэ (о равенстве  конечнопорождённых и конечноопределённых полугрупп). Одна из наиболее известных  математических проблем для которой доказана алгоритмическая неразрешимость —  десятая проблема Гильберта (кстати, доказал это наш соотечественник Юрий  Владимирович Матиясевич). Алгоритмическая неразрешимость – это не препятствие для алгоритмического ИИ Искусственный интеллект* В замечательном произведении Аркадия и Бориса Стругацких «Понедельник начинается в  субботу» есть такой диалог: – Голубчики, – сказал Фёдор Симеонович озабоченно, разобравшись в почерках. – Это же  проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения. – Мы сами знаем, что она не имеет решения, – сказал Хунта, немедленно ощетиниваясь. –  Мы хотим знать, как её решать. – Как­то странно ты рассуждаешь, Кристо… Как же искать решение, когда его нет?  Бессмыслица какая­то… – Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица – искать решение,  если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет.  Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к  сожалению, не доступен. Решение неразрешимых задач – это не просто художественная метафора. Поспорить здесь  можно лишь с тем, что этот вопрос принципиален не в меньшей степени и для практики.  Как это ни парадоксально, вся область искусственного интеллекта посвящена, по сути,  решению неразрешимых и плохо поставленных задач. Но что это за задачи? Первые выводы о неразрешимости некоторых математических проблем были получены  Гёделем в 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 и только лишь вызовет другую его копию, тем самым парадокс будет снят! В  этом случае выводы из неразрешимости проблемы останова, равно как выводы из теоремы  Гёделя к такой программе будут просто неприменимы. Хотя это вовсе не доказывает  алгоритмическую разрешимость проблемы останова, но устраняет разницу между  компьютером и человеком, когда они поставлены в одинаковые условия. Третий момент заключается в требовании к останову алгоритма. Конечно, требовать от  алгоритмов остановки с выдачей результата вполне естественно для классических  алгоритмов, однако нелепо требовать от искусственного интеллекта того, чтобы он спустя  ограниченное время останавливался и выдавал какой­то конечный результат.  Безостановочные алгоритмы обладают большей мощностью, чем классические алгоритмы и тоже могут быть вполне полезны. К примеру, такой «алгоритм» может выдать какой­то  результат и продолжить работать. Многим ученым не нравится идея безостановочных  алгоритмов, поскольку для них остается вопрос, когда считать, что ответ сформирован,  поэтому свойства таких алгоритмов в математике исследованы меньше. Но для них можно  ввести понятие «вычислимости в пределе»: если на каком­то шаге формируется ответ,  который не меняется в процессе последующей работы безостановочной программы, то  полагается, что задача решена. К сожалению, мало известен тот факт, что классическая  проблема останова является разрешимой в пределе. Таким образом, безостановочность  алгоритма потенциального искусственного интеллекта – это не плохое, а принципиально  необходимое его свойство. Дело в том, что сложность безостановочных алгоритмов может  неограниченно возрастать, в то время как алгоритмы, от которых требуется остановка за  заранее определенное (в самом алгоритме или исходных данных) число шагов, действительно обладают ограниченными возможностями. Итак, существование алгоритмически неразрешимых проблем и ограничения,  накладываемые теоремой Гёделя на формальные системы, по­видимому, не являются  бесспорным аргументом против возможности реализации сильного искусственного  интеллекта как физической реализации некоторого алгоритмического процесса, но  процесса безостановочного и открытого. Имеются и другие «аргументы» против алгоритмизуемости мышления. К примеру, часто  говорится, что результат работы алгоритма полностью и однозначно определяется  начальными данными, в то время как человек обладает «свободой воли». Однако  детерминированность не является ключевым свойством алгоритма. Существуют  вероятностные и недетерминированные машины Тьюринга, результат работы которых  неоднозначен. Однако установлено, что они не расширяют понятия алгоритма в смысле  алгоритмической разрешимости задач. И хотя некий источник хаоса может быть важен для  реализации мышления, идею алгоритмичности это не опровергает. Кроме того,  существенной неопределенностью обладают данные, поступающие в программу из  внешнего мира. Интереснее другое: механическое применение известного алгоритма для нас не выглядит  проявлением умственной деятельности. Если мы не знаем алгоритма умножения двух чисел «в столбик», то умножение каждой конкретной пары чисел для нас будет требовать  интеллектуального напряжения. Но как только алгоритм известен, умножение любых двух  чисел становится малоинтеллектуальной задачей. Может, мышление – это процесс  построения новых алгоритмов в случаях, когда способ решения некоторой массовой  проблемы еще неизвестен? Поиск алгоритма, решающего проблему останова и ряда других проблем в общем случае  невыполним. Но это не мешает исследовать алгоритмы решения этих задач при некоторых  естественных ограничениях. Зачастую поиск этих ограничений и составляет основную  часть решения реальной «неразрешимой» задачи. Не зря говорят, что правильная  постановка задачи составляет уже половину ее решения. Хотя пока не ясно, как  реализовать приближенное решение алгоритмически неразрешимых задач, по крайней мере, теорема Гёделя не накладывает ограничений на возможность этого.  искусственный интеллект +84 5653 208 aideus 22,3 Похожие публикации Искусственный интеллект не уничтожит мир, но может забрать вашу работу 2 февраля в  19:46 Искусственный интеллект нам не угроза 15 декабря 2014 в 19:29 Илон Маск считает, что искусственный интеллект опасен для человечества 21 ноября 2014  в 19:39 Искусственный интеллект и Почему мой компьютер меня не понимает? 9 сентября 2013 в  17:21 Искусственному интеллекту быть 29 июня 2012 в 23:42 Искусственный интеллект и Web: Часть 0 27 января 2009 в 12:43 Может ли страдать тетрадка в клеточку,      или моральные проблемы создания искусственного интеллекта 11 июля 2008 в 03:19 Делаем Искусственный Интеллект 17 мая 2008 в 21:37 История Искусственного Интеллекта, часть 2. Нейросетевой ИИ — неизбежно или  невозможно? 19 марта 2008 в 17:19 История Искусственного Интеллекта, часть 1. Картина без художника. 17 марта 2008 в  18:06 Проблема остановки ­ это проблема построения систематического метода ­ эффективной  процедуры ­ для выявления машин Тьюринга, которые, будучи запущенными в начальном  состоянии на пустой ленте, никогда не остановятся. [1] Проблема остановки сводима к 10 ­ й проблеме Гильберта. [2] Проблема остановки далеко не единственная среди неразрешимых проблем. Есть много  математических задач, общее решение которых было бы очень полезным, однако доказана  их алгоритмическая неразрешимость. [3] Неразрешимость проблемы остановки ­ прямое следствие того, что вычисляемая  универсальной машиной U функция обязательно частичная. Точнее, в § 2.2.10 показано  существование программы Р с кодом Р п, таким, что U ( п, п) не определено. [4] Entscheidungsproblem) проблема остановки Одна из проблем разрешимости,  исследовавшаяся Тьюрингом. Turing machine), на вход которой подается воздействие X.  После запуска машины могут возникнуть две ситуации: машина остановится через  конечное число шагов или машина будет работать бесконечно. Имеется ля возможность  определить, какая из этих ситуаций реализуется на практике. В этом вопросе и содержится проблема остановки. На самом деле эффективная процедура определения возможности  остановки заданной машины Тьюринга при ­ заданном входном воздействии отсутствует. О  проблеме остановки известно, что она неразрешима. [5] Схема Патерсона всегда останавливается. Ясно, что проблемы остановки и расходимости ­ частный случай проблемы  эквивалентности. [6] Предположим, что проблема остановки разрешима; будут ли тогда существовать другие  неразрешимые проблемы. [7] Докажите такое следствие: проблема остановки неразрешима. [8] Схема Патерсона всегда останавливается. Патерсон и А. А. Лети­чевский, проблемы остановки, расходимости и эквивалентности в  классе стандартных схем программ алгоритмически не разрешимы. [9] Если тезис Черча верен, то проблема остановки неразрешима. [10] Хорошо изложенное объяснение того, почему проблема остановки неразрешима.  Доказывает следующую фундаментальную теорему: любой компьютерный язык, в котором  есть условное наклонение и определения через рекурсивную функцию, достаточно  мощный, чтобы запрограммировать собственного интерпретатора, не может быть  использован для того, чтобы запрограммировать собственную функцию остановки. [11] В данной статье показаны возможности инженерного решения проблемы остановки  трещин в конструкциях. Разработаны методы для измерения величин трещиностойкости,  которые управляют процессом остановки трещины в толстостенных элементах  конструкций. Для большого класса конструкций могут быть проанализированы пути  применения этих величин трещиностойкости ­ как на основе динамического, так и на  основе более приближенного, статического, подходов. Такие возможности существуют  сейчас в основном для условий линейно­упругого деформирования, соответствующих  плоской деформации. Для решения практических задач об остановке трещины при высоких напряжениях, распространение которой сопровождается большой пластической  деформацией, необходимы дополнительные исследования. Они включают изучение  пластического поведения материала и его взаимодействия с трещиной в течение коротких  промежутков времени при высоких скоростях деформирования, типичных для быстрого  роста и остановки трещины. Необходимы также методы анализа остановки трещины при  смешанном разрушении и разрушении полностью путем среза. Исследования корреляций с  результатами стандартных испытаний, таких, как испытания по Шарпи, испытания  падающим грузом и обычные испытания для определения трещиностойкости, могут со  временем облегчить задачу оценки трещиностойкоети по отношению к остановке. [12] Основополагающей теоретической и практической проблемой для информатика  является проблема остановки. Она допускает множество вариантов. [13] Теорему 1.3 часто интерпретируют как утверждение о не разрешимости проблемы  остановки ( для МНР­программ), в ка тором говорится о том, что не существует никакого  эффектиЯ ного общего метода установить, остановится ли некотора конкретная  программа, запущенная после введения в нее не которого конкретного набора начальных  данных. [1] Применение только депрессаторов без дополнительных мероприятий не позволяет  решить проблему остановки скважин в зимнее время. [2] Для машин Минского и, следовательно, счет­чиковых автоматов неразрешима проблема  остановки ( останавливается ли машина, начав работать с заданными начальными  значениями счетчиков. [3] Заметим также, что одной из актуальных проблем прочности являтся проблема остановки трещины. Решение указанной инженерной проблемы приводит к необходимости знания  путей распространения разрушения. Последняя задача, достаточно трудная для  однородной среды, существенно усложняется при наличии включений и иных  неоднородностей. [4] Тьюринг вводит абстрактную модель цифровой вычислительной машины и доказывает  неразрешимостьпроблемы остановки и проблемы разрешимости для логики первого  порядка. [5] Тьюринга сводится к про блеме конечности автономного поведения, а поскольку проблем  остановкиалгоритмически неразрешима, то неразрешима и про1 блема конечности. [6] Однако, очевидно и то, что более глубокое проникновение в проблему остановки  трещины возможно, если понят механизм инициирования и развития трещины.  Следовательно, оправдана подробное рассмотрение основных факторов, влияющих на  инициирование и, распространение трещины. [7] Вопрос о соотношении между результатами о неразрешимости, например теоремой Геделя  или проблемой остановки для машин Тьюринга, и возможностями машин решать задачи  был достаточно запутан как в литературе, так и в умах многих исследователей. Никем не  было показано, что мозг имеет преимущество перед машинами, так как он может  использовать теорему Геделя для доказательства справедливости некоторых недоказуемых высказываний. Однако нет причин, мешающих машине воспроизвести эти же самые доводы, пользуясь вышеупомянутой якобы непротиворечивой метасистемой; в этом нет ничего  такого, что выходило бы за рамки обычных стереотипных доказательств. [8] В добавление к этим следствиям, касающимся транслируе­мости, техника языков значений  имеет также следствия, касающиеся разрешимости проблемы остановки для данного  класса схем. Это вытекает из того, что проблема пустоты разрешима для контекстно­ свободных языков, но неразрешима для рекурсивно­пере­числимых языков ( Хопкрофт и  Ульман [2], стр. [9] Еще одна родственная проблема, подобным же образом оказывающаяся неразрешимой,  если только тьюрингово понятие вычислимости универсально, ­ это проблема  остановки из упр. Тьюринга ( неважно, в стандартной или в какой­либо иной заключительной конфигурации), если ее запустить в начальном ее состоянии считывающей  самую левую клетку в сплошном массиве единиц на ленте с пустыми символами во всех  остальных клетках. Замечательно, что независимо от того, принимается тезис Черча или  нет, следующая функция Л, вычислимость которой в интуитивном смысле эквивалентна  разрешимости проблемы остановки, оказывается, как можно доказать, невычислимой по  Тьюрингу: Л ( тп, п) 2 или 1 в соответствии с тем, остановится в конце концов или нет  машина Тьюринга с номером т, если ее запустить в начальном состоянии считывающей  самую левую единицу в сплошном блоке из п единиц на ленте с пустыми символами во всех остальных клетках. Таким образом, если тезис Черча верен, то проблема остановки  неразрешима. [10] Мы доказываем неразрешимость логики первого порядка от противного: мы докажем, что  если бы соответствующий тест существовал, то проблема остановки оказалась бы  разрешимой, т.е. существовала бы эффективная процедура для ответа на вопрос,  останавливаются ли в конце концов машины Тьюринга, если их запускать в состоянии gi на  самой левой единице в некотором массиве единиц на ленте с пустыми символами в  остальных клетках. [11] Чтобы подробно разобраться в этом вопросе, предположим, что у нас есть некий алгоритм, который иногда позволяет решить проблему остановки. [12] Хотя исследования по определению скорости распространения трещины были основаны на  этом или другом равнозначном энергетическом критерии, его использование для  решения проблемы остановки трещины было минимальным. Следовательно, наибольшая  часть современной литературы об остановке трещины базируется на статических или  квазистатических схемах, хотя ниже рассмотрены и динамические явления. Более того,  применение статических методов анализа предложено по меньшей мере половиной  исследователей, которые изучали роль динамических эффектов. Ирвин и Уэллс ( 1965 г.)  предложили рассматривать остановку трещины как простое реверсирование по шкале  времени возможных начальных явлений плоской деформации. Основываясь на этой  концепции, можно представить схематично критерий остановки трещин, как и критерий их  неустойчивого распространения. [13] Используя так называемый диагональный метод, Тьюринг построил доказательство того,  что не существует алгоритма, который может успешно рассмотреть все частные  случаи проблемы остановки. [14] Таким образом, если мы можем отыскать k, то мы знаем, как построить вычислительную  процедуру, для которой алгоритм не дает решения проблемы остановки, но нам ответ  известен. Необходимо тщательно изучить конструкцию Я ( п; т) и Т ( т) и понять, как в точности действует 1 Т ( п) х Я ( п; п) в качестве машины Тьюринга. Возможно, мысль о  том, что мы умнее каких­то алгоритмов, принесет нам некоторое удовлетворение. [15] Вспоминая, что множество пар ( р, х) программа р завершает работу на входе х является  одним из т­пол­ных перечислимых множеств, можно сказать, что 0 вы числимые функции  вычисляются машинами, которым придан специальный оракул, решающий проблему  остановки: этому оракулу посылают программу и вход, и он отвечает, останавливается ли  эта программа на этом входе или не останавливается. При этом посылаемая на экспертизу  программа ­ самая обычная, без обращений к оракулу. [1] Однако проблема остановки трещины связана с некоторой неопределенностью  статического подхода к ее решению. Тем не менее предложено рассматривать остановку  трещины как явление, обратное ее инициированию относительно шкалы времени. Эта  концепция говорит о том, что все накопленные знания, касающиеся механизма  инициирования трещины, основываются на решении проблемы остановки трещины, и  фактически большая часть работ посвящена этому вопросу. Накопленный опыт  подтверждает это, хотя неясно, идентичны ли значения К и Gc для остановки и  инициирования трещины. [2] Однако эта ситуация не настолько безнадежна, как это может показаться на первый взгляд. С практической точки зрения решение проблемы остановки трещин имеет наиболее  важное значение для тех материалов, которые не обнаруживают заметной пластичности во  время быстрого распространения трещины. Случаи быстрого, катастрофического  разрушения происходят в условиях, когда пластическая зона по фронту трещины  практически мала. Поэтому использование методов линейной механики хрупкого  разрушения ( с учетом динамических эффектов) может стать эффективным при решении  проблемы остановки трещин. [3] Неразрешимые проблемы разрешения впервые были обнаружены при исследовании основ  понятия алгоритма. Как правило, базисной проблемой разрешения является проблема  остановки для машины Тьюринга. В ней ставится вопрос, существует ли алгоритм,  который для любого слова в ленточном алфавите некоторой машины Тьюринга решает,  остановится или нет эта машина, если она начнет работу в положении, когда читающая  головка стоит у первого слева символа рассматриваемого слова, которое считается  отпечатанным на ленте. [4] К ним относится проблема распознавания самоприменимости машин Тьюринга, проблема  остановки алгоритма, проблема распознавания принадлежности числа данному  нерекурсивному множеству натуральных чисел. [5] Сопротивление их хрупкому разрушению может быть настолько высоким, что проблема  остановки трещинможет стать второстепенной, поскольку инициирования трещины может не произойти. Эффективными оказались композитные металлы, содержащие как  высокопрочную компоненту, несущую нагрузку, так и вязкую компоненту, которая  обеспечивает остановку трещин. Создание в конструкциях специальных отверстий и  полостей для проверки влияния второй компоненты композитного металла на его  сопротивление хрупкому разрушению, а также применение нагретых зон позволяют  выявить дополнительные эксплуатационные возможности материала в специфических  условиях. [6] Иерархия Хомского. Это обстоятельство приводит к неразрешимости проблемы распознавания принадлежности  данного выражения заданному языку. В действительности приведенные сейчас  рассуждения служат неким обоснованием неразрешимости так называемой проблемы  остановки: не всегда можно предусмотреть, остановится данная машина или нет. [7] Но, полагая х т, мы видим, что абак с номером т, запущенный с т камешками в регистре RI  и всеми остальными пустыми регистрами, останавливается тогда и только тогда, когда он  не делает этого. Значит, такого абака не существует, а потому никакой абак не вычисляет  функцию h и проблема остановки абаковнеразрешима. [8] Например, невозможно в полной общности решить, зацикливается ли программа Р или еще, эквивалентна ли Р программе Q. Если бы такое решение было возможно, то ( в  противоречии с предыдущим) решалась бы ипроблема остановки. [9] На этом основании делается вывод, что исследуемая проблема также алгоритмически  неразрешима. Если бы существовало решение задачи ПАСС с произвольной функцией Л  разметки, то данное сведение позволило бы решить проблему остановки машины  Тьюринга, которая, как известно, является алгоритмически неразрешимой. [10] Читатель может заметить определенное сходство между рассуждениями,  устанавливающими, вопреки недоказуемости, истинность Р & ( &), и парадоксом Рассела.  Помимо этого, наблюдается сходство и с доказательством Тьюринга о невозможности  существования машины Тьюринга, которая могла бы решитьпроблему остановки. Эти  сходства не случайны. Между этими тремя событиями имеется прочная историческая  нить. [11] Он построил около полудюжины простых хорновских дизъюнктов, представляющих  необходимый механизм УМТ, и доказал затем, что любая вычислимая по Тьюрингу  функция может быть вычислена с помощью резолюции, исходя из этих дизъюнктов в ответ  на соответствующие целевые утверждения. Кроме того, хорошо известный факт о том, что  не существует никакого алгоритма, позволяющего решить, закончится или нет  произвольное тьюрингово вычисление ( проблема остановки), преобразуется тогда в  эквивалентный факт: не существует никакого алгоритма, позволяющего решить, дает ли  произвольная программа на хорновских дизъюнктах конечное успешное резолютивное  вычисление. Это в свою очередь просто вариант того факта, что общезначимость  произвольных предложений в логике первого порядка не является полностью  разрешимой. [12] То есть мы покажем, что процедуру Е вместе с некоторыми другими, существование  которых неоспоримо, можно было бы применить для решения того частного  случая проблемы остановки, неразрешимость которого была доказана ранее;  следовательно, предположение о существовании Е приводит к противоречию. [13] Розенберг в [7] и независимо от него авторы установили ряд результатов по  неразрешимости, включая результат для автоматов с двумя головками. Оказалось, что для  моделирования этих автоматов в известном смысле могут быть использованы схемы с  двумя ячейками, и мы воспользуемся: этим обстоятельством, чтобы установить  неразрешимость разного вида проблем остановки и проблем эквивалентности для схем  программ. [14] Таким образом, машина Мт останавливается тогда и только тогда, когда машина Мп не  делает этого ( т.е. в точности тогда, когда Л ( п, п) 1), если обе их запустить в их начальных состояниях считывающими самую левую клетку сплошного блока из п единиц на ленте с  пустыми символами во всех остальных клетках. Подставляя т п, мы убеждаемся, что  существование машины Мт невозможно, а потому не существует и машины Я: функция Л  невычислима по Тьюрингу независимо от того, справедлив тезис Черча или нет. Иными  словами, проблема остановки не допускает решения с помощью машины Тьюринга. Если  же принять тезис Черча, то она неразрешима и в абсолютном смысле. [1] Мы доказываем неразрешимость логики первого порядка от противного: мы докажем, что  если бы соответствующий тест существовал, то проблема остановки оказалась бы  разрешимой, т.е. существовала бы эффективная процедура для ответа на вопрос,  останавливаются ли в конце концов машины Тьюринга, если их запускать в состоянии gi на  самой левой единице в некотором массиве единиц на ленте с пустыми символами в  остальных клетках. Черча верен, проблема остановки неразрешима. В частности, мы  доказали, что никакая машина Тьюринга не может реализовать процедуру, решающую  проблему остановки, и отметили, что, согласно тезису Черча, это означает невозможность  какой бы то ни было эффективной процедуры, решающей проблему остановки. [2] Как известно, общим в постановке таких проблем является поиск ответа на вопрос,  обладает ли исследуемый объект интересующим нас свойством, определяющим его  принадлежность к множеству всех объектов, этим свойством обладающих. Известен ряд  классических неразрешимых проблем. Так, неразрешимость проблемы  остановки означает, что нельзя построить алгоритм, который устанавливал бы,  остановится ли машина Тьюринга, начав работать над любым словом в заданном алфавите.  Неразрешима и более частная проблема: остановится ли машина Тьюринга, работающая с  пустой лентой, не содержащей никаких символов, кроме пустого. [3] Но в некоторых случаях этого недостаточно. Мы показываем, что проблема  остановки сводится к этой задаче. При этом нам важно, чтобы определение алгоритма  было как можно проще. [4] Дело в том, что, согласно главному результату предыдущей главы, некоторая данная  машина не останавливается при данном входе тогда и только тогда, когда некоторое  предложение ( конъюнкция отрицания предложения Я и всех членов множества А)  выполнимо. Но алгоритмический позитивный тест дляпроблемы остановки очевидным  образом существует, а именно, следует имитировать выполнение машинных операций,  применив машину при заданном exodel Итак, если бы существовал алгоритмический  позитивный тест для выполнимости, то для проблемы остановки имелись бы и позитивный,  и негативный тесты и, значит, проблема остановки была бы разрешима. [5] Один из фундаментальных инструментов, используемых в проведении границы между  разрешимыми и неразрешимыми задачами, ­ понятие сводимости, которое было впервые  выдвинуто на первый план благодаря работе логика Эмиля Поста. Задача А сводима к  задаче В, если, исходя из процедуры, способной решить задачу В, можно построить  алгоритм для решения задачи А. Например, большое значение имел следующий  результат: проблема остановки сводима к 10 ­ й проблеме Гильберта. Отсюда следует, что 10­я проблема Гильберта должна быть неразрешимой, так как в противном случае мы могли бы использовать это сведение, чтобы построить алгоритм для проблемы остановки,  которая, как известно, неразрешима. [6] Рассмотренная в теореме 1.1 неразрешимая проблема х Wx важна по нескольким  причинам. Одна из них состоит в том, что неразрешимость многих проблем можно  доказать, показав, что они по крайней мере не проще, чем эта. Именно таким путем мы без  большого труда доказали, что проблема остановки ( теорема 1.3) неразрешима: этот  процесс называется сведением одной проблемы к другой. [7] Возникает естественный вопрос: каким образом следует определять, остановится какая­то  определенная машина Тьюринга ( в которую введены конкретные начальные данные) или  нет. Для многих машин Тьюринга ответить на этот вопрос нетрудно, но, как мы видели  выше, иногда для ответа может потребоваться решение какой­нибудь до сих пор не  решенной математической задачи. Так существует ли некая алгоритмическая процедура  для решения общей проблемы ­ проблемы остановки ­ полностью механическим путем. [8]

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость
Материалы на данной страницы взяты из открытых истончиков либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
17.02.2017