💬 Бесконечный и неограниченный

Бесконечный и неограниченный

Эта статья была впервые опубликована в блоге доктора Крейга Райта, и мы повторно опубликовали ее с разрешения автора.

К сожалению, основная проблема связана с недостаточным пониманием многих распространенных сегодня терминов. Полнота по Тьюрингу не требует бесконечной ленты, и Тьюринг упомянул в своей статье не бесконечную ленту; это была неограниченная система. Важно отметить, что у вас не может быть машины Тьюринга с бесконечной лентой, а не с неограниченной лентой — по определению. Бесконечная лента не связана с проблемой, которую можно вычислить. Когда и Черч, и Тьюринг писали свои статьи, компьютер, о котором они говорили, был человеком. Человека, который был математиком, решившим задачи, называли компьютером. Поэтому, когда мы говорим о проблемах одного типа, мы говорим о задачах, которые можно вычислить с помощью простого алгоритмического процесса, которые могут быть созданы и использованы простым процессом, который теперь выполняется на машине.

Первое, что вам нужно запомнить, это то, что машина Тьюринга может решить любую вычислимую задачу. Не все алгоритмы могут быть вычислены. Сказать, что вы можете запустить программу, которая никогда не остановится, не значит создать машину Тьюринга. Это также не бесконечная лента; это неограниченная система. По определению любая неограниченная система всегда бесконечно меньше бесконечной. Если подумать, процесс, который выполняется как «неограниченный», требует системы в нашей вселенной, которая может работать во времени. По общему признанию, это потребовало бы очень большого значения для вычисления и ошеломляюще велико. Тем не менее, это что угодно, только не бесконечность.

Следующий и, возможно, более важный компонент, о котором следует помнить, заключается в том, что если в нашей вселенной нужно вычислить другое число, наша вселенная не бесконечна; время вычисления числа должно быть конечным. К сожалению, вычисления — неразрешимая проблема, потому что компонент математики привел к так называемой проблеме остановки (Turing, 1936; Burkholder, 1987). Вычисление значений может не останавливаться, и проблема остановки не может быть решена (Boyer & Moore, 1984). По той же причине невозможно определить, завершится ли когда-нибудь какой-либо сценарий, который может работать на машине Тьюринга. По самому своему определению любое вычислимое число и, следовательно, любое значение, которое может быть решено алгоритмически, должно закончиться в течение конечного времени. Чего люди не могут понять, так это того, что машины Тьюринга не запускают программы, которые нельзя вычислить алгоритмически. Любая программа, не имеющая алгоритмического решения, не является программой, разрешимой на машине Тьюринга. Многие из них либо потерпят неудачу, либо, что более важно, будут продолжаться бесконечно, так и не придя к решению.

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

Основная причина, по которой Bitcoin Core подвергает критике мой комментарий о том, что Биткойн является полным по Тьюрингу, связана с введением ограничений, которые изначально были временно наложены на Биткойн и которые были реализованы более коварными способами в BTC. В то время как я сказал, что Биткойн будет расти до точки, где он закончится в центрах обработки данных, они хотели создать отдельную систему, которая была бы более ограниченной. Ограниченная лента не может работать ни с одним алгоритмом. Другими словами, при ограниченном размере транзакции вы никогда не сможете достичь того же уровня вычислений, что и при неограниченном размере транзакции. Как продемонстрировал Роджерс (1959), существуют степени вычислительной неразрешимости, но это не устраняет того факта, что во многих случаях мы не знаем, разрешима программа или нет, пока она не будет запущена. Хуже того, как продемонстрировали Габури (1942) и позже Роджерс (1958), нет решения, позволяющего выяснить, можем ли мы вообще найти решение многих проблем.

В информатике существует проблема, известная как омега-проблема (Dantzig, Fulkerson, & Johnson, 1954; Hudzik, 1979). Сложность разработки алгоритмов заключается в том, что вы даже не знаете, как создавать алгоритмы, которые наверняка остановятся. Последствия омега-проблемы приводят к одной из трудностей исправления компьютерных ошибок. Омега непреодолимая. Если мы спросим о вероятности случайных программистов и о том, остановится ли этот алгоритм в конечном итоге для заданного ввода, мы не обязательно сможем даже определить, верен ли вопрос. Он связан с проблемой теории всего (ТОЭ) в физике. Мы не можем создать аксиоматическое основание для математики, но мы можем найти единую основополагающую теорию того, как устроена Вселенная. К сожалению, поскольку мы не в состоянии определить математические основы вычислений, попытки решить проблему остановки — это просто пустая дыра, которая заберет все, что мы можем дать, оставаясь при этом пустой (Jacobs, 1890).

Тьюринг написал несколько статей, подробно описывающих одну и ту же тему (Turing, 1936; Turing & Church, 1937) и смежные статьи о вычислимости и лямбда-определениях (Turing, 1937). Если вы прочтете их, то увидите, что он говорит о «вычислимых» числах (Turing, 1936, p. 230), которые «можно кратко описать как действительные числа, чье десятичное выражение можно вычислить конечными средствами». . Pi не является вычислимым по Тьюрингу значением по тому же определению. Скорее, приближение числа пи за конечное время и пространство можно считать вычислимым по Тьюрингу.

Есть много хороших ссылок на вычислимость различных числовых значений, включая пи. Нис (2009) предоставляет превосходный исследовательский справочник, связанный с этой темой, а другие, такие как Миллер (2003), предоставляют подходящие дополнительные работы. Я мог бы даже связать это с произведениями менее известных авторов, таких как Хусаинов, Сламан и Семухин (2006), но если бы я сделал это здесь, меня бы обвинили в пропаганде «техноболтовни». Это так, потому что такая работа, хотя и действительна и интересна с точки зрения алгоритмов и синтаксиса, является узкоспециализированной и даже, в некотором смысле, загадочной. Так что, к сожалению, сегодня в эту кроличью нору я не полезу.

Статья Тьюринга основана на работе Геделя (1931). К сожалению, если у вас нет математической подготовки в виде дискретной математики, о которой писали авторы, вы, вероятно, совершите одну из многих ошибок, которые делают люди, когда дело доходит до определения машины Тьюринга. Например, Тьюринг отметил (1936, стр. 230), что класс вычислимых чисел «тем не менее перечислим». Но он не сказал, что сама машина Тьюринга должна быть счетной, чтобы все остальное было правдой.

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

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

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

Шеннон (1956) рассмотрел предложенную Тьюрингом концепцию создания механической или электрической машины и допустил ошибку в описании. К сожалению, Шеннон (1956, стр. 157) описал машину Тьюринга как систему, требующую «элемент управления, считывающую и записывающую головку и бесконечную ленту». Однако не Тьюринг сказал, что машина Тьюринга должна быть бесконечной, а Шеннон. Другие в 50-х и 60-х годах, которые использовали распараллеливание в вычислениях, также использовали терминологию «бесконечный», когда они должны были сказать «неограниченный» или «неограниченный». Различие между невообразимо большим числом и бесконечным числом не имеет значения для большинства людей. Для многих ранняя концепция, используемая для упрощения дискуссий в физике и математике, называлась «эффективно бесконечной». Он используется в статье Фармера (1935), где автор отмечает, что хотя система и не бесконечна, приближенное значение можно получить, предположив, что это значение «фактически бесконечно».

Хотя Шеннон создал отличные инженерные решения, он не был математиком. Разница между инженерными знаниями, информатикой и математическими основами обеспечивает важное различие, поскольку Тьюринг (1936, стр. 230) категорически сказал, что это машина, которая может вычислять «действительные числа, чьи десятичные выражения могут быть вычислены конечными средствами». . Шеннон инженер. Для инженера математика системы менее важна, и разница между неограниченной системой и бесконечностью кажется бессмысленной; в каждом случае они представляют большие числа, чем вы когда-либо вычислите.

Тьюринг отметил, что вычислительная машина записывает не более конечного числа символов (1936, стр. 233). Таким образом, машина неограничена, но не бесконечна. Это существенное и важное различие, которое не смогли понять многие нематематики. Значение, связанное с неограниченной машиной, бесконечно меньше любого бесконечного значения. Таким образом, несмотря на то, что многие инженеры уравновешивают концепцию «фактически бесконечной» системы, а другие даже говорят, что значение 2^256 само по себе является бесконечным для всех целей, такие значения остаются вычислимыми и пригодными для использования в реальных терминах.

Более того, значения, фактически бесконечные в один момент времени, могут оказаться вычислимыми позже. Важно отметить неинклюзивные множества и концепции пределов, неограниченных систем и бесконечных систем. Например, можно сказать, что все существующие шифры (за исключением одноразовых блокнотов, которые никогда не использовались повторно) имеют срок годности и в конечном итоге могут быть взломаны. Из-за ограничений того, как мы обучаем людей сегодня, люди не понимают, что существует огромная разница между действительно бесконечной системой и системой, которая практически бесконечна. Важно отметить, что, несмотря на то, что значение может иметь пренебрежимо малую долю ошибок и может быть отброшено, Лоренц (1961) продемонстрировал, что небольшие вариации могут иметь значительное или одновременно важное влияние на результаты версий target="_blank" rel="noopener"> машины Тьюринга, и что в случае с автономной машиной Тьюринга, о которой я упоминал ранее, можно предположить, что лента не зацикливается. В своей статье (1969, стр. 169) вы заметите, что авторы убрали предположение о том, что машина останавливается при каждом вводе. Хотя он обеспечивает форму машины, это не более чем единичный пример, и люди принимают их за нечто большее, чем они есть, и делают их универсальными. Обратите внимание, что я не говорю здесь об универсальной машине Тьюринга, что опять-таки другое.

Предположим, вы прочитали статью полностью. Если вы это сделаете, вы увидите, что определение недетерминированной машины Тьюринга, представленное Хопкрофтом и Ульманом (1969, стр. 169) в виде 6-кортежа, создано с использованием конечных состояний и конечных символов. Следовательно, это не бесконечная машина. Создание конечных значений в неограниченной системе означает, что при необходимости ленту можно расширить. Это не означает, что лента в такой системе бесконечна, а скорее то, что каждый раз, когда приближается конец ленты, может быть добавлена ​​новая лента. При форматировании транзакций на основе биткойн-скриптов потребуется дополнительное место на диске для хранения разворачиваемой транзакции (Dongarra & Hinds, 1979).

Хотя люди используют термины "бесконечный" и "неограниченный" взаимозаменяемо, они представляют разные понятия. Между неограниченной системой и бесконечной системой есть разница, поскольку неограниченная система обязательно конечна. Хотя она не имеет определенных границ, она в общем и целом поддается определению, что отличается от бесконечной системы, которая в общем и целом неопределима. В процессе, отмеченном Steele (1980), создается ряд алгоритмов с использованием развернутых циклов. Тем самым автор продолжает некоторые работы Кнута (1973) и исследует создание серийных машин. В других исследованиях, таких как исследование Бейкера (1978), также изучались развернутые циклы для приложений линейных машин.

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

Односторонние автоматы с конечным числом состояний хорошо задокументированы и существуют уже много лет (Greibach, 1978). Некоторые также расширили свои исследования на изучение односторонних функций (Levin, 2003). Другие исследовали создание детерминированных односторонних машин Тьюринга в так называемом внезапном линейном пространстве и способы их создания более эффективно (Kutrib et al., 2015). Но, пожалуй, самое интересное использование такой системы заключается в создании так называемого упрощенного универсального клеточного автомата (Iirgen Albert & Culik II (1987).

Обратите внимание, что я сказал «в <пространстве> конечное», и я не сказал это таким образом, чтобы сказать, что это процесс, который является «бесконечным». Различие не математическое, а скорее в том, что в слове конечный отличается от английского выражения бесконечный. Неразрешимая проблема не может быть решена и не имеет решения. Тем не менее, неограниченная задача может быть вычислена при наличии достаточного времени и памяти. Лично меня интересовали вероятностные односторонние машины Тьюринга (Santos, 1969; Kaņeps & Freivalds, 1990). Во всех них, как показал Аблаев (1996), можно найти нижние границы вычислительной сложности таких систем.

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

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

Заключение

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

Ссылки

Аблаев, Ф. (1996). Нижние оценки сложности односторонней вероятностной связи и их применение к пространственной сложности. Теоретическая информатика, 157(2), 139–159.

Бейкер-младший, Х.Г. (1978). Обработка списка в режиме реального времени на последовательном компьютере. Сообщения ACM, 21(4), 280–294.

Бойер, Р. С., и Мур, Дж. С. (1984). Механическое доказательство неразрешимости проблемы остановки. Журнал ACM (JACM), 31(3), 441–458.

Буркхолдер, Л. (1987). Проблема остановки. Новости ACM SIGACT, 18(3), 48–60.

Черч, А. (1936). Неразрешимая проблема элементарной теории чисел. Американский журнал математики, 58 (1936), 345–363.

Гёдель, К. (1931). О формально неразрешимых теоремах «Принципов математики» и связанных с ними систем I. Jahreshfte fürmathematics und Physik, 38 (1931), 173-198.

Данциг Г., Фулкерсон Р. и Джонсон С. (1954). Решение крупномасштабной задачи коммивояжера. Журнал Американского общества исследования операций, 2(4), 393–410.

Донгарра, Дж. Дж., и Хайндс, А. (1979). Развертывание циклов на Фортране. Программное обеспечение: практика и опыт, 9(3), 219–226.

Фермер, Ф. Т. (1935). Устройство для записи средних амплитуд беспроводных эхо-сигналов. Математические труды Кембриджского философского общества. 31(2), 295–302.

Габури, Дж. (1942). О невычислимых числах: истоки квир-вычислений. Журнал собрания новых медиа| ISSN, 017X.

Грейбах, С. А. (1978). Односторонние автоматы с конечным посещением. Теоретическая информатика, 6(2), 175–221.

Хартманис, Дж. (1968). Вычислительная сложность вычислений на одноленточной машине Тьюринга. Журнал ACM (JACM), 15(2), 325–339.

Хенни, ФК (1965). Одноленточные автономные вычисления на машине Тьюринга. Информация и контроль, 8(6), 553–578.

Хопкрофт, Дж. Э., и Ульман, Дж. Д. (1969). Некоторые результаты о ленточных машинах Тьюринга. Журнал ACM (JACM), 16(1), 168–177.

Худзик, Х. (1979). Проблема отделимости, двойственности, рефлексивности и сравнения для обобщенных пространств Орлича-Соболева \(W_M^ k (\Omega)\). Математические комментарии, 21(2).

Джейкобс, Дж. (1890 г.). английские сказки. Дэвид Натт.

Жюйе Х. и Поллак Дж. Б. (1996). Массивно-параллельное генетическое программирование. Успехи генетического программирования, 2, 339–357.

Хусаинов Б., Сламан Т. и Семухин П. (2006). (Pi^0_1)-представления алгебр. Архив математической логики, 45 (6), 769–781.

Канепс, Дж., и Фрейвалдс, Р. (1990). Минимальная нетривиальная пространственная сложность вероятностных односторонних машин Тьюринга. Международный симпозиум по математическим основам информатики, 355–361.

Кнут, Д. Э. (1973). Искусство компьютерного программирования, том 2: Получисловые алгоритмы. Аддисон-Уэсли Профессионал.

Кутриб М., Провиллар Дж., Васзил Г. и Вендландт М. (2015). Детерминированные односторонние машины Тьюринга с сублинейным пространством. Fundamenta Informaticae, 136(1–2), 139–155.

Ирген Альберт, Дж., и Кулик И.И., К. (1987). Простой универсальный клеточный автомат и его односторонний и тотальный вариант. Сложные системы, 1, 1–16.

Левин, Л. А. (2003 г.). Сказка об односторонних функциях. Проблемы передачи информации, 39(1), 92–103.

Лоренц, Е. Н. (1956). Эмпирические ортогональные функции и статистический прогноз погоды. Департамент метеорологии Массачусетского технологического института.

Лоренц Э. (1961). Теория хаоса.

Маккарти, Дж. (1956). Инверсия функций, определяемая машинами Тьюринга. Исследования автоматов (AM-34), 34, 177–182.

Миллер, Дж. С. (2003). Классы Pi-0-1 в вычислимом анализе и топологии. https://dl.acm.org/doi/abs/10.5555/935786

Нис, А. (2009 г.). Вычислимость и случайность (т. 51). ОУП Оксфорд.

Роджерс, Х. (1958). Гёделевские нумерации частично рекурсивных функций. Журнал символической логики, 23(3), 331–341.

Сантос, Э. С. (1969). Вероятностные машины Тьюринга и вычислимость. Труды Американского математического общества, 22(3), 704–710.

Шеннон, CE (1956). Универсальная машина Тьюринга с двумя внутренними состояниями. Исследования автоматов (AM-34), 34, 157–166.

Стил-младший, Г. Л. (1980). Деструктивное изменение порядка кодированных CDR списков.

Тьюринг, А. М. (1936 г.). О вычислимых числах с приложением к Entscheidungsproblem. Труды Лондонского математического общества, 2(1), 230–265.

Тьюринг, А. (1936b). Проблема остановки. Лондонское математическое общество.

Тьюринг, AM (1937). Вычислимость и λ-определимость. Журнал символической логики, 2(4), 153–163.

Тьюринг, А. М., и Черч, А. (1937). Вычислимость и X-определимость. Символическая логика, 2.