Пару лет назад я написал статью Размышления о структурном программировании, в которой пытался разобраться с заблуждением, будто Эдсгер Дейкстра доказал, что любой алгоритм можно построить всего из трех конструкций (следования, ветвления, цикла). Тогда как на самом деле:
Эту теорему доказали (с условиями и ограничениями) итальянские ученые Бём и Якопини, а Дейкстра лишь ссылался на неё.
Трех указанных базовых алгоритмических конструкций недостаточно для современного программирования (например, требуется обработка исключений).
Знаменитая критика оператора
gotoот Дейкстры (а также оператора присвоения, о чем всегда забывают рассказать) была не строгим запретом, а всего лишь рекомендацией по улучшению стиля кода, чтобы программы было легче анализировать.
А вот теперь настало время написать про некоторые проблемы машины Тьюринга - фундаментальной основы всех информационных технологий.
Зачем?
Поводом для текущей статьи стал мой диалог с одним пользователем на Reddit при обсуждении статьи Гарантии языка программирования как основа безопасной разработки программного обеспечения (там я тоже получаю обратную связь от читателей, как на Хабре, только от англоязычной аудитории).
Мне пытались доказать свою позицию, аргументируя её теоретическими выкладками на основе рассуждений о гипотетической машине Тьюринга, не понимая при этом некоторых её особенностей и ограничений. В результате мне стало очевидно, что, чтобы двигаться дальше, нужно обязательно прояснить и этот момент.
Что не так с машиной Тьюринга?
Машина Тьюринга - это фундамент информатики и теории вычислений, чисто абстрактный исполнитель (математическая модель вычислений), способный имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления.
Каково бы ни было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.
Однако, как и любой математической абстракции, ей присущи некоторые ограничения и допущения, например наличие бесконечной ленты для хранения данных и игнорирование вопросов учета используемых ресурсов (объема памяти и времени выполнения программы), тогда как в реальном мире любой носитель информации конечен, да и время выполнения алгоритма тоже имеет значение, в связи с чем машина Тьюринга определяет теоретическую, а не практическую вычислимость.
Из-за этого машина Тьюринга (а следовательно, и любой компьютер, который мы можем себе представить) не позволяет сделать некоторые вещи:
Решить невычислимые задачи - те, для которых в принципе не существует алгоритма. Неважно, сколько времени или памяти мы дадим машине, она никогда не сможет гарантированно дать правильный ответ для всех возможных входных данных.
Невозможно создать программу, которая проанализирует любую другую программу и её входные данные и скажет, завершится ли эта программа когда-нибудь (остановится) или будет работать вечно (зациклится). Кстати, скорее всего, это и подтверждают слова Э. Дейкстры: «Тестирование выявляет только наличие, но никак не отсутствие ошибок».
Решить NP-трудные задачи за разумное время.
Адекватно моделировать определённые процессы. Машина Тьюринга - это всегда обработка входных данных с последующей остановкой и выдачей результата. Она не предназначена для моделирования постоянно работающих систем, которые взаимодействуют с внешним миром и используют прерывания.
Мысленный эксперимент "Китайская комната", показывает, что машина Тьюринга не позволяет "создать понимание" или "сознание" в человеческом смысле, она лишь симулирует его внешние проявления.
Конечно, все это не умаляет значимости машины Тьюринга, и её простота - это её сила, которая позволяет строго доказывать фундаментальные теоремы о возможностях и границах вычислений.
Если вам интересна эта тема, рекомендую почитать Surprisingly Turing-Complete · Gwern.net или её перевод Неожиданная полнота по Тьюрингу повсюду - Хабр.
Причём тут машина Тьюринга?
В контексте предыдущей статьи о Гарантиях языка программирования как основы безопасной разработки программного обеспечения, свойства Тьюринг-полных языков программирования позволяют сделать следующие выводы:
Любой язык программирования, обеспечивающий гарантии безопасной разработки обязан ограничивать возможности реализации некоторых алгоритмов (как минимум таких, которые содержат ошибки), а это означает, что любой безопасный язык программирования не может быть Тьюринг-полным по определению (раз на нем нельзя написать программу с ошибкой).
Интересен и обратный вывод: полнота языка программирования по Тьюрингу является достаточным основанием, чтобы такой язык программирования нельзя было отнести к безопасным :-)
Комментарии (26)
ramiil
15.11.2025 14:26Тут надо смотреть в сторону тотальных ящыков программирования. Они, например, запрещают зацикливание программы
skthn
15.11.2025 14:26Как-то очень сумбурно.
Китайская комната — это совсем не про то. Машина Тьюринга теоретически может эмулировать головной мозг человека во всех деталях, и тогда там будет сознание.
Любой алгоритм может считаться ошибочным только применительно к конкретной задаче. Если взять корректный алгоритм и его испортить, то он всё равно будет решать какую-то задачу, только другую. Таким образом, вам заранее придётся решить какой круг задач ваш язык позволит решать, а какой нет. Это примерно то же самое, что вы написали в статье (неполнота по Тьюрингу), только немного с другой стороны с акцентом на том, что кто-то должен заранее определить множество решаемых задач. А раз это делает человек, то определять этот круг придётся каким-то явным образом. А раз так, то никто не мешает вместо этого просто написать функции, которые будут решать эти задачи, а раз так, то тут не нужен и язык, можно просто написать библиотеку для любого из существующих языков. Короче, идея получается совсем нелепая.
rsashka Автор
15.11.2025 14:26Китайская комната — это совсем не про то. Машина Тьюринга теоретически может эмулировать головной мозг человека во всех деталях, и тогда там будет сознание.
Китайская комната, это только внешняя эмуляция разума, тогда как классическая Машина Тьюринга даже в теории не может эмулировать головной мозг человека во всех деталях, так как она строго последовательная и не не может обработывать только статическую информацию с бесконечной ленты, тогда как мозг работает параллельно, он постоянно обработывает внешнюю информацию и не останавливается, когда завершает решение очередной задачи.
Любой алгоритм может считаться ошибочным только применительно к конкретной задаче ...
Вы не правильно рассуждаете. Например классический алгоритм с циклическими ссылками, который приводит к утечкам оперативной памяти или алгоритм деления двух чисел с делением на ноль. И тот и другой являются алгоритмами исполнимыми на Машине Тьюринга, но безопасный язык программирования не должен их реализовывать (может, но не должен). Вот это "не должен" как раз и является не полнотой по Тьюрингу.
А так да, именно человек должен ограничивать допустимость реализации тех или иных алгоритмов. И вы правы, что новый язык не нужен. Можно взять уже существующий полный по Тьюрингу (например С++), и сделать для него анализатор кода, реализующий те или иные ограничения.
vadimr
15.11.2025 14:26На мой взгляд, мысленный эксперимент с Китайской комнатой доказывает только то, что он некорректно сформулирован: не доказано, что задача построения колоды карт конструктивно разрешима. В общем это похоже на наивную теорию множеств.
Olorin111
15.11.2025 14:26Забавно, что обратил внимание на ваш комментарий уже после написания своего. Полностью согласен. Более того, со временем и развитием ИИ мне все больше кажется, что даже тезиз проблемы остановки, приводимый и доказываемый Пенроузом через интерпретацию по Черчу неполноты по Геделю, кроет в себе не менее коварные софизмы, так как с динамической индексацией , к аналогу которой можно свести нейросеть доказательство уже далеко не столь очевидно.
Anarchist
15.11.2025 14:26Обработка исключений не обязательна, её современные языки программирования стараются избегать. И по сути она является синтаксическим сахаром над тремя основными операциями.
rsashka Автор
15.11.2025 14:26Обработка прерывания являются обязательной и она в том или ином виде присутствует во всех языках, даже тех, какие стараются ион нее избавится, и смена названия сути не меняет.
Olorin111
15.11.2025 14:26Последний ваш тезис о китайской комнате Серля вообще не очень понятен в данном контексте. Естественно у машины Тьюринга есть ряд ограничений, и все тезисы кроме последнего вполне уместны. Однако каким образом можно заявлять о наличии или отсутствии сознания даже не имея термина, определяющего его? Софизм комнаты Серля в том, что человек перебирающий символы - не более чем аналог нейрона у нас в мозгу. Вы-же не станете считать его разумным? Я хотел вместо нейрона сказать о нейронном блоке, но пожалуй не стану. Здесь уже скорее всего у вас появится возможность меня подловить. В свою-же очередь о том, чем в таком случае является сама комната почему-то редко задумываются, тем не менее наделив ее свойствами с очевидностью выходящими за рамки ограничений машины Тьюринга, упомянутых вами в предыдущих тезисах.
vadimr
15.11.2025 14:26Серль подразумевает, что разуму комнаты негде получить субстрат, кроме разума мужичка и примитивной колоды карт. Однако выводимое за скобки рассмотрения наличие сверхразума, по условию способного напечатать колоду, равномощную всем потенциальным когнитивным возможностям человека, существенно меняет дело. Этот гипотетический сверхразум и есть субстрат сознания, отделивший в колоду синтаксис от семантики (если это вообще возможно).
Всё это некоторым образом перекликается с идеями профессора Чжана об ИИ 3 поколения.
rukhi7
15.11.2025 14:26Размышления о машине Тьюринга и причинах возникновения ошибок в языках программирования
Интересно было бы посмотреть пример какой-нибудь "ошибки в языке программирования", а то как то не очень понятно к чему все эти высокоумные рассуждения относятся.
rsashka Автор
15.11.2025 14:26x / 0
rukhi7
15.11.2025 14:26а где здесь язык программирования? По моему это ошибка в вычислениях, причем не в этой записи даже, а в том как вы дошли до этой записи, то есть на самом деле ошибки мы не видим.
Вообще говоря если вашу запись интерпретировать как строку в ней вообще нет никакой ошибки: да, получилось что надо икс поделить на ноль, вполне возможно, что это один из корректных результатов некоторой логики, результатом действительно является бесконечность.
Что с точки зрения языка здесь является ошибкой:
наличие нуля или наличие самой операции деления или ограниченность разрядности реального-физического вычислителя?
То есть что из этого надо запретить в языке программирования?
rsashka Автор
15.11.2025 14:26Вы правы и тут нет противоречия.
Я привел пример ошибки в языке программирования, так как в классических ЯП деление на ноль, это именно ошибка, но для машины Тьюринга алгоритм деления чисел, это точно такой же алгоритм, как и любой другой.
Именно поэтому и возникает описанная в статье особенность, когда сужается список допустимых к реализации (выполнению) алгоритмов. Т.е. их реализовать можно и они выполнимы, но фактически запрещены на уровне синтаксиса, что и приводит такой ЯП к не полноте по Тьюрингу.
redbeardster
15.11.2025 14:26Можно попробовать заюзать чего с зависимыми и уточненными типами - вдруг полегчает. F* там или Агду
rukhi7
15.11.2025 14:26но для машины Тьюринга алгоритм деления чисел
какой, на фик, алгоритм, деления чисел? При чем здесь, на фик, машины Тьюринга?
Деление это элементарная арифметическая операция, использованию которой учат во втором классе! И тогда же учат тому, что делить на ноль нельзя, при чем здесь программирование?
Если вы написали:"Казнить нельзя помиловать!" это тоже ошибка русского языка, что вы запятую забыли поставить? Или это ошибка языка что в языке есть слова обозначающие противоречивые операции?
vadimr
15.11.2025 14:26Деление в арифметике и в компьютере – разные вещи.
Коллега, как я его понимаю, пишет как раз о том, что семантика, которой человек наделяет операцию деления, не соответствует синтаксической операции, которую компьютер (мТ) фактически здесь производит над цепочками битов. И это святая правда.
Но проблема тут в том, что семантика вообще не имеет однозначного выражения в синтаксисе ни одного известного нам языка, а имеет только приближенные интерпретации (или, наоборот, сама является приближенной интерпретацией некоторого синтаксиса).
Когда мы хакнем человеческий мозг и расшифруем язык сигналов в нейронах, то, вероятно, синтаксис этого языка будет соответствовать семантике в пределах отдельно взятого экземпляра мозга. Поэтому в принципе задача разрешима (если нет божественной одухотворяющей мозг души). Но известных решений нет.
Sirion
Есть ощущение, что вы путаете тёплое с мягким. Тьюринг-полнота - это про вычисления, а безопасность - это, как правило, про изменение состояния.
rsashka Автор
Про вычисления речь не идет вообще, так как машина Тьюринга, это еще и возможность записи этой самой программы (на бесконечной ленте), тогда как гарантия безопасной разработки на уровне синтаксиса языка программирования, это невозможность записать не безопасный код.
Sirion
Когда оценивают тьюринг-полновость языков, не оценивают их способность записать данные в произвольную область памяти. Имеется в виду их способность решать те же вычислительные задачи (производить нужный аутпут из заданного инпута). Вы можете ввести свои определения, но стоит их вынести в отдельный неймспейс
rsashka Автор
Зачем мне "свои определения", когда достаточно уже имеющихся.
Sirion
Затем, что ваши определения противоречат имеющимся.