Предполагают ли машины Тьюринга что-то бесконечное в какой-то момент?

В предыдущем вопросе Что такое алгоритм? Я спросил, является ли алгоритм алгоритмом, который возвращает значение функции, основанной на массиве предварительно вычисленных значений.

Один из ответов, который привлек мое внимание, был таким:

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

Теперь мы могли бы вместо этого рассматривать вычисления следующим образом: для каждого входного размера существует ТМ (или какое-либо другое вычислительное устройство), которое решает проблему. Это совсем другой вопрос. Обратите внимание, что один TM не может хранить факториал каждого целого числа, так как TM имеет конечное описание. Тем не менее, мы можем создать TM (или программу на C), которая хранит факториалы всех чисел ниже 1000. Затем мы можем создать программу, которая хранит факториалы всех чисел от 1000 до 10000. И так далее.

Разве каждая ТМ не предполагает какой-либо способ борьбы с бесконечностью? Я имею в виду, даже ТМ с конечным описанием, который вычисляет факториал любого числа N через алгоритм

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

содержит предположение, что TM имеет «аппаратное обеспечение» для сравнения чисел произвольного размера через компаратор «<=», а также ADDers для увеличения i до произвольного числа, более того , возможность представления чисел произвольного размера.

Я что-то пропустил? Почему подход, который я представил в своем другом вопросе, менее осуществим в отношении бесконечности, чем этот?

<=<=$Q$$\Sigma$

<=$|Q|$$|\Sigma|$

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

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

Описание TM - это конечный набор кортежей <current state, input, output, move, next state>.

На каждом шаге, что нужно сделать, найти путем сопоставления текущего состояния и ввода. Например, мы находимся в состоянии 0 и читаем 1, поэтому мы находим кортеж, который начинается, <0, 1, ...>затем мы записываем новое значение в текущую ячейку, перемещаемся влево или вправо (я думаю, что классическое определение также позволяет оставаться в той же ячейке а также), а затем перейти в новое состояние.

Таким образом, для вашего примера вам потребуется либо бесконечно большое описание TM (бесконечное число <current state, input, output, move, next state>кортежей), либо включить информацию о поиске во входные данные для TM. Я считаю, что вклад в ТМ определен как конечный. Так что это, вероятно, не то, что вы могли бы сделать с классически определенной машиной Тьюринга.

Напротив, пример Фибоначчи может быть вычислен в двоичном виде с конечным числом кортежей для описания ТМ и имеет конечный ввод.

В двух словах : машина Тьюринга может выполнять (конечно определенные) бесконечные вычисления на (конечно определенных) бесконечных данных и давать (конечно определенные) бесконечные результаты. Основная идея заключается в том, что эти бесконечности могут быть определены как предел конечных сущностей, определенных математически соответствующим образом. Это основа математической семантики вычислений. Если вы рассматриваете программы, а не машины Тьюринга, эти программы также могут содержать (конечно определенные) бесконечные структуры данных. Случай табличной функции factкак возможного алгоритма в конце анализируется как программа или модель TM с подсказкой относительно связи с ленивой оценкой бесконечных объектов.

Со многими другими деталями

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

Но оригинальный вопрос о роли бесконечности в машинах Тьюринга в целом.

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

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

Итак, если мы смотрим на проблему с бесконечным множеством экземпляров, такую ​​как вычисление GCD или просто использование арифметики на целых числах произвольного размера, мы видим, что бесконечность возвращается к нам через черный ход, как эта бесконечная набор FSA.

$\pi$

Опять же, мы можем заменить это бесконечной последовательностью конечных вычислений с конечными машинами. Но мы обманываем.

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

Но как мы можем обращаться с этими бесконечностями последовательным и понятным способом с математической точки зрения.

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

Что вы действительно хотите, это определить понятие согласованности. Но это требует некоторых мер предосторожности. Предположим, вы используете бесконечную последовательность автоматов для имитации ТМ, который отвечает да или нет или не останавливается. Проблема в том, что FSA всегда будет останавливаться с ответом, например, да или нет. Но если вы используете FSA, размер которого недостаточно велик для выбранного входа, на что он должен ответить. И да, и нет зарезервированы для случаев, когда FSA фактически прекратил вычисление TM, и использование одного из этих ответов с незавершенным вычислением приведет только к путанице. Вам нужен ответ, который говорит: « Извините, я слишком маленький, и я не могу сказать. Пожалуйста, попробуйте с большим парнем в семье ». Другими словами, вы хотите получить ответ типа переполнения или не знаете$\bot$

Таким образом, вам нужны автоматы, которые имеют 3 вида состояний: принимающий, не принимающий и неопределенный. Неопределенное состояние может рассматриваться как состояние, обозначающее отсутствующую часть автомата, которая заставляет вычисления останавливаться. Таким образом, когда вычисление останавливается, в зависимости от состояния, в котором оно останавливается, вы получаете ответ yes , no или undefined .

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

$\pi$$3.14\bot\bot\bot\bot...$$3.1415\bot\bot\bot\bot...$$\bot.\bot5159\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$\pi$

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

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

Самым простым документом, который я когда-либо читал, является рукописный набор лекций Даны Скотт, часто называемый амстердамскими лекционными заметками. Но я не смог найти его в Интернете. Любой указатель на копию (даже неполный, как у меня есть часть) будет приветствоваться. Но вы можете посмотреть на другие ранние публикации Скотта, такие как « Схема математической теории вычислений» .

Вернуться к первоначальному примеру вопроса

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

fact$\bot$

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

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

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

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

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

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

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

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

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

$23{rd}$ Но это все равно будет часто реализовываться как бесконечные вычисления, которые искусственно останавливаются при достижении правильного ответа.

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

На самом деле, единственное, что имеет значение в вычислениях, это то, что все должно быть определено конечным образом вычислимо, а не быть конечным .

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

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

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

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

Утверждения усул, воспроизведенные в вашем текущем вопросе, на мой взгляд, неверны (хотя все также является вопросом определения). В своем ответе он сделал вывод , что вы не воспроизвели, что использование бесконечной таблицы не может считаться алгоритмом, поскольку она может быть реализована только с помощью неоднородной модели вычислений, с помощью набора различных машин и, следовательно, такого использует « не имеют конечного описания, которое может быть реализовано для решения« целой »проблемы при любом размере ввода$\pi$

Способ, с помощью которого такие бесконечные объекты вычисляются на практике, заключается в ленивой оценке , вычислении любой необходимой части в любое время и возобновлении вычисления для некоторых остальных, когда потребуется больше. Это именно то, что предлагается выше, когда factмашина лениво вычисляет факториал для хранения в таблице всякий раз, когда из таблицы требуется больше данных.

В некотором смысле это, кажется, подтверждает утверждение (в ответе DanielV ), что кодовое пространство должно быть конечным, поскольку ленивая оценка будет фактически основана на некотором конечном коде. Но вычислимость - это широко распространенная игра кодирования, так что, среди прочего, различие кода от данных всегда в значительной степени в глазах смотрящего. Действительно, многие современные языки программирования не имеют большой разницы между интенсиональной и экстенсиональной спецификацией значений, и денотационная семантика на самом деле не отличает «2 + 2» от «4». Семантика - это то, о чем мы говорим, когда задаем такой вопрос, как « Что такое X ? ».

Такое представление о конечности кода, также рассматриваемое как статическое, является еще одной причиной, по которой бесконечная таблица (рассматриваемая как часть кода) не рассматривается на равных условиях с неограниченными целыми числами, используемыми в качестве данных. Но это еще одна иллюзия, которая не переживает известную практику программирования в метапрограммировании , рефлексивных языках и использовании evalфункции. На этих языках код может быть расширен без ограничений самой запущенной программой, пока компьютер работает. Действительно, можно рассмотреть машины Тьюринга, которые изменяют свои собственные правила перехода, увеличивая их количество без ограничений. Это довольно близко к тому, как работают машины Universal Turing.

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

Краткий ответ: нет . Машины Тьюринга не предполагают ничего бесконечного в любой точке.

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

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

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

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

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

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

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