Этот вопрос касается того, существуют ли какие-либо известные обратимые тарпиты Тьюринга, где «обратимый» означает в смысле Аксельсена и Глюка , а «тарпит» является гораздо более неформальным понятием (и, возможно, не очень удачным выбором слова), но я сделаю все возможное, чтобы объяснить, что я имею в виду под этим.
Что я имею в виду под "брезентом"
Некоторые модели вычислений предназначены для некоторого использования. Другие просто оказываются завершенными по Тьюрингу и не обладают какими-либо особенно полезными свойствами; они известны как "брезенты Тьюринга". Примеры включают в себя язык Brainfuck , клеточный автомат Rule 110 и язык Bitwise Cyclic Tag (который мне нравится, потому что он очень прост в реализации и любая двоичная строка является допустимой программой).
Формального определения термина "Тьюринг Тарпита" не существует, но для этого вопроса я использую его для обозначения довольно простой системы (с точки зрения наличия небольшого числа "правил"), которая "просто случается" является завершенной по Тьюрингу, без его внутреннее состояние, имеющее очевидный смысловой смысл. Наиболее важным аспектом для моих целей является простота правил, а не отсутствие очевидной семантики. По сути, мы говорим о вещах, о которых Стивен Вольфрам однажды написал очень большую книгу , хотя он не использовал слово «тарпит».
Что я имею в виду под «обратимым»
Я заинтересован в обратимом вычислении. В частности, мне интересны языки, которые полны по r-Тьюрингу, в смысле Аксельсена и Глюк , что означает, что они могут вычислять каждую вычислимую инъективную функцию и могут вычислять только инъективные функции. В настоящее время существует много моделей вычислений, которые обратимы в этом смысле, например , обратимая универсальная машина Тьюринга Аксельсена или обратимый язык высокого уровня Януса . (Есть много других примеров в литературе; это активная область исследований.)
Следует отметить, что определение полноты r-Тьюринга Аксельсеном и Глюком представляет собой иной подход к обратимым вычислениям, чем обычный подход из-за Беннетта. В подходе Беннетта системе разрешено производить «мусорные данные», которые выбрасываются в конце вычислений; в таких условиях обратимая система может быть завершена по Тьюрингу. Однако в подходе Аксельсена и Глюка система не может создавать такие «ненужные данные», что ограничивает класс задач, которые она может вычислять. (Следовательно, «полная Т-Тьюринга», а не «Тьюринга завершена».)
Примечание: бумага Аксельсена и Глюка находится за платным экраном. Это прискорбно - насколько мне известно, в настоящее время нет ни одного неоплачиваемого ресурса по полноте r-Turing. Я постараюсь открыть страницу Википедии, если у меня есть время, но без обещаний.
Что я ищу
Упомянутые выше примеры обратимых вычислений все "семантически загружены". Это хорошо в большинстве случаев, но это означает, что правила, необходимые для обновления их состояния на каждом временном шаге, довольно сложны. Я ищу "брезенты" обратимых вычислений. То есть более или менее произвольные системы с довольно простыми правилами, которые «просто случаются», являются полными языками Т-Тьюринга. Я повторяю, что нет формального определения того, что я ищу, но я узнаю об этом, когда увижу это, и я думаю, что это разумный вопрос.
Есть ряд вещей, о которых я знаю, которые почти соответствуют всем требованиям, но не совсем. Существует несколько обратимых клеточных автоматов, которые, как было показано, являются полными по Тьюрингу. Муравей Лэнгтона (своего рода двумерная машина Тьюринга с довольно произвольной и довольно простой обратимой функцией перехода состояний) также является полным по Тьюрингу, если его начальные условия могут содержать бесконечные повторяющиеся структуры. Тем не менее, в этих системах нетривиально определить отображение из их состояния в «вывод» таким образом, чтобы никакие ненужные данные не выбрасывались. Меня особенно интересуют системы, о которых можно думать, что они принимают входные данные, выполняют на нем некоторую последовательность (обратимых) преобразований, а затем (если они завершаются) возвращают некоторый выходной результат.
(Я надеюсь, что на этот вопрос будет легче ответить, чем на мой предыдущий вопрос об обратимом эквиваленте лямбда-исчисления.)
Ответы:
«r-complete», по-видимому, является относительно новой концепцией, изобретенной Аксельсеном и Glück ~ 2011, и, возможно, ее авторы не слишком много думают, и задаются вопросом, существует ли доказательство, отличное от полного Тьюринга.
я беру этот многословный и окольный вопрос, чтобы спросить в основном:
попробуйте Тьюринг-полный обратимый клеточный автомат, например:
Двухсторонние, обратимые, универсальные клеточные автоматы в трехмерном пространстве Миллер / Фредкин
К. Имаи и К. Морита, универсальный для вычислений двумерный треугольный обратимый клеточный автомат с 8 состояниями, Теоретическая информатика 231 (2000), №. 2, 181–191.
это было найдено в качестве ссылки в этом обзоре CA, который может иметь другие полезные сведения в запросе (например, см. раздел 7 «Обратимость и универсальность»). (в 17 pgs & 86 refs название граничит с иронией.)
УНИВЕРСИТЕТЫ ПО ОБЗОРУ КЛЕТОЧНЫХ АВТОМАТОВ А (КОРОТКИЙ) Ollinger
источник