Обсуждение:Пост–машина Тьюринга

Данная статья была номинирована на удаление 27 августа 2020 года. Результатом обсуждения стало сохранение .

Эта статья имеет рейтинг B-класса по шкале оценки контента Википедии . Она представляет интерес для следующих WikiProjects :

Математика Низкий приоритет This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

В статье утверждается, что работа Поста независима от работы Тьюринга. Однако Юрий Гуревич утверждает, что Пост видел статью Тьюринга до того, как приступить к своей работе. Есть ли еще доказательства в пользу того или иного варианта? Rgrig ( talk ) 17:18, 10 сентября 2010 (UTC) [ reply ]

Гуревич не лентяй, так что, может быть, его "факты" (понимание) неверны? Единственный способ, которым Пост мог увидеть статью Тьюринга, был бы в том, что Алонзо Чёрч показал Посту копию неопубликованной статьи Тьюринга, или кто-то другой тайком передал ему копию, а затем Пост солгал об этом. Но что бы Пост выиграл от этого? Когда вы читаете исторические факты (последовательность времени), это вообще не имеет смысла. Поэтому мы применяем бритву Оккама и придерживаемся самого простого объяснения: их работа была независимой.

Вот известные мне письменные факты, взятые из книги Мартина Дэвиса «Неразрешимое » 1965 года (сборник переизданных статей) и биографии Алана Тьюринга, написанной Эндрю Ходжесом в 1983 году:

В 1936 году Алонзо Чёрч начал издавать новый журнал The Journal of Symbolic Logic в Принстоне, штат Нью-Джерси. Тем временем, в Великобритании, через своего профессора, Тьюринг представил свою статью (на самом деле магистерскую диссертацию) 31 мая 1936 года в Лондонское математическое общество (Hodges 1983:112). Чёрч был единственным, кто мог рецензировать статью, и поэтому LMS отправила статью ему для комментариев (Hodges 1983:113). 23 сентября 1936 года Тьюринг отплыл из Великобритании в Принстон (он был на гранте); здесь он встретился с Чёрчем и др. Он получил свои доказательства где-то осенью (октябрь, ноябрь) для рецензирования (ср. Hodges страницы 116-123). Одновременно, 7 октября 1936 года, Чёрч получил статью Эмиля Поста (Пост преподавал в Городском колледже Нью-Йорка) "Конечные комбинаторные процессы, формулировка I", т.е. через 5 месяцев после статьи Тьюринга и в то же время, когда Тьюринг получил свои доказательства для проверки. Чтобы опубликовать статью Поста, Чёрч "должен был подтвердить, что работа была полностью независимой" (Hodges 1983:125). Вот что он написал в сноске к статье Поста:

Получено 7 октября 1936 г. Читатель должен сравнить статью А. М. Тьюринга « О вычислимых числах» , которая вскоре появится в Трудах Лондонского математического общества . Однако настоящая статья, хотя и датирована позже, была написана совершенно независимо от Тьюринга. Редактор

Статья Поста появилась в печати в конце 1936 года (точная дата?). Статья Тьюринга появилась немного позже, в Трудах Лондонского математического общества, сер. 2, т. 42 (1936-37) в январе 1937 года.

Я не знаю никаких доказательств того, что Чёрч и Пост были знакомы лично — нам пришлось бы найти биографии обоих мужчин — но Пост в своей статье 1936 года сослался на «Неразрешимую проблему элементарной теории чисел» Чёрча 1935 года. Чёрч, по-видимому, знал о докторской диссертации Поста 1921 года — весьма важной статье, которая впервые формализовала метод «таблицы истинности» и нанесла значительный удар по «теории типов» Рассела, которая была ему нужна для Principia Mathematica (ср. van Heijenoort 1967:264ff). Поэтому мы можем предположить, что эти двое знали друг друга. Билл Увбейли ( обсуждение ) 18:30, 10 сентября 2010 (UTC) [ ответить ]

Вот почему я всегда проверяю страницы обсуждения; Википедия была бы намного слабее без этой информации, информации, которая никогда не будет разрешена в рамках жесткой структуры главной страницы. Спасибо! 2001:470:1F09:10D6:F21F:AFFF:FE54:B8C (обсуждение) 08:25, 13 ноября 2014 (UTC) [ ответить ]

См. http://en.wikipedia.org/wiki/Wikipedia:Five_pillars, «все редакторы должны следовать нашей политике отсутствия оригинальных исследований »).

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

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

По поводу названия мы не согласны. Я видел, как это используется в сети. Дэвис использовал слова "программа Тьюринга-Пост". И я сделал кучу перекрестных ссылок.

Машина Тьюринга-Пост

Модель Тьюринга-Поста

Программа Тьюринга-Пост

Пост-машина Тьюринга

Программа после Тьюринга

Пост-Тьюринговская модель

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

wvbailey Wvbailey 21:36, 12 января 2006 (UTC) [ ответить ]

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

Не обязательно "универсальные"... Но три цитируемых: чрезвычайно похожи, просто отклонения в инструкциях 6-7 в "наборе" плюс {0,1} или {blank,mark} только на ленте. Версия Тьюринга существует как контрапункт.

Я не думаю, что вы бы рассматривали их, если бы они не были универсальными .

(Кстати, одно из главных различий между этими двумя теориями, о котором не упоминалось, заключается в том, что Пост настаивал на останавливающихся вычислениях, тогда как вычисления Тьюринга должны были быть непрерываемыми !) --res ( Обсуждение ) 00:36, 13 января 2006 (UTC) [ ответить ]

Пост предоставил свой STOP для числовых вычислений, но не для логических, где он не будет использоваться (я не уверен, почему).

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

Вы не поверите, какую борьбу я вел по поводу темы HALT/STOP против «кругов» Тьюринга. (См. диалог на странице «Проблема остановки» в разделе «Обсуждение: «История» или что-то в этом роде...). Этот «диалог» с разными людьми продолжается уже несколько недель. А также: откуда взялась фраза «проблема остановки»? Этот вопрос — причина, по которой я вообще занялся Википедией, просто чтобы ответить: почему доказательство Тьюринга так отличается от «доказательств остановки». Происхождение «проблемы остановки» (вероятно) не было связано с Тьюрингом, но кто это был? Как это произошло? Идеи? Обсуждение: «История» и сноски на странице «Проблема остановки» должны прояснить этот вопрос. Также путаница между "Проблемами Гильберта" 1900 года и его переработанным в 1928 году "1900 Hilbert #2" как "1928 3 Hilbert Questions" ...wvbailey Wvbailey 02:06, 13 января 2006 (UTC) [ ответить ]

Я не вижу причин сомневаться в том, что доказательство Тьюринга было первым доказательством неразрешимой проблемы типа «проблемы остановки». (Доказательство неразрешимости Чёрча для проблемы в λ-исчислении было более ранним, но не относилось к этому типу.) Что касается того, кто мог впервые поставить такую ​​проблему (независимо от того, подвергать ли ее разрешимость сомнению), то это может быть невозможно выяснить. Но я думаю, важно понимать, что λ-исчисление Чёрча, а также комбинаторная логика (возвращающаяся к 1920-м годам) включают идею приведения термина к «нормальной форме» за конечное число шагов — поэтому, конечно, в статье Чёрча 1936 года обсуждаются приведения, которые « должны (если продолжать) заканчиваться в нормальной форме ». (Это не было представлено как проблема разрешимости, а всего лишь часть его разработки λ-определимости.) --res ( Обсуждение ) 09:16, 13 января 2006 (UTC) [ ответить ]

Интересно, спасибо. Я посмотрю статью(и) Чёрча и посмотрю, где есть слово "завершить", и тоже на неё сошлюсь. Что касается различных форм "Остановочного доказательства" (в отличие от кругового доказательства Тьюринга), то примерно так же, как я смог обойтись без похода в библиотеку, как у Минского в 1967 году [так что я могу добавить его на эту страницу, как-то, как в "Самую раннюю известную версию...". Интересно, что Минский (1967), Дэвис в Стине (1978), Бельтрами (1999) все используют то, что я называю версией "антиномии", хотя есть и тонкие различия - все они включают использование алгоритма с ОСТАНОВКОЙ в одной ветви, но с "кругом" какого-то рода в другой ветви. wvbailey Wvbailey 17:54, 13 января 2006 (UTC) [ ответить ]

Я думаю, стоит взглянуть на статью Хао Вана, в которой представлена ​​«программная формулировка» ТМ, очевидно, основанная на Формулировке 1 Поста :

Ван, Хао (1957): «Вариант теории вычислительных машин Тьюринга», Журнал Ассоциации вычислительной техники (JACM) 4, 63-92.

Краткое описание есть в [программе Ванга]

В любом случае, Тьюринг и другие все еще ссылались на его версию задачи без кругов/круговую версию в конце 1940-х годов, так что я подозреваю, что именно в 1950-х годах укоренилась «современная» версия — может быть, она есть в статье Вана? --res ( Обсуждение ) 20:03, 13 января 2006 (UTC) [ ответить ]

Это не была статья Вана. Я посмотрел и отсканировал ее; для получения дополнительной информации см. Halting Problem в "Footnote|Davis". Я уверен, что я тоже поймаю мегадерьмо за эти изменения, но я копал глубоко, просматривая реальные вещи в коллекции математического факультета в библиотеке Дартмута. "Halting Problem"? Похоже, что эту фразу придумал Дэвис...

Проблема в следующем: если рецензент не может предоставить опровергающую документацию, его слово... менее чем бесполезно.

Изменения RE в первом абзаце: Дэвис действительно называл их "машинами пост-Тьюринга", а программы - "программами пост-Тьюринга". И забавная вещь: бедный Дэвис в "Что такое вычисление?" оговорился и в одном месте сослался на "программу пост-Тьюринга" (стр. 256) вместо того, чтобы использовать "программу Тьюринга-Поста" в другом месте своей статьи. Я был удивлен, обнаружив более ранние материалы Дэвиса, особенно в чем-то столь малоизвестном, как документ, в котором я их нашел (он выглядел как мимеограф... но пусть будет так...): В любом случае, это есть в печатной литературе... это не "я". Wvbailey 00:25, 18 января 2006 (UTC)wvbailey [ ответить ]

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

Я открыл работу перед собой. но в этих эквивалентах есть что-то особенное: простота. Это не просто еще один эквивалент. wvbailey Wvbailey 21:36, 12 января 2006 (UTC) [ ответить ]

Но эти две модели настолько различны, что их композит будет просто еще одной эквивалентной моделью Тьюринга. --res ( Обсуждение ) 20:58, 12 января 2006 (UTC) [ ответить ]

Что означает «ОТ»?

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

Под "OT" я подразумевал "не по теме" — тема, как я понимаю, очень простые варианты модели "формулировки 1" Поста. Чтобы проиллюстрировать, как данные могут быть закодированы в этих моделях (которые даже не являются "вычислительными машинами" по определению Тьюринга, поскольку их алфавиты строго двоичны), я думаю, было бы предпочтительнее ограничить примеры вариантами формулировки 1, а не ссылаться на универсальную машину Тьюринга и на то, как она была закодирована. (Я подозреваю, что мало кто, кроме нас двоих, интересуется оригинальной моделью Тьюринга, учитывая, что она была "отлажена" и заменена теперь уже стандартными переформулировками, как в статье о машине Тьюринга .) --res ( Обсуждение ) 01:05, 26 января 2006 (UTC) [ ответить ]

Я бы не возражал, если бы вы его сократили/вычеркнули и переместили остатки на страницу обсуждения, чтобы это была фоновая ссылка. Думаю, я все еще борюсь с вопросом, о чем статья "на самом деле". wvbailey Wvbailey 17:03, 26 января 2006 (UTC) [ ответить ]

Выполнено -- см. ниже.--res ( Обсуждение ) 03:21, 3 февраля 2006 (UTC) [ ответить ]

Исходя из вашего знакомства с этим материалом, я предполагаю, что вы написали U-код для машины PT, поэтому вы знакомы с кодированием "0" и "1", например, как пробел-метка и метка-пробел, а затем оставляя третий квадрат между ними в качестве места для указателей... или чего-то еще (какое-то однозначное кодирование, чтобы U мог сохранять ясность ума). И кодирование инструкций в унарной системе с дополнительными "метками" (например, или пробелами), которые U временно стирает (или печатает)... но поскольку мы не можем публиковать оригинальную работу... [Я сделал это еще в середине 1980-х, у меня все еще есть код, я запустил небольшой пример на своей машине]... если только вы не знаете какие-то печатные материалы, на которые мы можем ссылаться (и я избегаю веб-страниц, потому что они не рецензируются)... мы ограничены опубликованными отчетами о том, как другие проектировали U-машины в коде "PT" пробел-метка. Вы знаете такие? То есть опубликованный на бумаге U-код в предложениях с "пробелами" для "PT-машины"? (Я почти уверен, что видел его много лет назад для настоящей машины Тьюринга, то есть 5-кортежа, я думаю, в "Hennie". Я нашел ссылку в своей старой записной книжке, что он использовал нули (пробелы) в унарной системе). wvbailey Wvbailey 16:52, 25 января 2006 (UTC) [ ответить ]

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

«Дж. У. Тэтчер, Самоописывающие машины Тьюринга и самовоспроизводящиеся клеточные автоматы», в книге А. В. Беркса (ред.), Эссе о клеточных автоматах , U. Illinois Press, Урбана, 1970; стр. 103-131.

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

Я «сканировал» статью Вана, но, насколько я помню, она все еще в традиции Тьюринга «5-кортежей» или «4-кортежей» [«3-кортежей» ?] Давайте посмотрим... машина PT является как 2-кортежами («действие ленты: L, R, E, P», «следующая инструкция» [или #qj] ), так и чем? 3-кортежами для условных переходов? Давайте посмотрим («символ ленты», если-символ, то перейти к-ци, если не-символ, то следующая инструкция [или #qj]) [Если переход: машина U должна перейти в «область данных», посмотреть и увидеть, есть ли отметка на отсканированном квадрате, затем вернуться к инструкции перехода и принять решение на основе перехода-если-отметка или перехода-если-пусто. Затем он либо восстанавливает свой указатель и переходит направо к следующей инструкции, либо переходит к переходу: «отмечает» адресный квадрат, переходит влево к «инструкции № 0» и отмечает ее, переходит вправо к переходу и ремонтирует и «отмечает» все квадраты справа, затем переходит влево к инструкции № 0, ремонтирует отметку, переходит направо к инструкции № 1 и отмечает ее и т. д., пока все отметки не будут «использованы» и U не придет к новой инструкции].

Ван (1957), с благодарностью Посту, часто упоминается как источник «программной формулировки» машин Тьюринга с двоичной лентой, использующих пронумерованные инструкции из набора

написать 0

написать 1

двигаться влево

двигаться вправо

если сканирование 0, то перейти к инструкции i

если сканирование 1, то перейти к инструкции j

где предполагается последовательное выполнение , и единственное "if ... then ... else" Поста было "атомизировано" в два "if ... then ...". Дэвис и другие последовали за Вангом в этом, насколько мне известно. В любом случае, это настолько близко к Посту, что кажется вполне уместным считать их "посттьюринговскими" программами. (Кстати, универсальная программа Ванг, о которой я упоминал выше, использует очевидное расширение этого набора инструкций на ленты с более чем двоичным алфавитом.)

Похоже, нам следует поместить Вана на страницу и... что, убрать Бельтрами? (он ничего не внес в историческом смысле, он просто еще один пример, то же самое для Пенроуза). На самом деле, я просто собираюсь это сделать, скопировать ваши слова в статью. Убрать Бельтрами и добавить Вана. Вы знаете, были ли Ванг и Дэвис на одном факультете? Я почему-то думаю, что они были, или Дэвис был моложе Вана, может быть, студентом.wvbailey Wvbailey 17:13, 27 января 2006 (UTC) [ ответить ]

Итак, на самом деле есть только три фундаментальных инструкции: «переместить ленту», «напечатать символ на ленте» и «перейти», и у каждой из них есть два варианта (интересная симметрия): L/R, P/E, Jb/Jm. И если каждое «перемещение» и «печать» — это 3-кортеж [нет..., некоторые результаты пустая трата], можем ли мы обойтись без перехода? ... нет, нам нужно добавить «нет хода» [это правда? это будет фактически условный переход]. Интересный вопрос: каково минимальное количество общих «-кортежных-записей». Похоже, 8 + 3 + 3 = 14. Это правда?

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

Думаю, мне интересно: какой из всех наборов инструкций является «самым атомизированным» (если такой вопрос вообще имеет смысл)? Одной из мер может быть: не считая использования унарного кода, какая кодировка даст наименьшее количество инструкций (где инструкция перехода считается как «двойная» P, L, Jb, 1, E, R, Jb, 4, Jb, 1) на ленте при записи «примера», даже если есть компромисс по скорости. «Хорошая» вещь в «переходе к следующей инструкции в последовательности» заключается в том, что «следующая инструкция в последовательности» может быть обработана «аппаратным счетчиком» и не тратить ленту (и время). Плохая вещь в том, что это может привести к более длинным последовательностям инструкций, в конечном счете? Или, возможно, другой мерой может быть: какая кодировка дает «самую простую машину PT» в «счетчике вентилей» (вероятно, каноническая версия конечного автомата). Или, если лента рассматривается как сдвиговый регистр, каждый квадрат которого имеет определенное "количество вентилей", какой будет "самый дешевый" набор инструкций и машина. Просто чудо. Это напоминает мне (старую) статью в Scientific American, где культура строит "компьютер", странствующий по вселенной, где время не проблема, а низкое потребление энергии и надежность/сложность, и, может быть, размер, как кто-то построит его.

Мой интерес к тьюринговым тарпитам привел меня к написанию кода и реализации универсальной машины на двоичном варианте языка программирования Бёма P′′ (который является эквивалентом формулировки Поста-1, использующей циклы while вместо условных goto).

Интересно. Я посмотрел ссылку на Бёма... он использовал счетчик в своих циклах while? Звучит немного похоже на то, что Минский описал в своем тексте. В какой-то момент я добавил счетчик к своей машине PT с тремя новыми командами: Up ​​(инкремент), Down (декремент) и Jump-if-zero. Это значительно сократило универсальный машинный код и действительно ускорило машину. Условные переходы увеличивали счетчик, чтобы «сохранить» адрес перехода; затем U перемещался влево к началу кода, а затем перемещался вправо, «уменьшая» счетчик при каждой инструкции.

В конструкции Бёма "(...)" не задействованы счетчики. Это простой цикл while; т. е. с алфавитом {0,1}, "(...)" означает "пока сканируемое значение равно 1 do ... end_while", и, как обычно, проверка выполняется в начале каждого предполагаемого цикла.

Чтобы решить проблему кодирования данных в этом случае, я обобщил идею Тьюринга о чередующихся типах квадратов, чтобы использовать четыре (вместо двух) чередующихся последовательностей битов, и использовал строго унарное кодирование повсюду. Я упоминаю об этом, чтобы подчеркнуть возможно удивительную свободу действий, которую двоичные машины имеют в своей организации и использовании памяти.--res ( Talk ) 01:05, 26 января 2006 (UTC) [ ответить ]

Я полностью согласен с проблемой свободы действий. Это удивительно: некоторые люди, такие как я, кодируют с "отметками", чтобы "вести счет", другие кодируют с "пробелами" для подсчета, некоторые бедняги, которые никогда его не создавали, пытаются использовать двоичный код, я полагаю, что вы можете, но какой кошмар. Я экспериментировал с безусловным "переходом" плюс один условный переход. Даже решение использовать "канонический конечный автомат" или "заклинивающий счетчик" в качестве "памяти инструкций" приводит к разным конструкциям. (Я построил три таких варианта в Excel.) Возможно, это обсуждение может быть кому-то полезным - студентам, скажем, - поскольку оно "офлайн", и мы "раскрываем" больше. Я использовал кое-что из этого, пытаясь найти способ для микроконтроллера квази-"самотестировать" себя (создание "случайных чисел" было лучше, но я обнаружил интересный трюк с машиной PT). Эта штука может иметь некоторое теоретическое применение, которое мы не можем себе представить.wvbailey Wvbailey 17:03, 26 января 2006 (UTC) [ ответить ]

Написание собственного кода для универсальной машины практически на любом из этих примитивных языков, скорее всего, будет очень сложной задачей (и более чем просто немного познавательной, если судить по моему опыту). --res ( Обсуждение ) 23:52, 26 января 2006 (UTC) [ ответить ]

Образовательная тема была источником моего изначального интереса к этому много лет назад: найти дешевую, сложную "обучающую компьютерную" штуку. Но я обнаружил, что она была по сути "слишком" сложной. Только самые простые программы были под силу среднему смертному. (Программа умножения довольно аккуратна, я бы сказал, предел). С тех пор я использовал ПТ как вызов самому себе, когда сталкивался с "новым языком", например, чтобы написать его на C, в Excel, на языке ассемблера, что угодно... wvbailey Wvbailey 17:48, 27 января 2006 (UTC) [ ответить ]

[Ниже приведена копия раздела, который считается не относящимся к теме данной статьи и перемещен сюда для возможного обсуждения на странице обсуждения. --res ( Обсуждение ) 03:21, 3 февраля 2006 (UTC)] [ ответить ]

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

Пенроуз в своей книге « Новый разум императора» , стр. 30 и далее, явно описывает использование «унарного кодирования» (Пенроуз, стр. 41), хотя он не первый, кто использовал это соглашение. (Унарное кодирование встречается в разделе 10 статьи Тьюринга 1936-1937 годов, в которой n ^-е значение в последовательности представлено «количеством цифр 1 между n - ^й и ( n +1) ^-й цифрой 0»). Процитируем Пенроуза:

«Поскольку мы хотим иметь возможность включать числовые данные как часть наших входных данных [т. е. данные на ленте], мы захотим иметь способ описания обычных чисел (под которыми я здесь подразумеваю натуральные числа 0, 1, 2, 3, 4, ...) как части входных данных. Одним из способов сделать это может быть простое использование строки из n единиц для представления числа n (хотя это может вызвать у нас трудности с натуральным числом ноль):

1 -> |, 2 -> | |, 3 -> | | |, 4 -> | | | |, 5 -> | | | | | и т.д.

Эта примитивная система счисления называется (довольно нелогично) унарной системой. Тогда символ '0' можно было бы использовать как пробел для разделения различных чисел друг от друга. Важно, чтобы у нас был такой способ разделения чисел..." (Пенроуз, стр. 41)

При создании универсальной машины «кодирования» Бельтрами использует «двоичный код» для инструкций, например, «запись 0» имеет код 000, «запись 1» имеет код 001 и т. д. В отличие от модели Пенроуза, Бельтрами использует строку нулей для обозначения адреса перехода, а не строку единиц.

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

Тьюринг также использовал унарно-подобное кодирование как часть «Стандартного описания» (SD) машины, которое представляло собой строку с использованием символов A, C, D, L, R, N и точки с запятой ';'. Было принято соглашение, согласно которому квадраты ленты чередовались между двумя типами — «F-квадраты» (чье содержимое никогда не должно было стираться и должно было образовывать «непрерывную последовательность» без «пробелов до конца»), и «E-квадраты» (чье содержимое можно было стирать, для «черновых заметок, помогающих памяти», используя «достаточно богатое разнообразие символов»). В частности, символы SD должны были появляться на ленте в F-квадратах, а универсальная машина U могла печатать любые из символов A, C, D, 0, 1, u, v, w, x, y, z и двоеточие ':' (при этом u, v, w, x, y, z использовались как стираемые «маркеры» в E-квадратах). Таким образом, универсальная машина эмулирует любую вычислительную машину M, SD которой она находит на ленте в F-квадратах, печатая (в других F-квадратах) кодировки последовательных полных конфигураций M — включая ту же подпоследовательность «цифр» (0 и 1), которую печатала бы M — и используя E-квадраты в качестве вспомогательного рабочего пространства.

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

Например: Следующая строка представляет собой код для четырех инструкций, которые будут печатать на ленте 0 1 0 1 ... до бесконечности вправо (пример Тьюринга на стр. 127 в «Неразрешимом» ):

;ДАДДКРДАА ; ДААДДРДААА ; ДАААДДККРДАААА ; ДААААДДРДА

Ниже показаны инструкции, которые формируют строку. Здесь «qn» означает «инструкция №n», «Si» означает «символ №i», S0 — «пусто», S1 = «0», S2 = «1»:

Inst{ q1 S0 S1 R q2 } = DADDCRDAA

Inst{ q2 S0 S0 R q3 } = DAADDRDAAA

Inst{ q3 S0 S2 R q4 } = DAAADDCCRDAAAA

Инст{ q4 S0 S0 R q1 } = DAAAADDRDA

Инструкции должны были предваряться "D", за которой следовала бы унарная строка из A (т. е. инструкция № 4 - это "q4" и кодируется как "D", за которым следуют четыре A: DAAAA). Символы, которые должны были быть напечатаны (командой универсальной машине U, только косвенно машиной на ленте), должны были предваряться "D", за которой следовала бы унарная строка из C (в частности, "blank" - это D, "0" - это DC, "1" - это DC C. Другие символы, если требовалось, могли быть определены таким же образом.

При обычных соглашениях ввода/вывода невозможно опустить инструкцию записи 0 , иначе количество единиц на ленте никогда не уменьшится, и, таким образом, функция не может быть вычислена. Я не смотрел на фактическое письмо Вана; есть ли у кого-нибудь легкий доступ к нему? Я уверен, что проблема в том, что у Вана есть какое-то нестандартное соглашение ввода/вывода, как и в оригинальной статье Тьюринга. Это нужно прояснить. CMummert 02:42, 25 июля 2006 (UTC) [ ответить ]${\displaystyle \lambda x.1}$

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

«Теперь мы можем продемонстрировать замечательный факт, впервые показанный Вангом [1957], что для любой машины Тьюринга T существует эквивалентная машина Тьюринга Tn, которая никогда не меняет однажды записанный символ ! Фактически, мы построим двухсимвольную машину Tn, которая может только менять пустые квадраты на своей ленте на 1, но не может менять 1 обратно на пробел». (курсив его; Минский 1967, стр. 262-266)

Он предлагает нам теорему 14.5-1:

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

Доказательство занимает 3 страницы. Он начинает с создания машины T'n, используя 4 символа 0 = 000, A = 100, B = 100, C = 110. Он показывает, что любая машина T может иметь эквивалентную T'n со следующими ограничениями:

0 -> А, 0 -> В, 0 -> С, А -> В, А -> С, В -> С

В продолжении он комментирует, что эта машина стирает все записи своих вычислений, преобразуя все символы в символы C. Машина, которая ведет запись, также возможна. Я не читал доказательство; оно выглядит простым, но сложным. Дайте знать, если вам нужна дополнительная информация.wvbailey Wvbailey 03:35, 25 июля 2006 (UTC) [ ответить ]

Раздел, о котором идет речь, был написан мной («res»), и (как отмечено) не ошибается, что инструкция «write 0» не нужна для полноты Тьюринга. «Программная формулировка» ТМ Вана не использует «нестандартные» соглашения о вводе-выводе, за исключением (в случае «нестирания») в смысле чередования ячеек, используемых для ввода-вывода, с теми, которые используются как «рабочие ячейки», во многом как это делал Тьюринг. Для представления чисел используется стандартный унарный код. Сначала Ванг представляет полную по Тьюрингу формулировку, использующую только четыре типа инструкций, эквивалентных {"write 1", "shift right", "shift left", "if 1 goto k"} — с соглашением об альтернативных ячейках ввода-вывода — а затем обсуждает различные альтернативные наборы инструкций, например, включающие эквиваленты "write 0", "if 0 then goto k", "(безусловный) goto" и т. д., указывая на то, что вспомогательные ячейки не нужны, когда к набору добавляется "write 0". (Он заявляет, что это "открытый вопрос", можно ли обойтись без вспомогательных ячеек в случае нестирания.) Кстати, вероятно, стоит также отметить, что Ванг на самом деле представил эту "статью 1957 года" на собрании ACM в 1954 году! --res ( Talk ) 05:43, 25 июля 2006 (UTC) [ ответить ]

Предположим, мне нужна машина, которая выполняет вычисления, используя следующую схему ввода/вывода, которая, как я считаю, является стандартной:${\displaystyle \lambda x.1}$

Просто интересно: что такое "лямбда x.1?" Спасибо, wvbailey Wvbailey 15:22, 25 июля 2006 (UTC) [ ответить ]

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

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

Обычно "0" т.е. пустое множество { } записывается в унарной системе как |, одиночный знак. "1" т.е. последующее за "0" записывается как ||, "2" т.е. последующее за "1" записывается как ||| -- три знака. Насколько мне известно, никто не пытается представить "0" как "пустое".wvbailey Wvbailey 15:22, 25 июля 2006 (UTC) [ ответить ]

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

Есть хитрый способ сделать это — в конце расчета намеренно отправить машину в «узкий круг», как в «xxx: безусловный переход к этой инструкции xxx» и использовать вторую машину (например, меня-как-компьютер) для обнаружения этого состояния. Это то, что я делал со своими самодельными машинами; я-как-компьютер обнаруживаю это состояние визуально. Но построить «детектор» просто. Кроме того, мы обычно делаем это в проектах на основе микроконтроллеров; в конце последовательности вычислений мы помещаем микроконтроллер в узкий круг и включаем прерывание по времени; мы позволяем прерыванию «выгнать собаку» из ее «узкого круга».wvbailey Wvbailey 15:22, 25 июля 2006 (UTC) [ ответить ]

Ответить CMummert: Извините, если комментарий показался мне загадочным — я отредактировал (и, надеюсь, прояснил) эту часть статьи. Машины Ванга останавливаются, если есть попытка передать управление на номер инструкции, которого нет в программе. (Это происходит только двумя способами: при выполнении goto, который пытается перейти на несуществующий номер инструкции, или сразу после выполнения последней инструкции в программе.) Ниже приведен мой ответ относительно соглашений о вводе-выводе, которые полностью стандартны в «машине W» Ванга. --res ( Обсуждение ) 23:58, 29 июля 2006 (UTC) [ ответить ]

Оригинальная статья Тьюринга о вычислении действительных чисел также использует нестандартные соглашения ввода-вывода. Возможно, поэтому считалось, что модель Вана этого не делает. CMummert 11:27, 25 июля 2006 (UTC) [ ответить ]

Обозначение обозначает постоянную функцию . Если машина должна останавливаться только с одной (или двумя, это не имеет значения) непустыми ячейками, но на входе может быть произвольное количество непустых ячеек, то машина должна либо стереть некоторые ячейки, либо не сможет вычислить эту функцию. Вот почему в статье необходимо описать нестандартное соглашение о вводе/выводе, которое использует Ван. Наиболее близким к стандартному современному пониманию машины Тьюринга является то, что она представляет числа в унарной или двоичной системе счисления (или унарной с конечным маркером, если вам так больше нравится) и останавливается в конце успешного вычисления. Модель Ванга, по-видимому, не следует этим соглашениям. CMummert 15:56, 25 июля 2006 (UTC) [ ответить ]${\displaystyle \lambda x.1}$${\displaystyle f(x)=1}$

Мне придется уйти и подумать, можно ли успешно запрограммировать "k = 1" с помощью "машины Ванга". С трюком, описанным выше ( 0 = 000, A = 100, B = 100, C=110), я думаю, что можно.wvbailey Wvbailey 17:00, 25 июля 2006 (UTC) [ ответить ]

Я вышел на прогулку, и мне пришла в голову мысль: что машина Тьюринга в состоянии HALT может не останавливаться в конце успешного вычисления. Скорее, «плохой скачок» — из-за «программной ошибки» или «шума», или «неудачного ввода», или «невезения», или «сломанной машины» — может преждевременно отправить машину в состояние HALT (лучше всего использовать только один HALT в «программе») до того, как машина сможет вывести свое вычисление (число). Это постоянно происходит в (плохо спроектированных) микроконтроллерах и является очень плохой вещью (травмирует/убивает людей, уничтожает имущество) — я никогда не использую HALT (STOP) в своей работе, а вместо этого использую схему сторожевого пса, которую я описал выше. Есть целая наука вокруг сторожевых таймеров и их использования).

Я хочу сказать, что HALT нельзя доверять как индикатору успешного вычисления. Тогда возникает вопрос: как мы узнаем , что "продукт" нашей машины (выходное число, вычисление) правильный или даже "завершен"? [Возможный ответ: мы не знаем, если только не сделаем пример вычисления вручную (по совету Кнута -- "читатель всегда должен брать карандаш и бумагу и работать над примером каждого алгоритма..." (т. I, стр. 4). Но этот пример вычисления действителен только для этого случая; у нас есть только вероятность успешного вычисления, никаких гарантий. Это отвратительная проблема. Прямо перед тем, как я "ушел на пенсию", я работал над этой самой проблемой -- "вычислительной корректности" -- и мало что мог о ней найти, только одна группа в Стэнфорде работала над ней (под руководством Э. Дж. МакКласки, насколько я помню.) wvbailey Wvbailey 17:00, 25 июля 2006 (UTC) [ ответить ]

Под успешным вычислением я подразумевал просто завершение вычисления. Действительно, возможно, что конкретная машина будет неправильно запрограммирована так, что остановится, но оставит недопустимый вывод. Однако это не проблема; это обрабатывается определением вычислимой функции , а именно, полная функция f от натуральных чисел вычислима, если есть машина Тьюринга, которая, всякий раз, когда ей дается вход n в правильной форме, выдает правильную форму для f ( n ) на ленте, а затем останавливается с головкой на левом краю ответа. И наоборот, любая машина Тьюринга вычисляет уникальную частичную функцию. Областью определения функции является множество n , которые заставляют машину завершать работу с выходом в правильной форме (поэтому неправильно сформированный выход просто означает, что функция не определена для этого входа). Вот почему важны соглашения о входе/выходе — потому что они являются неотъемлемой частью определения вычислимой функции. Не существует понятия машины, вычисляющей неправильную функцию; если вам нужна другая вычислимая функция, вы выбираете другую машину. CMummert 17:34, 25 июля 2006 (UTC) [ ответить ]

Для CMummert : Ваши "стандартные" соглашения по вводу-выводу не используются только тогда, когда набор инструкций не содержит "write 0". В основной статье "модель Вана" относится к его большему набору инструкций, который действительно включает "write 0". Я предлагаю, чтобы в основной статье просто не упоминался косвенный факт, что полнота по Тьюрингу возможна с меньшими наборами инструкций, ввиду отвлечения внимания, которое это, по-видимому, вызвало. Должно быть очевидно, что набор из шести инструкций достаточен для моделирования любой машины Тьюринга в современном смысле (например, аля Клини), используя только стандартные соглашения по вводу-выводу. --res ( Talk ) 18:42, 25 июля 2006 (UTC) [ ответить ]

Я предложу еще одну идею (согласно более раннему предложению CMummert): в духе упрощения основных статей создайте еще одну статью — возможно, назовите ее «Машина Вана» — как еще один пример машин, «эквивалентных Тьюрингу». (Кибербумага дешева, ни один ум не пострадает...).wvbailey

Причина в следующем: я пытался нарисовать "машину Тьюринга" как "механическое приспособление" с бумажной лентой и индексирующим "тракторным колесом", похожим на старомодный телетайп с бумажной лентой или 35-миллиметровую пленку с ее квадратными индексирующими отверстиями. Но снова и снова я сталкиваюсь с проблемой: "СТИРАНИЕ" и "ПЕЧАТЬ НАД ПЕЧАТЬЮ" как практически невозможные для реализации с реальными механическими объектами (исчезающие чернила - одна из возможностей, какой-то вид ластика-колеса - другая). Есть много способов сделать это, если бы мы двигали что-то - например, шарик, ползунковый переключатель - вперед и назад в последовательности лотков-как-ленты, но это не в духе Тьюринга стираемых, перепечатываемых символов на бумажной ленте.wvbailey

Идея о том, что машина, эквивалентная Тьюрингу, может существовать идентично телетайпу, за исключением того, что «телетайп Ван-Тьюринга» способен менять направление ленты на противоположное — я действительно думаю, что видел такую ​​ленту с реверсом на некоторых ранних компьютерах (я знаю, что машины с магнитной лентой делают это) — (для меня) увлекательна. Это очень упрощает «конструкцию» «машины Тьюринга» — телетайп просто меняет свое движение, чтобы найти нужный «квадрат», и пробивает еще одно отверстие в ленте. (Ну и что, если длина ленты составляет 186 000 миль? А расчет занимает 14,7 лет?) Пока вы и я можем спорить: «Кого, черт возьми, это волнует?» (очевидно, Ван и Мински это сделали, и мы достаточно обеспокоены, чтобы потратить время на написание этого) — мы никогда не узнаем, какой будущий ум может быть вдохновлен таким удивительным доказательством.wvbailey Wvbailey 19:59, 25 июля 2006 (UTC) [ ответить ]

На самом деле, я думаю, что модель Вана относится к настоящей статье даже больше, чем модели Дэвиса, поскольку модели Дэвиса появились после модели Вана и по сути дублировали ее. (На мой взгляд, неявное или явное использование инструкции «стоп» не имеет большого значения в этом отношении.) Хотя возможно, что эта модель также может найти место в какой-то другой статье с другим тематическим акцентом, я настороженно отношусь к вашему подходу «кибербумага дешева». Кстати, «машина W» — это название модели, которую мы обсуждаем, которое дал Ванг («машина B» — так он назвал нестирающую версию). --res ( Talk ) 21:11, 25 июля 2006 (UTC) [ ответить ]

Я не уверен, что могу придираться к вам по этому поводу; мне нужно будет перечитать модель Вана еще раз (у меня нет копии, как указано выше); кроме того, Дэвис более широко опубликован, чем Ванг. Но см. мое замечание сразу ниже о Клини. Все эти ребята (Пост, Клини, Ванг, Дэвис, Мински, даже Чайтин) знали друг друга (я думаю, все пересекались в Институте Куранта Нью-Йоркского университета в то или иное время, либо как студенты, либо как профессора), поэтому я не удивлен, что их модели похожи. В своем предложении я имел в виду создание новой страницы о "модели Вана без стирания (Print 0)". Если вы этого не сделаете, я могу просто сделать это сам; т. е. расширить Википедию: Будьте смелее в обновлении страниц до их создания. wvbailey Wvbailey 23:53, 25 июля 2006 (UTC) [ ответить ]

На самом деле Стивен К. Клини (1952) опередил и Вана примерно на год, и Дэвиса на милю. Если вы сможете найти копию его «Введения в метаматематику» , издательство North-Holland Publishing Company, первое издание 1952 года, я думаю, вы будете поражены, как и я. Я предполагаю, что это источник всех последующих моделей пост-Тьюринга. Меня на этот источник навел сам Мартин Дэвис. (Хотя он признает, что придумал фразу «проблема остановки», он приписывает доказательства Клини в этой книге и, в конечном счете, второму доказательству Тьюринга. После некоторых раздумий я вынужден с ним согласиться.) Серьезно, посмотрите, сможете ли вы получить копию, и внимательно прочитайте главу XIII «Вычислимые функции», стр. 356 и далее. Обратите внимание на его модель в частности («Предположим, что символ S1 на самом деле является меткой '|'» и т. д.) wvbailey Wvbailey 23:27, 25 июля 2006 (UTC) [ ответить ]

Введение в метаматематику Клини , особенно глава "Вычислимые функции", действительно произвела на меня впечатление (я прочитал ее около года назад) — как можно увидеть в моих правках к статье "Проблема остановки" . Но пара замечаний о модели Клини, возможно, будет уместна в контексте настоящей статьи:

• В отличие от модели Поста (и Вана), машины Клини не используют строго двоичный алфавит — ввод/вывод использует двоичный алфавит, но в ходе вычислений допускаются другие вспомогательные символы ленты. (стр. 360)

Вы правы относительно "... другие [символы] могут использоваться в вычислениях"; однако в его примере использования | и пробела, который распространяется на всю главу (стр. 356-386), он использует только | и пробел; никаких других символов на его ленте не появляется, за исключением стр. 381, где он допустил утечку 2.wvbailey Wvbailey 15:24, 26 июля 2006 (UTC) [ ответить ]

Я поправил себя в вопросе о том, требовала ли модель Клини чего-либо, кроме строго двоичного ленточного алфавита. После того, как он сначала определил «вычислимость» таким образом, что ленточный алфавит не был строго двоичным, он переходит к определению «1/1-вычислимости» таким образом, что она была строго двоичной («1/1» относится к односторонней бесконечной ленте, 1 символ, отличный от пробела). Мои извинения — путаница была моей. --res ( Talk ) 21:44, 26 июля 2006 (UTC) [ ответить ]

• В отличие от модели Поста (и Вана), машины Клини, по замыслу, имеют базовую структуру машин Тьюринга — с «логикой», воплощенной в таблице переходов состояний, практически идентичной Тьюрингу (хотя с явным «состоянием остановки»). В то время как таблицы переходов Тьюринга были списками пятерок вида (q, s, s',d',q'), у Клини записи (s',d',q') для каждого (q,s) как (row,col) — по сути одно и то же. Хотя таблицу переходов можно (современным взглядом) рассматривать как своего рода «программу», следует, что модель не является «программной формулировкой» почти в том же смысле, что и у Поста и Вана. (На мой взгляд, трудно не рассматривать Формулировку 1 Поста как ранний язык программирования.)

wvbailey здесь: Клини выражается ясно: «Наша трактовка здесь в некоторых отношениях ближе к Post 1936. Post 1936 рассматривал вычисления с 2-сторонней бесконечной лентой и только 1 символом» (стр. 261, первый абзац). Затем на стр. 379 он делает следующее замечание:

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

Я полагаю, что то, о чем вы говорите выше, это то, что я заметил в заявлении Клини — что машина модели Поста (2 «операции» на строку таблицы состояний) больше «атомизирует» действия машины, чем модель Тьюринга (3 «операции» на строку таблицы). Очевидно, что это различие является фундаментальным для модели Поста.wvbailey Wvbailey 15:29, 26 июля 2006 (UTC) [ ответить ]

Модель Клини, несомненно, оказала важное влияние на формирование современной формулировки ТМ и вычислений ТМ, которые завершаются. --res ( Обсуждение ) 04:53, 26 июля 2006 (UTC) [ ответить ]

Вместо того, чтобы придираться, мы могли бы вынести из обсуждения и включить в статью (у нас есть множество проверяемых подтверждений в приведенных выше цитатах из Клини) сильное различие между TM и PT — (i) добавление HALT/STOP, (ii) дальнейшее дробление инструкций за пределами модели Тьюринга, (iii) возможно — и я не уверен здесь — понятие последовательных инструкций с исключительным тестом+ветвлением как особым типом инструкций, что дает следующие 7 инструкций, выполняемых последовательно { R, L, E, P, Jb,xxx, Jm,xxx, H } [или любые другие сокращения, которые вы захотите выбрать]. Вот как я построил свою маленькую модель из КМОП-материалов — я использовал заклинивающий/загружаемый счетчик в качестве «регистра состояний», также известного как «счетчик программ». Однако совсем недавно я обнаружил, что при моделировании модели Post в электронной таблице версию конечного автомата (каждая инструкция сопровождается тестом+ветвью) «построить» гораздо проще.

Что касается последнего (iii), по вашему мнению, Ван и/или Пост явно утверждают последовательное выполнение инструкций? Я говорю, что мы должны выследить это и пригвоздить это — т.е. есть ли цитаты, подтверждающие это утверждение? Это интересно, и я согласен с вами, что в своей окончательной форме модель PT представляет собой примитивный язык программирования. (Дэвис утверждает последовательное выполнение, в некоторых своих поздних работах).wvbailey Wvbailey 15:24, 26 июля 2006 (UTC) [ ответить ]

В обеих моделях — Поста и Вана — инструкции нумеруются последовательными положительными целыми числами, а под «последовательным выполнением» я подразумеваю, что инструкция i+1 выполняется следующей после инструкции i:

• В формулировке Поста 1 каждая инструкция («направление») содержит номер инструкции, которая должна быть выполнена следующей (за исключением, конечно, Stop) — и это может быть любая инструкция в программе — поэтому выполнение, как правило, не является последовательным.
• В программе Ванга выполнение последовательное -- за исключением, очевидно, случаев, когда ветвление происходит из-за условной инструкции "goto". Соответствующий материал для цитирования находится на стр. 64-65. --res ( Talk ) 20:57, 26 июля 2006 (UTC) [ ответить ]

Это хорошие новости. Я считаю, что мы могли бы переработать статью, чтобы сжать ее в одну "компьютерную" модель, которая включает остановку, последовательное выполнение инструкций, две "операции" на "машинный цикл" и использование одного символа плюс пробел на двусторонней ленте. Мысли? У вас есть копия Вана в формате pdf? Я специально сходил в библиотеку (за этим и за Марковым на странице алгоритма), но они все облажались и не смогли получить статью из своих электронных архивов (гррр -- все же нашел Маркова :-) . wvbailey Wvbailey 22:01, 26 июля 2006 (UTC) [ ответить ]

Конечно, это не место для публикации оригинальной работы, что, как мне кажется, и звучит в вашей предложенной сжатой «единой „компьютерной“ модели». Как я вижу, по сути, обсуждаются только два типа вычислительных моделей — те, которые по сути являются формулировками программ (Пост, Ван, ...) и те, которые таковыми не являются (Тьюринг, Клини, ...). Есть некоторое совпадение, но для меня достаточно различий, чтобы сосредоточить статью на Формулировке 1 Поста и тесно связанных формулировках программ, которые можно рассматривать как производные от нее. Модель Клини не относится к статье, имхо, потому что она гораздо ближе к тому, что считается «современной» формулировкой машин Тьюринга. (По моему мнению, именно аспект «формулировки программ» в моделях дает основное обоснование того, чтобы не объединять статью со статьей о машинах Тьюринга.) О доступе к статье Вана (и другим) ... Как и вы, я полагаюсь на университетскую библиотеку и имею только печатную копию избранных разделов. --res ( Обсуждение ) 01:03, 27 июля 2006 (UTC) [ ответить ]

Я не согласен с вашим беспокойством по поводу "формулировки программы". Ваше (подразумеваемое) определение "программы" как пронумерованного последовательного набора машинных команд подозрительно/спорно и неверно по мнению некоторых авторов. Например, более навороченные TI DSP, которые могут выполнять более одной инструкции в "цикле инструкций". Или следующее определение:

«Алгоритм для машины Тьюринга состоит из набора из пяти кортежей, таких, что для каждой пары состояние-символ, за исключением состояния HALT, существует ровно один пятикортеж. Такой алгоритм известен как программа машины Тьюринга : (курсив в оригинале, стр. 9 в книге Гарольда С. Стоуна « Введение в организацию компьютеров и структуры данных» , McGraw-Hill Book Company, 1972)

Термин «программная формулировка» принадлежит Вангу, который назвал эту модель «программной формулировкой машин Тьюринга». Кажется вероятным, что некоторые более поздние авторы также переформулировали ТМ в терминах программ, во многом благодаря (косвенно) оригинальному примеру Вана. Но ISTM, что настоящая статья лучше всего ограничена программными формулировками, которые очень близки к Посту и Вангу (и Дэвису, который, по-видимому, принял/адаптировал модель Вана). --res ( Talk ) 02:49, 28 июля 2006 (UTC) [ ответить ]

Оригинальное исследование RE: Модель PT значима, поскольку она более «атомарна», чем модель Тьюринга, включает HALT и, как бонус, (иногда) представлена ​​как последовательность серий пронумерованных инструкций в стиле фон Неймана. Мой критерий выбора: победителем оказывается наиболее удаленная от модели Тьюринга, но все еще соответствующая духу модели Поста. Поскольку название было дано Дэвисом и использовано им по крайней мере один раз в литературе, по всем правилам его модель должна быть «предпоследней», какой бы она ни была. Я мог бы спросить его, каковы были его намерения, но его ответ был бы неопубликованным и неизменяемым, и бла-бла-бла.

Вероятно, под "моделью PT" вы подразумеваете те, которые так называет Дэвис. Та, что с пронумерованными инструкциями, по-видимому, взята из Wang (1954/7), а другая, по-видимому, является тривиальной адаптацией к маркированным (а не пронумерованным) инструкциям. Есть ли более ранняя публикация Davis такой модели? Если нет, то статья в энциклопедии должна отдать должное, где это необходимо -- imo, она будет описана как модель Wang, популяризированная Davis, или что-то в этом роде. --res ( Talk ) 02:49, 28 июля 2006 (UTC) [ ответить ]

Меня беспокоит то, что когда кто-то говорит о пост-Тьюринговой машине, о чем он говорит? Об одной из трех возможных моделей PT #1, #2 или #3? Я бы хотел, чтобы появилась только одна модель, потому что тогда слова «пост-Тьюринговая машина» становятся однозначными. Ну и что, если мы согласимся определить ее определенным образом? Это не оригинальное исследование. Если модель Вана на самом деле является «сжатой версией, то есть предпоследней моделью», и мы согласны — и особенно если она совпадает с названной моделью Дэвиса — то это та модель, которую я предлагаю использовать. Мы оставим другие для исторического, эволюционного интереса. wvbailey Wvbailey 22:40, 27 июля 2006 (UTC) [ ответить ]

Пост представил свою Формулировку 1 (1936), Ван представил очень похожую, но более простую «программную формулировку машин Тьюринга» (1954/7), а Дэвис популяризировал варианты модели Вана, назвав их «Пост-машинами Тьюринга» (197?). Если это историческая прогрессия, я не вижу никаких проблем в том, чтобы статья обсуждала ее таким образом.

1974. Вторая модель, которую он назвал моделью Тьюринга-Пост , появилась в "популярной" литературе (т.е. в неспециализированной форме) в 1980 году [см. ссылки]. В этом и заключается источник трудности, по моему мнению. Дэвис написал еще одну книгу в середине 50-х, которую мне тоже нужно прочитать. wvbailey

Насколько я понимаю, вы приписали Дэвису термин «Пост-Тьюринговая машина»; поэтому ваши опасения по поводу того, что означает этот термин, безусловно, необоснованны. «Когда кто-то говорит о пост-Тьюринговой машине», он, несомненно, должен иметь в виду одну из тех машин, которые Дэвис популяризировал под этим названием. В статье энциклопедии мы не имеем права придумывать что-то еще (например, «сжатую версию»). --res ( Обсуждение ) 02:49, 28 июля 2006 (UTC) [ ответить ]

О, какая ирония, мы уже сделали это дело. Когда вы гуглите «машина Пост-Тьюринга» [даже без кавычек], что вы получаете? Мы уже определили фразу, хотя и неоднозначно, для всех ученых на все времена [или пока мы не передумаем]. Если я не ошибаюсь, любой, кто пишет словарь, находит текущее использование слов и в конечном итоге определяет их в соответствии с общепринятым/принятым использованием — вики также является словарем. (Я посмотрю некоторые из использования и посмотрю, что они определяют). Я не называю это оригинальным исследованием. Я считаю, что вы и я согласны — что модель представляет собой семь инструкций, 2 действия на инструкцию, последовательно пронумерованные инструкции, которые выполняются последовательно, пока не произойдет ветвь. Если я ошибаюсь относительно вашей концепции этой модели, дайте мне знать. Я снова изучу монографию Дэвиса (редкая находка в библиотеке, так что мне нужно туда зайти; если я смогу найти Вана в формате PDF, я сделаю это и отправлю вам копию) и посмотрю, действительно ли Дэвис 1974 ясно говорит об этой модели. Wvbailey 15:14, 28 июля 2006 (UTC)wvbailey [ ответить ]

За исключением нескольких небольших оговорок, я думаю, что это справедливое резюме модели s (насколько мне известно). Во-первых, я предполагаю, что под «2 действиями на инструкцию» вы подразумеваете, что первое действие — это «запись», «сдвиг» или «тест», а второе действие — это передача управления (явная или неявная) инструкции, которая будет выполнена следующей. Во-вторых, типы инструкций для машины Вана W — «запись 1», «запись 0», «сдвиг влево», «сдвиг вправо» и «если 1, то перейти к k») — условная «если 0, то перейти к k» и безусловная «перейти к k» являются необязательными — поэтому все эти инструкции соответствуют вашему описанию «2 действия на инструкцию», за исключением безусловной goto (только nit, потому что она совершенно необязательна, заменяемая парой условных goto). В-третьих, во всех программах Вана Stop существует только неявно, как эффект любой попытки передачи на номер инструкции, которого нет в программе. Наконец, я бы посчитал несущественным изменением использование номеров/меток инструкций (как мог бы сделать Дэвис?) только для инструкций, на которые фактически ссылается некий явный goto — при естественном предположении, что инструкции в остальном написаны в предполагаемой последовательности. --res ( Обсуждение ) 00:03, 29 июля 2006 (UTC) [ ответить ]

Думаю, мы согласны, но мне нужно уточнение по поводу goto. Я использовал обе пары goto, то есть { "If 'mark' goto xxx", "goto xxx" } и другую пару { "If 'mark' goto xxx", "If blank goto xxx" } и, как вы заметили, этот выбор - гнида. Что касается вашего замечания о метках инструкций, я немного запутался и нуждаюсь в вашем разъяснении.... Мы можем либо (i) сформировать goto так, чтобы они были относительными к текущей инструкции — при столкновении с успешным тестом «центральное управление» должно «считать назад» или «считать вперед» (или использовать сумматор плюс регистр состояния) смещение, как предписано числом в инструкции goto (аналогично инструкции «перехода» в микроконтроллерах Motorola, таких как MC68HC05) — таким образом, как указать «отрицательное» смещение, становится интересной проблемой (двоичное смещение?), или (ii) как абсолютное , как в «имея фиксированную метку». Я всегда делал (ii) в своей работе из-за проблемы, как указать «отрицательное» смещение (т. е. перейти назад на -3 инструкции); плюс, кажется, требуется третий тип перехода: (if 'mark' jump_forward xxx, if 'mark' jump_back xxx, goto xxx }. Какой вариант вы предлагаете? Все мои разработки (т. е. с использованием варианта (ii)), построенные с использованием КМОП или в виде модели электронной таблицы, требовали явных меток для каждой инструкции. "Центральное управление, также известное как таблица инструкций, также известная как ОЗУ", должно выслеживать метку "следующей инструкции" с совпадением с номером в регистре состояний — обычно с помощью параллельного "совпадения"). Дайте мне знать, что вы предлагаете. wvbailey Wvbailey 14:50, 29 июля 2006 (UTC) [ ответить ]

Извините, если я не ясно выразился: я не предлагал никаких новых вариантов, поэтому я попытался вместо этого подчеркнуть идею простого обобщения тех чрезвычайно похожих моделей , которые уже есть в статье. Проблемы «реализации», о которых вы упомянули, кажутся мне несущественными, поскольку мы говорим об абстрактных теоретических моделях вычислений. По моему скромному мнению, основное внимание следует уделить « каковы модели, известные в литературе как «машины после Тьюринга » (или важные предшественники, настолько близкие к ним, что заслуживают упоминания), и, возможно, дать хорошее резюме по ним — но определенно не описывать еще один наш собственный вариант. --4.232.96.249 00:57, 30 июля 2006 (UTC) [ ответить ]

Я должен согласиться с вами. Но вы должны простить мой ум — всегда устремляющийся к «реализации» — как бы я построил эту штуку. Я инженер, так что я ультраконструктивист: парень типа «Если мы не можем построить это из липкой жижи, то этого не существует», худший кошмар абстрактного математика. RE Пост-Тьюринговые машины У меня действительно есть «вентильно-эквивалентная» модель в голове — я мог бы нарисовать ее в вентилях NAND и т. д. в короткие сроки. И моей модели требуется куча «вентилей» для декодирования каждого адреса каждой возможной «следующей инструкции» (т. е. ОЗУ с декодерами адресов столбцов и строк). Ирония в том, что мне было бы легче нарисовать эту штуку, чем пытаться ее описать. Но в любом случае... я понимаю/уважаю необходимость абстрактного моделирования, правда... и я согласен с вами, что мы должны представить все варианты моделей... (Мне нужно снова прочитать Вана, но если он оправдает мои ожидания, то он "da man", теперь, когда у Дэвиса в 58-м не было посттьюринговской модели или ссылок на Вана (вероятно, тогда он был студентом), см. ниже жирным шрифтом). wvbailey Wvbailey 03:40, 30 июля 2006 (UTC) [ ответить ]

Интересные факты о библиотечном сыске: пока я был в библиотеке, я заглянул в книги Дэвиса (все три книги стоят на полке одна за другой — «полка» действительно короткая, всего несколько типов теории рекурсии»). Первая книга — его лекции в Институте Куранта, в которых определяются посттьюринговские «программы», третья — «Неразрешимое» (у меня есть личная копия, я ее храню). Но вторая — его «Вычислимость и неразрешимость» 1958 года. Здесь, на стр. 70, появляется первое известное выражение «проблемы остановки». Но Дэвис нигде не упоминает посттьюринговские или тьюринговские (машины или программы), а Хао Ван нигде не появляется .

Дэвис действительно предоставляет хорошую полную версию "программы" умножения машины Тьюринга (и несколько других), используя только знак, пробел и пару других символов. Что касается Fredrick C. Hennie (1977) Introduction to Computability , Hennie даже не упоминает "проблему остановки" (я забыл проверить его относительно Вана. Minsky (1967) действительно дает Hao Wang 5 ссылок в своем индексе, ПЛЮС наш Wang (1957) в качестве источника). Hennie предоставляет очень хорошую часть относительно универсальной машины Тьюринга, стр. 90-103 -- примеры и блок-схема, но нет фактического кода. Я видел весь код Тьюринга только в одном месте -- Roger Penrose, The Emporer's New Mind , стр. 56-57. Никогда не видел версию, использующую пост-Тьюринговский код (я делал это, но, как ни печально, это "ИЛИ"). Вы видели опубликованный пост-Тьюринговский код U-машины? wvbailey Wvbailey 03:40, 30 июля 2006 (UTC) [ ответить ]

Моя первая мысль заключается в том, что поскольку любую двоичную ленту TM в стандартной форме 5-кортежа очень легко переписать как машину PT (просто переведя каждую пару состояний из 5-кортежей в соответствующим образом пронумерованные инструкции), любая из UTM такого рода в литературе может быть обработана таким образом. Например, опубликованная Рогожиным имеет только 24 состояния. --res ( Обсуждение ) 08:49, 30 июля 2006 (UTC) [ ответить ]

Вопрос: ниже инструкция 7 — это безусловный переход к инструкции 8, аналогично инструкция 21 — это безусловный переход к инструкции 22. Переход к следующей инструкции кажется ненужным, так как это часть определения, не так ли? Или такой переход считается невыполняемой инструкцией, но тогда зачем нам это нужно? pmuet 15 августа 2006 г.

Вы абсолютно правы, задавая этот вопрос. Поскольку модель PT может идти последовательно, иногда безусловный переход — это просто пустая трата инструкции (отсюда nop). Но это указывает на то, почему модель Post-Turing отличается от модели машины Тьюринга...

Что я сделал, чтобы быть доскональным, так это превратил "3-state busy beaver" в набор из семи инструкций Post-Turing с своего рода механическим/бездумным "алгоритмом", который всегда заканчивается безусловными переходами (условный переход идет в начале, как в модели Тьюринга). На странице статьи я поднял этот вопрос с примером подпрограммы "стирания ленты" в конце busy beaver. Надеюсь, это объяснение поможет. Если нет, дайте мне знать. Вы указали на возможный источник путаницы, спасибо.wvbailey Wvbailey 20:54, 15 августа 2006 (UTC) [ ответить ]

Я понимаю. Использование этого (простого) алгоритма имеет приятный эффект, позволяя упорядочивать исходные T-состояния в любом порядке в модели PT.

Да, я об этом не думал. Но это правда. Состояния конечного автомата не обязательно должны быть упорядочены. Должно быть указано только начальное состояние.wvbailey Wvbailey 21:41, 17 августа 2006 (UTC) [ ответить ]

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

Правда.wvbailey Wvbailey 21:41, 17 августа 2006 (UTC) [ ответить ]

Это также имело бы преимущество в том, что можно было бы включать несколько начальных состояний (звучит как противоречие, я знаю) в "программу" ПТ, что заставило бы ее вести себя по-разному в зависимости от того, какое состояние было перенесено первым. Действительно, довольно интересно. pmuet 17 августа 2006 г.

Это всего лишь тест макроса, который преобразует таблицы Excel в вики-таблицы. Он сработал! Переход от машины Тьюринга к пост-Тьюринговой машине — это простое, примитивное преобразование — каждое состояние BB (инструкция Тьюринга) преобразуется в начальный условный переход, затем в 3 инструкции для случая «0» и три для случая «1», в общей сложности 1+2x3 инструкции на состояние BB. Таким образом, мы ожидаем ~21 (3 x 7) всего инструкций в BB с 3 состояниями. Но для финального HALT требуется на одну меньше, в общей сложности 20 инструкций PT. Если нам нужно использовать только условные переходы, то безусловный переход заканчивается двумя переходами (например: J,15 = J0,15, за которыми следует J1,15).

Таблица состояний ( таблица переходов , таблица инструкций) для машины Тьюринга нарисована в соответствии с инженерным соглашением (состояния внизу слева, различные входы нарисованы наверху) (ср. Peterson, McClusky (1965) и т. д.). Это расходится с некоторыми (ранними?) математическими соглашениями, например Mirsky (1968)), где таблицы повернуты так, что символы находятся внизу слева, а следующее состояние — наверху. Обратите внимание, что версия таблицы Post-Turing в виде электронной таблицы чем-то похожа на это неинженерное соглашение.

Это соглашение для таблицы состояний соответствует соглашению, используемому на странице Busy Beaver :

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

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

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

wvbailey Wvbailey 20:39, 2 августа 2006 (UTC) [ ответить ]

Таблица состояний для машины Тьюринга с двумя состояниями. Инструкция «Печать» записывает 1, инструкция «Стирание» записывает 0. Лента движется «влево» или «вправо» (т. е. «головка» неподвижна).

Инструкции для пост-тьюринговской версии 2-стабильного занятого бобра, за которыми следует "запуск" эквивалента PT. Как показано на этом рисунке, ни "Стереть", ни "Перейти, если символ ленты равен 0" не используются занятым бобром:

Ниже приведен двухстадийный занятый бобёр Тьюринга с дополнительными инструкциями 15-20 для демонстрации использования «Стирания», J0 и т. д. Они сотрут единицы, записанные занятым бобёром:

Дополнительные инструкции Пост-Тьюринга с 15 по 20 стирают символы, созданные занятым бобром. Они более "эффективны" — для выполнения той же задачи машине Пост-Тьюринга (обычно) потребуется меньше состояний Пост-Тьюринга, чем машине Тьюринга, просто преобразованной с 7 эквивалентными состояниями Пост-Тьюринга на состояние Тьюринга; переход (скачок) может произойти в любое "подсостояние" (например, P, E, L, R) внутри состояния Тьюринга, возможна группировка инструкций перемещения, таких как L, L, L, P и т. д.:

wvbailey Wvbailey 14:05, 2 августа 2006 (UTC) [ ответить ]

На рисунке «Algorithm_P-T_multiply_2.JPG» отсутствует «P» там, где он «ремонтирует» пустой маркер в «b» после увеличения «c». Nl 2304 (обсуждение) 10:07, 8 апреля 2013 (UTC) [ ответить ]

Нашел файл (2006!), исправил изображение, загрузил исправленную проблему. Будем надеяться, что это будет успешно. Bill Wvbailey ( talk ) 15:22, 8 апреля 2013 (UTC) [ ответить ]

День спустя, а файл все еще не является последним, исправленным (текущим) изображением. Билл Увбейли ( обсуждение ) 14:03, 9 апреля 2013 (UTC) [ ответить ]