Арсенал ненасытного педанта

Я слышал, что термин «полнота Тьюринга» используется гораздо чаще в разработке программного обеспечения, чем я ожидал. Я думаю, что есть небольшая путаница в том, что означает Turing Complete, особенно в контексте разработки программного обеспечения.

Мы говорим, что полнота по Тьюрингу - это свойство вычислительной системы, которое утверждает, что система обладает такой же вычислительной мощностью, как машина Тьюринга. Но что ИМЕННО это означает? Наденьте акваланг и гидрокостюм, потому что мы глубоко погружаемся в формализм:

Машины Тьюринга

Машины Тьюринга - это теоретические компьютеры, определенные Аланом Тьюрингом в его очень влиятельной статье под названием О вычислимых числах в приложении к проблеме Entscheidungsproblem, опубликованной в 1936 году. Машины Тьюринга - это абстрактные математические конструкции, которые помогают нам описывать в строго определите то, что мы подразумеваем под вычислением.

Существует бесчисленное множество подробных руководств о том, как работает машина Тьюринга, и вы можете посмотреть любое из них! Я могу в значительной степени гарантировать, что они лучше меня объяснят, как работает машина Тьюринга, но если вы не хотите смотреть что-либо из них, я также добавлю свое описание.

Машина Тьюринга состоит из двух элементов: вычислительной головы и бесконечно длинной ленты. Головка работает примерно как головка «чтения-записи» на дисководе, а лента разделена на бесконечно длинный набор квадратов, для которых на каждом квадрате можно написать или стереть символ. Машина Тьюринга распознает и может записать конечный набор символов, называемый алфавитом машины Тьюринга.

Машина Тьюринга «осведомлена» только об одном квадрате на ленте, а именно о квадрате, на котором сейчас находится голова машины Тьюринга.

На этой ленте машина Тьюринга может выполнять любое из этих 4 действий:

  • Сдвинуть голову влево на 1 деление
  • Сдвинуть голову вправо на 1 деление
  • Напишите символ в голове
  • Сотрите символ на голове

Машина решает, какую из этих операций выполнять на любом заданном шаге через конечный автомат. У разных машин Тьюринга разные конечные автоматы, которые определяют их работу.

Конечный автомат состоит из конечного числа состояний (которые Тьюринг называет конфигурациями m-), между которыми он переключается на каждой итерации. Устройство может одновременно находиться только в одном состоянии, но переключается между ними в зависимости от текущего состояния и символа, который машина в данный момент сканирует. Машина Тьюринга берет текущее состояние и символ и находит, что делать, в большой таблице.

Машина Тьюринга также имеет набор состояний принятия, которые говорят машине Тьюринга о прекращении выполнения. Если машина Тьюринга входит в любое из этих состояний принятия, говорят, что машина останавливает и приостанавливает выполнение навсегда. Вот и все, что касается машин Тьюринга!

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

Давайте построим машину Тьюринга, которая никогда не останавливается с диаграммой состояний!

Мы начнем с создания очень простой машины Тьюринга с алфавитом {0, 1}. Мы начинаем с состояния S1 и решаем, что делать. Для любого символа (обозначенного *) на ленте машина Тьюринга записывает символ 1, перемещает на один пробел вправо и переключается на S2. Теперь в состоянии S2 для любого символа на ленте машина записывает 0 и перемещается на одну позицию вправо, переключаясь на S1. Вернувшись в S1, цикл повторяется, продолжаясь бесконечно. Как вы могли догадаться, это записывает 1010101 […] в бесконечном цикле. У машины нет состояний принятия, поэтому она никогда не остановится.

Что ж, это было захватывающе.

Описание номеров

Оказывается, мы можем однозначно пронумеровать все машины Тьюринга. Машину Тьюринга, удваивающую число, можно пронумеровать:

31332531173113353111731113322531111731111335317

в то время как тот, который утроил числа, может быть пронумерован как-нибудь иначе:

3133253117311335311173111332253111173111133531731323253117

Как вы понимаете, это огромные и до странности повторяющиеся числа, но, тем не менее, это числа.

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

Спойлеры: мы передадим номер описания машины Тьюринга в качестве входных данных для другой машины Тьюринга позже, но забудем, что вы что-нибудь слышали ...

… Как способ вычисления функций

Машины Тьюринга прекрасны, и все они представляют собой маленькие игрушечные компьютеры, но мы действительно хотим использовать их для определения функций. Тьюринг был математиком, и он заботился об определении набора чисел, называемых вычислимыми числами, и для этого он предложил машины Тьюринга.

В частности, мы хотим превратить машины Тьюринга в частичные функции, для которых могут быть неопределенные выходные данные. Мы хотим, чтобы эти функции были ℕ⁽ⁿ⁾ → ℕ, что означает, что они принимают любое число n натуральных чисел в качестве входных данных и выводят одно натуральное число (или не определены для этого ввода, поскольку они являются частичными. ).

Все, что нам нужно сделать, чтобы превратить машину Тьюринга в частичную функцию , - это оснастить ее схемой ввода и вывода. Сам Тьюринг не предлагает однозначного «входного» формата, но по мере того, как мы переходим к языкам программирования, будет полезно сделать этот шаг определения входных и выходных данных явным. Я выбираю монадическую нотацию, как указано в разделе Вычислимость и логика .¹

Precise Formulation
(a) The arguments m1...mk of the function will be represented in monadic notation by blocks of those numbers of strokes, each separated from the next by a single blank, on an otherwise blank tape. Thus at the beginning of the computation of, say, 3 + 2, the tape will look like this: 111B11
(b) Initially, the machine will be scanning the leftmost 1 on the tape, and will be in its initial state, state 1. Thus in the computation of 3 + 2, the initial configuration will be 1₁11B11. A configuration as described by (a) and (b) is called a standard initial configuration.
(c) If the function that is to be computed assigns a value n to the arguments that are represented initially on the tape, then the machine will eventually halt on a tape containing a block of that number of strokes, and otherwise blank. Thus in the computation of 3+2, the tape will look like this: 11111.
(d) In this case, the machine will halt scanning the leftmost 1 on the tape. Thus in the computation of 3 + 2, the final configuration will be 1ₐ1111, where the ath state is one for which there is no instruction what to do if scanning a stroke, so that in this configuration the machine will be halted. A configuration as described by (c) and (d) is called a standard final configuration (or position)
(e) If the function that is to be computed assigns no value to the arguments that are represented initially on the tape, then the machine will either never halt, or halt in some nonstandard configuration such as Bₐ11111 or B111ₐ11 or B11111ₐ.

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

Точное определение, которое мы выбираем для ввода и вывода, не так важно: пока перевод между различными форматами ввода и вывода вычислим (что почти наверняка так и есть для любого разумного определения), мы получим эквивалентный набор вычислимых функций.

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

Вычислимые числа

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

Вычислимое число a - это число, для которого существует некоторая вычислимая функция f такая, что f (n) дает nth цифра а.

Ой, Википедия говорит мне, что это не совсем так. Давай поменяем местами:

Вычислимое число a - это число, для которого существует некоторая вычислимая функция f такая, что f (n) удовлетворяет одному странному неравенству.

Интуитивный смысл в любом случае один и тот же: если вы можете вычислить число с произвольной точностью, это число вычислимо.

Оказывается, вычислим целый ряд чисел. Вот быстрый вкус:

  • Все рациональные числа
  • e
  • π
  • φ
  • Любая вычислимая функция любого вычислимого числа
  • На самом деле, почти каждое число, которое вы можете придумать,

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

Универсальная машина Тьюринга

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

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

Невычислимость

Поскольку термин вычислимые функции подразумевает , существуют также невычислимые функции:, которые мы можем определить, для которых не может существовать никакая машина Тьюринга.

И, несмотря на то, что их сложно построить, существует МНОГО невычислимых функций. На самом деле почти все функции невычислимы. Просто существует намного больше возможных функций, чем когда-либо могло быть машин Тьюринга, поэтому должны быть некоторые из них, которые машины Тьюринга упускают. На математическом языке множество машин Тьюринга счетно, тогда как множество действительных чисел несчетно велико.

Каноническая невычислимая функция, предложенная Мартином Дэвисом (с аналогичной проблемой в оригинальной статье Тьюринга), является проблемой остановки. Проблема может быть сформулирована очень просто:

Проблема с остановкой: Имеет ли компьютерная программа и ввод для указанной программы, завершает ли эта программа когда-либо выполнение?

Легко представить себе примеры программ, в которых можно определить, завершается программа или нет: если состояние в точности повторяется или программа немедленно останавливается, легко определить, остановятся ли эти программы. Но попробуйте придумать алгоритм решения для ЛЮБОЙ программы, и вы обнаружите, что проблема становится невероятно сложной, в буквальном смысле.

Дэвис доказывает, что эта функция невычислима, что не может существовать никакая машина Тьюринга, которая могла бы вычислить правильный ответ. Поскольку эта конкретная проблема дает ответ да / нет, она считается проблемой принятия решения, а поскольку она не поддается вычислению, проблема считается неразрешимой.

Вы можете получить больше информации о невычислимости из этого очаровательно полезного сообщения сообщества Buzzfeed.

… Как первоначально построено Тьюрингом

Вот что я подумал, когда впервые прочитал статью Тьюринга: « О, это будет совсем легко, не так ли? Мы просто сопоставляем терминологию в современном определении, которое мы только что выучили, с оригинальной терминологией Тьюринга! Это будет простое отображение, верно?

Я имею в виду, просто посмотрите на термин без круга! Без кругов легко, он достигает своего конечного состояния за конечный промежуток времени, как предлагают многие объяснения в оригинальной статье Тьюринга в Интернете! Вы только посмотрите на дефи ...

Если вычислительная машина никогда не записывает более конечного числа [символов 1 и 0], она будет называться круговой. В противном случае говорят, что он не содержит кругов.

[…]

Последовательность называется вычислимой, если ее можно вычислить на машине без окружностей. Число является вычислимым, если оно отличается на целое число от числа, вычисленного машиной без окружностей.

Подождите, это кажется обратным. Машина, которая печатает бесконечное число 1 и 0, никогда не останавливаясь, вычисляет вычислимые числа? Разве это не противоречит тому, как мы обрисовали это ранее, когда only определенный вывод был, когда машина Тьюринга остановилась в стандартной конфигурации? »

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

Вычислимые последовательности

Фактически, Тьюринг в первую очередь сосредоточился на идее вычислимых последовательностей, которые мы вскоре будем использовать для определения вычислимых чисел.

Мы можем взглянуть на эту неизменяющуюся машину Тьюринга, которую мы сконструировали ранее: на пустой ленте она печатает 10101010101…. Поскольку это было сделано машиной Тьюринга, которая в итоге распечатала бесконечное количество 1 и 0 с, Тьюринг счел бы это вычислимой последовательностью.

Согласно первоначальной конструкции Тьюринга, такие бесконечные последовательности - это именно то, к чему мы стремимся - мы хотим распечатать связку 1 и 0 во веки веков. Мы бы назвали машины Тьюринга, которые в конечном итоге печатают бесконечную последовательность, подобную этой без кругов, и все остальное круговой.

От вычислимых последовательностей к вычислимым числам

Точно так же, как у нас есть десятичные дроби в базе 10, мы можем иметь десятичные дроби и в базе 2! Они не называются десятичными, а скорее двоичными дробями, но работают практически одинаково, за исключением оснований 2, а не 10. Например, число 0,75, преобразованное в двоичное, становится 0.11 или 2,8125, преобразованное в двоичное, становится 10.1101. Точное преобразование десятичных и двоичных дробей не имеет особого значения, но вы можете посмотреть учебник, если хотите действительно.

Мы можем интерпретировать вычислимую последовательность как дробную часть двоичного числа. Таким образом, последовательность 101010… станет 0.101010…, что даст нам число, с которым мы будем работать. Все, что отличается от этого дробного компонента на целое число, само по себе вычислимо.

Оказывается, множество вычислимых чисел, определенных современной конструкцией и конструкцией Тьюринга, одинаковы!

Но… зачем тогда современное строительство?

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

Быстрое раздражение

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

Если из этой статьи вы ничего не догадались, поймите: педантизм в отношении определений машины Тьюринга не приведет вас очень далеко. Обычно это не делает вас более правильным с математической точки зрения. Большинство разумных определений исходного определения Тьюринга будут эквивалентны. Если мы не решаем проблемы в рамках конкретной области вычислимости, нам не следует спорить об этом в каком-либо значимом качестве - это того не стоит.

Эквивалентность другим вычислительным системам

Итак, как я упоминал ранее, существует достаточное количество эквивалентных моделей машин Тьюринга. Погуглите, сколько душе угодно.

  • Машины Пост-Тьюринга
  • Многоленточные машины Тьюринга

А также эквивалентные модели, не являющиеся машинами Тьюринга:

  • μ-рекурсивные функции
  • Нетипизированное лямбда-исчисление
  • OISC, очень минималистичные компьютеры с одной инструкцией.
  • Игра жизни Конвея
  • Большинство языков программирования
  • Счеты (с несколькими простыми правилами)
  • Ведра и камни (с несколькими простыми правилами)
  • Какую бы систему ни подразумевал Рэндалл Манро под этим

Мы можем доказать, что в каждом из этих случаев эти вычислительные системы могут вычислять тот же набор функций, что и любые другие. И, черт возьми, это много разных систем, эквивалентных Тьюрингу. Abaci, рекурсивные функции, лямбда-исчисление, куча камней? Все они в точности эквивалентны? Ха, странно ...

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

Языки программирования как завершенные по Тьюрингу

Интуитивно языки программирования могут быть полными по Тьюрингу. Посмотрим, сможем ли мы формализовать это понятие.

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

Чтобы быстро понять, насколько просто я думаю, мы сделаем небольшой пример для javascript:

If a javascript program exposes a function named run() which, when executed with a primitive integer as the first argument, returns either an integer or undefined, the output is the return value. Otherwise the output is undefined.

Я вернусь к этому определению позже, а сейчас просто отметим, что это одно из многих возможных определений, которые мы могли бы выбрать.

Ограниченность

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

Ни одна программа, запущенная на компьютере, не будет полностью завершена по Тьюрингу; существует предел. Ни один компьютер никогда не сможет вычислить Число Грэма * 2, никогда - во Вселенной просто недостаточно места для такого большого компьютера. Тем не менее, для машины Тьюринга, которая удваивает числа, практическая ограниченность Вселенной не является проблемой. Машина Тьюринга так же способна вычислять число Грэма * 2, как и вычислять 2 * 2, для этого требуется всего лишь несколько шагов. Этот пробел означает, что компьютеры реального мира не могут вычислять функции, вычисляемые по Тьюрингу, для всех входных данных и, следовательно, не являются полными по Тьюрингу.

Так что они?

У нас есть отдельное название для них - они не совсем эквивалентны полноценным машинам Тьюринга, но они могут делать все, что может машина Тьюринга, до определенного предела. Это называется Линейно-ограниченная автоматизация. Линейно-ограниченная автоматизация почти идентична машинам Тьюринга, за исключением того, что они накладывают левую и правую границу на ленту.

Итак, если компьютеры не полностью завершены по Тьюрингу, как может язык программирования, работающий на компьютере, когда-либо надеяться быть завершенным по Тьюрингу?

Уловка в том, что языки не обязательно подразумевают ограничения в рамках своих спецификаций, а вместо этого переносят эту проблему на более низкий уровень. Язык может быть либо полным по Тьюрингу, либо неполным по Тьюрингу, основываясь исключительно на его спецификации и независимо от какой-либо реализации на реальном компьютере. Разница может быть более тонкой, чем вы думаете, что я могу продемонстрировать с помощью Brainfuck.²

Давайте сравним две различные распространенные интерпретации байтового указателя в Brainfuck:

Original Definition
A Brainfuck program has an implicit byte pointer, called “the pointer”, which is free to move around within an array of 30000 bytes, initially all set to zero. The pointer itself is initialized to point to the beginning of this array.
Modified Definition
A Brainfuck program has an implicit byte pointer, called “the pointer”, which is free to move around within an infinite array, initially all set to zero. The pointer itself is initialized to point to the beginning of this array.

Найди отличие? Это то, что привязано к длине ленты. В первом случае сам язык имеет конечную границу, что делает его эквивалентным линейно связанным автоматам, независимым от какой-либо машины, на которой он работает. На теоретическом компьютере без ограничений функции, выражаемые исходным определением, НЕ являются полными по Тьюрингу.

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

Поэтому, когда кто-то говорит, что «язык [x] является полным по Тьюрингу» и не доказывает, что сам язык теоретически может поддерживать неограниченную память, вы можете перехитрить его и сказать, что вы не поверите им, пока они не покажут, что это так!

… Кстати говоря, давайте вернемся к определению ввода и вывода, которое мы выбрали для Javascript. Мы проверим работоспособность, чтобы увидеть, допускают ли наши вводимые и выводимые данные ЛЮБОЕ число размера, вплоть до числа Грэма и выше. Вот что мы изложили ранее:

If a javascript program exposes a function named run() which, when executed with a primitive integer as the first argument, returns either an integer or undefined, the output is the return value. Otherwise the output is undefined.

Так работает ли это с невероятно огромными числами, такими как число Грэма? К сожалению нет. В Javascript примитивные целые числа гарантируются только с точностью до 2⁵³, поэтому похоже, что этой конкретной схемы ввода / вывода было недостаточно.

Создание схемы ввода / вывода для Javascript

Итак, какая схема ввода / вывода будет жизнеспособной? Можем ли мы использовать строки для представления бесконечных данных? "Уже нет". Можем ли мы использовать очень большие унарные массивы для представления чисел? "К сожалению нет".

Давайте перейдем к другой структуре данных, от примитивов для ввода, и рассмотрим вместо этого связанный список различных объектов в JS. Помните, мы просто ищем эффективный способ представления натуральных чисел:

// null wrapped 3 times represents the number 3
{ next: { next: { next: null }}}

Эта схема должна работать⁴. Единственное ограничение того, насколько глубоко эта структура может быть вложенной, - это ограничения в самом интерпретаторе и компьютере, а не в спецификации. Что касается спецификации Javascript, мы можем представлять числа величиной с число Грэма, используя этот рекурсивный шаблон.

Означает ли это, что Javascript завершен по Тьюрингу? Мы не должны делать поспешных выводов слишком рано: может быть некоторая критическая преграда для обработки чрезвычайно больших рекурсивных структур, но для JavaScript я сомневаюсь, что есть такая преграда.

Гипервычисления на языках программирования

Возможность определять нереализуемые процессы имеет интересное значение: спецификация языка программирования не обязательно должна быть ограничена вычислимостью. То есть сам язык программирования может быть определен как полный супер-Тьюринг, способный вычислять то, чего машина Тьюринга никогда не могла.

Например, представьте себе что-то под названием JS-Hyper. JS-Hyper эквивалентен JS с добавлением новой встроенной функции willHalt (dn, args), где willHalt - это оракул, определяющий, с номером описания dn остановится для аргументов args. Поскольку машина Тьюринга не может вычислить эту функцию, JS-Hyper является полным по Супер-Тьюрингу.

Это служит демонстрацией того, что, хотя мы ожидаем, что компьютеры смогут исполнять языки программирования, ничто не мешает нам определить язык программирования, не ограниченный такими глупыми понятиями, как вычислимость. Мы можем делать все, что захотим! Сила наша! Ха-ха!

Тезис Черча-Тьюринга

Почему мы должны так заботиться об этом странном наборе функций, называемых вычислимыми функциями? Почему имеет смысл называть этот набор функций вычислимыми?

Тьюринг и Алонзо Черч утверждают, что люди связаны этими правилами точно так же, как и машины; что любой процесс, который человек может использовать для вычисления числа, может также выполняться компьютером, и наоборот. Тезис Черча-Тьюринга, по сути, утверждает, что люди (по крайней мере в вычислительном отношении) эквивалентны Тьюрингу.

Тьюринг называет числа, которые люди могут вычислить алгоритмически за конечное время, эффективно вычисляемыми числами. По сути, эффективно вычисляемые числа - это все числа, которые мы когда-либо надеялись вычислить - любое число, в котором мы можем придумать способ вычисления этого числа, считается эффективно вычисляемым.

Мы можем переформулировать тезис Черча-Тьюринга на этом языке, получив:

Тезис Черча-Тьюринга: Наборы эффективно вычислимых чисел и вычислимых чисел эквивалентны.

Выглядит почти официально, не правда ли?

И вдали от строгости

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

Аргумент Тьюринга предоставляет три доказательства в пользу эквивалентности эффективно вычислимых чисел и вычислимых чисел.

Аргументы, которые я буду использовать, бывают трех видов.
(а) Прямое обращение к интуиции.
(b) Доказательство эквивалентности двух определений (в случае, если новое определение имеет большую интуитивную привлекательность).
(c) Приведение примеров вычислимых больших классов чисел.

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

По сути, Тьюринг утверждает, что процесс, который компьютер (как в старой школе человеческого занятия) выполняет для вычисления числа, по существу сводится к бесконечной ленте, соединенной с конечным автоматом. Человек может одновременно сосредотачиваться только на конечном числе символов, а человек имеет только конечное число возможных состояний головы (из-за конечного числа нейронов). Учитывая, что определенное состояние головы определяет, какое действие вы предпримете дальше, вы можете представить себе массивную, массивную таблицу переходов, охватывающую все возможные мысленные переходы.

Очевидно, это очень грубый набросок аргумента. Но, по крайней мере, вы можете увидеть, как сочетание бесконечного количества бумаги и ограниченных умственных способностей намекает на тезис Черча-Тьюринга.

Более широкие последствия

Что так интересно с философской точки зрения в тезисе Черча-Тьюринга, так это то, что он указывает на полноту Тьюринга как на «оно» в определенном смысле. Это указывает на то, что никакая детерминированная система не может вычислить больше, чем может вычислить машина Тьюринга. В этом смысле невычислимый означает не только невычислимый для машин Тьюринга, но и для ЛЮБОГО типа детерминированной машины.

Учитывая, сколько систем эквивалентно Тьюрингу, насколько простой может быть система, чтобы быть эквивалентом Тьюринга, и насколько распространена эквивалентность Тьюринга, имеет ли смысл думать о полноте Тьюринга в терминах машин Тьюринга? Может быть, прагматично, но, на мой взгляд, эти машины не должны составлять сущность вычислимости Тьюринга, а просто источник вычислимости Тьюринга.

Для меня мысль об эквивалентности по Тьюрингу как о неразрывной связи с машинами Тьюринга как бы обесценивает фундаментальность вычислимых чисел и вычислимых функций. Этот набор функций имеет глубокое математическое и философское значение отдельно от того, как мы их определили; Машины Тьюринга просто оказались тем способом, которым мы научились понимать, что они из себя представляют. Я думаю, это действительно круто.

Решение неисчислимого

Можем ли мы выйти за рамки этих ограничений? Какие инструменты у нас есть против бесчисленного множества неисчислимых чисел? У вас может возникнуть соблазн подумать, что компьютер не может вычислить что-либо невычислимое - я имею в виду, это именно то, что утверждает Тьюринг!

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

В разработке программного обеспечения мы решаем такие подзадачи постоянно. На самом деле очень часто мы можем не осознавать, что делаем. Например, завершается ли когда-либо выполнение этой JS-программы?

function run(){
  for(let i = 0; i !== -1; i++);
}

Ответ: «Нет, конечно, нет. i никогда не будет равно -1 ,, поэтому эта программа будет работать вечно ». Что ж, вы только что выполнили небольшую подзадачу большой и неразрешимой задачи остановки, и это было даже не сложно! Ура!

Компиляторы сильно автоматизируют этот процесс, решая, недоступен ли код, останутся ли когда-нибудь определенные подпрограммы и т. Д. И т. Д. По сути, компиляторы решают проблему остановки в определенных случаях, как мы это делали выше. Если мы расширим рассуждения такого рода, мы сможем охватить несколько довольно сложных примеров.

Гипервычисления

Однако существует область исследований, называемая гиперкомпьютерами, которая занимается вычислением невычислимых чисел. Как настоящие, реальные, очевидные, неисчислимые числа в реальном мире. Гипервычисление как предмет требует либо:

  1. Что тезис Черча-Тьюринга ложен, так что существует некий механический процесс, который люди могут использовать для вычисления чисел, которые не могут быть выполнены компьютерами.
  2. Что тезис Черча-Тьюринга фундаментально слабее общепринятой интерпретации, так что существуют функции, которые машины могут вычислить, которые люди не могут (учитывая бесконечное время и пространство).
  3. Что существуют физически реализуемые невычислимые числа, например, есть случаи, когда мы можем измерить невычислимые числа физически, а не вычислить их.

С философской точки зрения, если что-то из этого верно, то это говорит о очень глубоком понимании природы вселенной: вселенная явно НЕ работает как машина Тьюринга. Это может быть действительно интересно узнать.

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

Это противоречие привело к появлению одной из лучших строк в академических кругах, написанной Дэвисом в Vol. 178 из прикладной математики и вычислений:

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

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

Это поле существует? Расскажите нам, что вы думаете, в разделе комментариев ниже. Не забывайте оценивать, комментировать и подписываться на больше подобных видео!

Полезны ли знания о вычислимости по Тьюрингу в разработке программного обеспечения?

Много говорят о том, что языки являются полными по Тьюрингу. Я не думаю, что это очень полезное соображение по нескольким причинам:

  • Это не высокая планка. Вы не стали бы дифференцировать язык программирования как полный по Тьюрингу, учитывая, что практически любой другой язык программирования, для которого имеет значение полнота по Тьюрингу, сам по себе является полным по Тьюрингу.
  • Является ли язык полностью полным по Тьюрингу или линейно ограниченным - не очень полезное различие, потому что мы запускаем наши программы на компьютерах конечного размера и скорости, а не в безграничной логической сфере математики, и большинство ограничений, определенных языком быть достаточно большим для любых целей.
  • Полнота по Тьюрингу не делает язык полезным. Я упоминал ранее, что Brainfuck - это законченный по Тьюрингу, но это не значит, что я собираюсь рассматривать его для какого-либо серьезного проекта. Говорят, что языки из этой категории попадают в тарпит Тьюринга.
  • Неполнота по Тьюрингу также не делает язык бесполезным. Если HTML оказывается неполным по Тьюрингу, это не делает HTML менее полезным: это инструмент для определения структуры документа. Он не обязательно должен быть полным по Тьюрингу.

Так что, если это когда-либо полезно в спорах о программной инженерии, в лучшем случае оно редко бывает полезным. Любой аргумент в разработке программного обеспечения, основанный на полноте Тьюринга, либо неправильно понимает полноту Тьюринга, либо формирует особенно слабое утверждение.

К счастью, людей не волнует только сиюминутная полезность информации. Это было бы довольно неприятно.

Эта статья окончена?

да.

Источники включают Вычислимость и логику, Аннотированный Тьюринг, множество Википедии, все упомянутые статьи (и несколько других, которые давно ушли в историю моего браузера), различные сообщения в блогах, разговоры о вычислимости с друзьями, несколько моих собственных аргументы и, надеюсь, комментарии от таких зрителей, как вы. Спасибо.

Если я ошибаюсь в НИЧЕГО, независимо от того, насколько педантичен, не стесняйтесь комментировать и объяснять мне, почему. У меня нет формального опыта в теории вычислений, поэтому очень вероятно, что я здесь что-то не так, просто надеясь, что это не было чем-то слишком серьезным.

Сноски

(1): Определение, которое я решил использовать здесь, лишь минимально отличается от описания частичной функции Клини и Мартина, которое требует дополнительного подсчета для каждого ввода, так что ввод 3 будет закодирован 1111, а не 111. Я не уверен, почему Вычислимость и логика решили отклониться от этого, но это не очень важная разница.

(2): Если вы раньше не сталкивались с Brainfuck и вы достаточно большой ботаник, чтобы зайти так далеко в статью о полноте Тьюринга, вас ждет удовольствие: это забавно минималистичное и сложное в использовании программирование. язык. Серьезно, попробуйте!)

(3) Я считаю, что это определение неявно используется в Brainfuck is Turing Complete.

(4) Было бы удобнее использовать вложенные массивы, такие как [] для представления 0, [[]] для представления 1 и т. Д. И т. Д. Я думал, что объекты лучше передают природу.

(5) В этом случае мы можем интуитивно догадаться, почему у нас, вероятно, нет такой проблемы. Помните нетипизированное лямбда-исчисление, о котором я упоминал ранее? Он использует рекурсивную структуру для представления унарных чисел очень похожим образом, и можно легко определить перевод между приведенным выше представлением связанного списка и числами Чёрча, которые использует нетипизированное лямбда-исчисление. Поскольку операции с лямбда-исчислением определяются рекурсивно, и (я не думаю) существует какой-либо определенный спецификацией предел глубины рекурсии, этого формата должно быть достаточно. Javascript почти наверняка завершен по Тьюрингу.

(6) Мне кажется, что наше более свободное понимание «Является ли эта система полной по Тьюрингу?» Неявно спрашивает: «Существует ли такая стратегия ввода / вывода, что результирующая система является полной по Тьюрингу?» Я не собираюсь углубляться в эту проблему, потому что это открывает банку червей с точки зрения «а что же определяет схему ввода / вывода? Может ли это одно быть полным по Тьюрингу? » и я еще не могу ответить на эти вопросы. Нам просто нужно заткнуть уши, закрыть глаза и притвориться, что мы не подумали об этом незначительном осложнении.

(7) Я считаю, что это то, чем пытался заняться исследовательский проект Терминатор Microsoft, но я не знаю, что с этим происходит и каково текущее состояние дел.