Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Научпоп доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 32
Как с помощью его машины формализовать какой-либо workflow, например, схему в нотации BPMN или EPC?
Доброго времени суток . Машина Тьюринга (МТ) может формализовать любой workflow, выраженный в BPMN или EPC, потому что она является универсальной вычислительной моделью. Мы можем представить схему процесса как алгоритм, данные процесса (токены, переменные) — как входную строку на ленте, а саму МТ — как интерпретатор (движок), который исполняет этот алгоритм над данными.
Хотя это возможно теоретически, на практике это было бы аналогично программированию веб-приложения непосредственно в машинных кодах процессора — возможно, но лишено смысла для практического использования. Ценность формализации через МТ — в строгом доказательстве выразительной мощности и в анализе фундаментальных свойств (например, может ли процесс завершиться?).
Любой процесс можно представить как последовательность шагов (состояний) и правил перехода между ними.
Определим формальную систему:
Представим множество состояний МТ (Q):
Q = {q_start, q_fetch, q_decode, q_execute, q_eval, q_cond_true, q_cond_false, q_join, q_halt} ∪ Q_nodesТогда представим алфавит ленты (Γ) , как :
Γ = {#, S, T, G, E, X, Y, Z, 0, 1, (, ), [, ], →, ∧, ∨, ¬, @, $}#— разделитель команд/данных.S, T, G, E— тип узла (Start, Task, Gateway, End).X, Y, Z— имена переменных.0, 1— значения переменных/токенов.(, ), [, ]— скобки для выражений и данных.→, ∧, ∨, ¬— логические операторы.@— маркер позиции токена.$— маркер конца данных.
Начальное состояние:
q_0 = q_startФункция перехода:
δ: Q × Γ → Q × Γ × {L, R, N}
Кодируем BPMN-процесс на ленте МТ:
Рассмотрим процесс:[Старт] → [Задача A] → {XOR-шлюз} → [Задача B] → [Конец] ↘ [Задача C] → [Конец]
Тогда закодируем граф , как :
#S@1# // Стартовое событие с активным токеном
#T(A)@1# // Задача A
#G(XOR)# // XOR-шлюз
#IF(X=1)THEN(T(B))ELSE(T(C))# // Условное ветвление
#T(B)@0# // Задача B (неактивна)
#E@0# // Конец 1
#T(C)@0# // Задача C (неактивна)
#E@0# // Конец 2
#DATA[X=0]$ // Область данныхПосле можно реализовать код на Python ( например эмуляция MT для BPMN ) .
эмуляция MT для BPMN
Есть такая?
В BPMN только стартовых событий 23 шт., а финальные такие как Компенсация и Терминатор ведут себя по-особенному (последний удаляет все токены из процесса).
Могу предложить такой код на Python (эмуляция MT для BPMN )
Код часть 1
Могу код более подробно расписать , чтобы было понятнее .
Схему алгоритма бы что-ли. Не очень понятно. Я так математизировал через WF2M-сеть. Там ведь нужно показывать время выполнения операции: сколько тактов маркер будет ожидать в узле типа "операция". Как формализовать and-join (синхронизатор). А кроме workflow еще бы и docFlow показать бы через МТ.
существуют чётко поставленные вопросы, на которые мы никогда не получим однозначный «да» или «нет» от любой вычислительной машины.
Это не то. А если вычислительная машина просто выдает длину кода входной строки?
Должно быть - не существует такой машины, которая получив на вход код любой другой машины сможет однозначно отвечать на вопрос о завершении работы этого кода на конкретной переменной.
Т.е. невозможно обойтись без этих кожанных тупых мешков везде(!), хотя и кажется что местами эта замена удачна.
Доброго времени суток . Соглашусь с вами , да, я допустил грубое упрощение. Существует бесконечное множество «чётких» вопросов, на которые машина может дать однозначный ответ (длина строки, чётность числа, синтаксическая корректность). Проблема остановки — не про «любые» вопросы, а про конкретный класс самореферентных вопросов о поведении программ.:
Более корректная формулировка звучит так : Пусть 
— множество всех программ (машин Тьюринга).
Функция 
{0, 1}, где
, если машина 
останавливается на входе 
,
в противном случае,
— не является вычислимой.
Я должен был сказать точнее: не существует универсальной вычислимой процедуры, отвечающей на вопрос «
остановится?» для всех пар 
. Это специфический, но фундаментально важный вопрос, отделяющий «вычислимое» от «узнаваемого».
готов в конце упомянуть , что ваша последняя фраза о «кожанных мешках» — блестяща. В этом и есть главный философский вывод: для решения таких задач (верификация, понимание смысла, оценка последствий) нам всё ещё принципиально нужен неалгоритмический интеллект — наш человеческий разум, со всей его «тупостью» и гениальностью. Замена удачна лишь там, где вопрос не требует выхода за рамки формальной системы. Проблема остановки показывает границу этой замены.
расскажите еще про вычислительную эквивалентность машин Тьюринга, частично рекурсивных функций, перечислимых множеств, формальных языков.
Если помню правильно, то это называлось "тезис Чёрча", что эти конструкции суть одно и тоже (а то есть такие кодеры, что готовы тут же на java решить любую задачу).
И еще интересней рассказ про теорему Мучника о существовании несравнимых по сложности частично рекурсивных функций. Т.е. нет такой самой сложной программы (сокровенное знание) владея которой можно вычислить любую другую программу.
И нужен не только один кожанный мешок,а целая толпа, если нужно решать сложную задачу. ))
Доброго времени суток . Ваш комментарий затрагивает сердцевину теоретической информатики. С большим интересом рассмотрю возможность подготовки отдельных статей, подробно разбирающих:
Доказательство эквивалентности моделей вычислений
Структуру степеней неразрешимости и теорему Мучника
Практические следствия этих результатов для современной computer science.
Эти темы остаются актуальными для понимания фундаментальных границ вычислимости и организации сложных вычислительных систем.
Машина, которая никогда не останавливается: как одно предложение поставило предел человеческому познанию
Оно устанавливает фундаментальный, алгоритмический предел: существуют чётко поставленные вопросы, на которые мы никогда не получим однозначный «да» или «нет» от любой вычислительной машины.
Т.е. предел в том, что предела нет?
Зарегистрирован 9 декабря, сегодня 30 декабря, и уже 7 подобных статей. Как же достали ИИ, без кулдауна генерирующие бред на хабре!
Доброго времени суток. Что касаемо предела , то тут так : предел есть. Доказательство Тьюринга как раз и устанавливает чёткий, абсолютный предел: нельзя алгоритмически решить проблему остановки. Это не «предела нет», а «здесь — стена». Мы нашли её координаты.
Что касаемо статьи , то эта статья — результат личного интереса и несколько дней работы. Все примеры кода проверялись в MATLAB, логика выверялась по учебникам.
Ваша критика — лучший стимул писать лучше, глубже и ответственнее.
Я только не понял почему циклы не считаются остановкой программы?
Я меня так все остановки реально в циклы уходят. Это вполне себе остановки. И их отлично ловит вотчдлог, т.е. они обнаруживаемые.
Как так?
цикл может быть неповторяющимся. Допустим в цикле перебираем увеличивающиеся числа в поисках контрпримера к гипотезе Гольдбаха.
Доброго времени суток . Вы задали правильный и важный вопрос. Давайте разберемся по порядку.
1. Что такое «остановка программы» в теории?
Это когда программа сама завершает работу и возвращает управление (например, операционной системе). В этот момент её процессорное время обнуляется, память освобождается.
2. А что такое «бесконечный цикл»?
Это программа, которая продолжает работать, выполняет инструкции, занимает процессор и память, но никогда не выдаст финальный результат и не завершится сама. Это работа, а не остановка.
Аналогия из жизни:
Остановка — вы приехали на станцию, вышли из поезда, поезд уехал в депо.
Бесконечный цикл — поезд едет по круговому маршруту без конечной станции. Он всё ещё в пути, он не «остановился».
3. При чём здесь вотчдог и мониторинг?
Вотчдог ловит симптом: «программа не отвечает уже N секунд». Но он не знает наверняка, действительно ли программа зациклилась навсегда — возможно, она просто очень долго вычисляет что-то сложное (например, перебирает варианты в шахматах). Вотчдог лишь гадает на основе таймаута. А проблема Тьюринга — именно о гарантированном знании для любой программы заранее.
В итоге могу сказать , что да, вечный цикл — это форма работы программы, а не её завершение. И невозможность определить наверняка, завершится программа или навсегда зациклится, — это и есть главное открытие Тьюринга.
Спасибо за вопрос — он вскрывает самую суть терминологической путаницы, которая часто возникает при первом знакомстве с проблемой остановки.
Я не понял вашего ответа.
Он мне звучит так - цикл это не остановка потому что это не остановка.
Процессор в принципе не останавливается даже когда заходит на точку останова, там генератор всегда включен и где-то что-то на аппаратном уровне все-равно выпоняется.
Вочдог не сработает случайно если это настоящая программа. Поэтому он обнаружит только остановки в виде пустых циклов, не важно что эти циклы там вычисляют. Ну да вотчдог как бы по времени, но можно же сделать и вочдог по действиям. Например программа точно что то должна сделать на всем протяжении свое работы.
Я бы все же задался вопросом про обнаруживаемость этих самых циклов.
Потом скажем что-то в цикле бесконечно вычисляется, чтобы не было повторяющегося паттерна, но тогда размерность данных должны быть бесконечной, но тогда и сама программа должна сразу быть бесконечной.
Запутанно как то все.
Доброго времени суток .
Давайте еще раз подробно разберемся .
Что такое остановка программы формально?
Это когда программа достигает заключительного состояния, определённого в её алгоритме. Для машины Тьюринга — это специальное состояние 
. Цикл — это работа в рабочих состояниях без перехода в .
Проблема остановки спрашивает: можно ли заранее, по коду программы, гарантированно определить, достигнет ли она ?
Вотчдог же лишь наблюдает за уже запущенной программой. Если программа за 10 лет не изменила состояние — это может быть либо бесконечный цикл, либо просто очень медленный расчёт. Вотчдог не может отличить одно от другого гарантированно.
Вы правы: если память программы конечна (N бит), то число её возможных состояний конечно: 
. Значит, рано или поздно состояние повторится — и это можно детектировать. В этом случае проблема остановки технически разрешима (хотя и за экспоненциальное время).
Но! Машина Тьюринга имеет бесконечную ленту, поэтому число её состояний не ограничено. Она может вечно писать новые символы и никогда не повторять состояние. Именно поэтому в общем случае (для абстрактной МТ) проблема неразрешима.
Важно подметить , что для реальных программ на реальных компьютерах (с конечной памятью) полная остановка действительно может быть обнаружена в теории. Но на практике это требует нереального времени и памяти. А Тьюринг говорил об идеальных машинах, где такие ограничения сняты.
Проще говоря:
В теории (машина Тьюринга с бесконечной лентой) — нельзя заранее сказать, остановится программа или нет.
На практике (ваш компьютер) — можно, если ждать достаточно долго и следить за состояниями. Но это не отменяет теоретического результата Тьюринга.
способности решать колоссальное, но всё же ограниченное подмножество задач из области человеческих интересов
Пытаетесь подменить тезис? Совершенно не элегантно вышло. «Существуют алгоритмы со свойством Х» совершенно не значит, что доля этих алгоритмов велика, что они входят в область значимых интересов (а не только теоретических), а так же не значит, что для нужного алгоритма нельзя сделать отдельный анализатор или обрезать алгоритм так, что бы решить какую-либо практическую задачу.
В целом мы знаем, что познание ограничено, но глупо делать из этого вывод, будто оно ограничено сильно или что для ИИ предел познания невысок. Это всё равно что знать, в океане водятся акулы. И поэтому не купаться нигде и когда, ещё и другим доказывать, что купание - ограниченная вещь.
Доброго времени суток . Вы абсолютно правы — я совершил логическую подмену, и ваша критика точечна. Разберем математически :
Пусть:
— множество всех алгоритмически формулируемых задач
— неразрешимые задачи (U≠∅, по Тьюрингу)
— практически значимые задачи
— некая мера «важности» или «частоты встречаемости»
Моя ошибочная импликация:
В итоге мы не знаем 
. Более того, часто:
потому что на практике мы:
Сужаем область: рассматриваем подкласс
, где задача разрешимаОслабляем условие: вместо точного решения ищем
-приближениеМеняем формулировку: переходим к разрешимой проблеме принятия решения
Если развивать дальше вашу аналогию с акулами , то :
Пусть 
— океан всех вычислительных задач,
— область, где водятся акулы (неразрешимые проблемы),
— пляжи, где люди actually купаются (практические задачи).
Мой первоначальный тезис звучал как: «Раз S≠∅, то
опасно мал».
Ваша поправка: Нам важно не S, а плотность акул в окрестности B. И оказывается, что:
для большинства практически релевантных 
.
Более того, мы умеем строить бассейны (специализированные формальные системы) и сетки (статический анализ для определённых классов программ), где:
и при этом 
достаточно велик для практических нужд.
В итоге могу сказать , что теорема Тьюринга — не про количество доступных нам задач, а про структуру доступности. Она показывает, что пространство вычислимых функций имеет сингулярности (неразрешимые проблемы), но не говорит о мере множества регулярных точек вокруг них.
То ли написано некорректно, то ли я тупой, но я не вижу тут никаких противоречий.
Задача поставлена корректно - некая программа (P), которая может делать анализ кода и входных данных другой программы (H) и отвечать на вопрос зациклится H или нет.
А дальше в мысленном эксперименте делается допущение, что программу H можно сделать такой, чтобы она отвечала обратное от P(H), но с чего все решили что это вообще возможно? Это нарушает причинно/следственные связи как минимум, такая программа не возможна в принципе, это похоже на парадокс брадобрея или парадокс классификаторов.
Более того, с точки зрения P выполняемость условий для H зависит только от её кода и входных данных и не требует выполнения H как таковой.
А вот по условиям «противоречия» нужно чтобы H ВЫПОЛНИЛО P(H), но в КОДЕ это невозможно задать динамически. Это всё-равно будут конкретные байты.
Что бы там H не решила по поводу P(H) ее код на момент анализа его программой P будет фиксирован и не может меняться во время анализа.
Так что как минимум это «противоречие» не верно.
Может кто-нибудь более умный что-ли пояснить где я тут не прав?
Доброго времени суток .
Главное уточнение: P не анализирует результат выполнения H, а анализирует код H.
Пусть:
H— программа-оракул, которая всегда останавливается и выдает вердикт:1(остановится) или0(зациклится).P— программа, которая получает на вход код другой программыXи делает следующее:Вызывает
H, передавая ей код X и код X же в качестве входных данных. То есть спрашивает: «Что скажет H про вычислениеX(X)?»Получает ответ
H(1 или 0).Если H сказала «1» (X(X) остановится), то P уходит в бесконечный цикл.
Если H сказала «0» (X(X) не остановится), то P немедленно завершается.
Но где же здесь тогда противоречие ?
Рассмотрим случай, когда X = P. Что происходит, когда мы спрашиваем H про P(P)?
Предположим,
Hговорит «1» (P(P) остановится).
Тогда, запускаяP(P), мы видим:Pполучит отHответ «1» и, по своему коду, уйдет в бесконечный цикл. Значит,P(P)не остановится. Противоречие:Hошиблась.Предположим,
Hговорит «0» (P(P) не остановится).
ТогдаP(P)получит отHответ «0» и, по своему коду, немедленно завершится. Значит,P(P)остановится. Противоречие:Hснова ошиблась.
Вы верно заметили: код P фиксирован. H анализирует этот фиксированный код. Она не должна «выполнять P(H)», она должна предсказать, что будет, если этот код выполнить.
Суть в том, что H — по предположению — всегда дает правильный ответ для любой пары (программа, вход).
Если такой H существует, то и P (которая использует H как подпрограмму) тоже существует — её код фиксирован и корректен.
Анализ H для P(P) должен дать ответ, исходя из этого фиксированного кода P. Но любой ответ приводит к тому, что реальное поведение P(P) будет противоположным. Следовательно, такой H не может существовать.
Здесь нет нарушения причинности, есть логический парадокс, аналогичный «это утверждение ложно». Мы предполагаем существование H → строим P → получаем противоречие → значит, H не существует.
В итоге , вы правы, что P не может динамически менять код H. Но она и не должна — ей достаточно иметь код H как часть себя. Противоречие возникает не из-за изменения кода, а из-за того, что предсказание H о поведении P(P) заведомо несовместимо с реальным поведением P(P), которое определяется этим же предсказанием.
Тут использовано допущение, что код H можно вставить в P, но реальные программы гораздо сложнее, чем просто "код". Более того, код H может быть "написан" вообще на мета-архитектуре, которую невозможно принципиально встроить ни в какие P. Например, на квантовых эффектах. Или на принципиально отличающейся архитектуре, которую невозможно описать кодом. Формально это будет некий "чёрный ящик", на вход которого подаётся что-то и получается ответ и единственным способом получить ответ H - вызвать H, но это уже исполнение, что P делать не может (она содержит только код). Причём сам "вызов" H может происходить способом, совершенно произвольным и который к компьютерам вообще не имеет отношения.
То есть Тьюринг был не прав, если говорить о задаче как "Можно ли создать некую программу, которая получит на входе набор код + входные данные и ответит гарантировано и верно зациклится или нет".
Более того, H может содержать реальный настоящий рандом, ей это по условию можно, а вот P нельзя. Но я пока не развивал эту теорию.
Так же H может возвращать разные данные, выполняется она сама по себе или в составе другой программы.
H может переписывать себя, может являться неким AGI с доступом к производственным мощностям и так далее.
А у меня, кстати, давно уже есть решение данной проблемы. Решение: Н уходит в бесконечный цикл(пытаясь выяснить ответ).
И противоречие исчезает. Ответ будет получен через бесконечное количество времени.
Да, решение противоречит оригинальному условию "Н всегда останавливается" . Ну это сродни условию: "Все числа можно делить друг на друга". А потом появляется ноль и нужно придумывать бесконечность. А потом оказывается, что у функций есть полюса и области определений, например. Проблема остановки таким образом это частный случай, своего рода полюс функции. Показывает, что у условной функции алгоритма Н существует полюс (входные данные, при кототорых ответ невозможен).
у условной функции алгоритма Н существует полюс (входные данные, при кототорых ответ невозможен).
иными словами, программа в том виде как это сформулировано изначально невозможна. Программа которая для некоторых входов возвращает результат а для других входов зависает (и таких входов отнюдь не один, потому что сформулировать контпример можно счетным числом способов) - конечно существует, например такую легко написать: "если программа останавливается за один такт - возвращаем 1, иначе зависаем".
А настоящее объяснение такое: программа-оракул Н для всех машин размером не больше N возможна, но сама Н будет иметь размер больше N. Простой пример такого оракула: исполняем входную программу BB(N) тактов (см. Busy Beaver), если она не остановилась за это время то она не остановится никогда.
И только при переходе к бесконечности, т.е. к оракулу для машин произвольного размера мы получаем противоречие.
Ну и еще одно замечание, для неформального понимания. Если бы такая программа оракул существовала, она могла бы решить примерно любые открытые математические проблемы. Все эти Теоремы Ферма, гипотезы Гольдбаха, поиски нечетных совершенных чисел, раскраски карт разными цветами или даже доказательство непротиворечивости ZFC - их можно свести к Машине Тьюринга, а значит этот оракул даст на них ответ. Так что нет, простого анализа потока выполнения и поиска циклов для оракула сильно недостаточно.
это похоже на парадокс брадобрея или парадокс классификаторов.
Так и есть, тут проблема самореференции
Все сводится к тому, что алгоритм H завершится, только если алгоритм H не завершится, в этом и заключается парадокс
у нас в телевизоре в контроллере приемника сигналов от пульта сидит программа, которая сделана чтобы никогда не останавливаться. Она постоянно анализирует сигнал приемника и если распознает его, выполняет операции управления в телевизоре. То что программа не завершается это не обязательно ошибка. Но у Тьюринга таких задач не было, насколько я знаю. Он вроде дешифровкой текстов в основном занимался, которая по определению конечна. А так, учитывая что бесконечная программа это не обязательно ошибка, получается нет смысла проверять ЛЮБУЮ программу что она никогда не закончится, надо различать программы которые действительно выдают результат и завершаются и условно бесконечные программы, которые созданы принимать данные бесконечно и так же бесконечно на них реагировать-обрабатывать эти данные.
Это похоже на разбор открытий тех же древних греков (в философии, и в той же математике, физике, ...), да они были гениальны для своего времени но теперь это школьный уровень.
Даже какой-то нотепад-редактор текстов, у нас в компьютере создан чтобы никогда не завершаться - вы можете редактировать-писать тексты в нем бесконечно, теоретически! Подумайте об этом.
Статья от ИИ и отвечает в комментах ИИ. Дичь.
Похвально, я заметил что это ИИ только через 20 секунд чтения.
По стилю на Gemini похоже ))
Каждая программа состоит из 0 и 1 и имеет "естественный номер" , определяемый этим набором.
Функция f(n) равна 0 , если программа не определена на собственном номере.
А если определена , то N(N) +1 , значение программы в ее "естественном номере" плюс 1.
Такая функция СУЩЕСТВУЕТ для каждой ОС, но не существует АЛГОРИТМА (и программы) для этой функции.
ИМХО такое объяснение проще иллюстрирует границы программируемого, а не "познаваемого". Разницу иллюстрирует тезис Черча о сводимости любой формализации понятия алгоритма к некоему набору функций, тождественному для любой формализации.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Машина, которая никогда не останавливается: как одно предложение поставило предел человеческому познанию