Если абстрактная машина может симулировать себя, делает ли это Тьюринг завершенным?

20

Например, в языках программирования обычно пишут компилятор / интерпретатор X-in-X, но на более общем уровне многие известные системы с полным набором Тьюринга могут имитировать себя впечатляющими способами (например, симуляция игры жизни Конвея в игре жизни Конвея). ).

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

Джереми Кун
источник
3
Прежде чем я попытаюсь ответить, можете ли вы быть более конкретным, что вы подразумеваете под «логическая система может симулировать себя»? Вы имеете в виду что-то вроде «может кодировать свой синтаксис и доказуемость»?
Андрей Бауэр
4
Что именно вы подразумеваете под «симуляцией»? В частности, как вы определяете симуляцию так, чтобы она все еще имела смысл, например, в контексте Игры Жизни, но не делает вопрос совершенно тривиальным (например, машина, которая ничего не делает, моделирует машину, которая ничего не делает)?
Юкка Суомела
5
Кросспост
Рафаэль
1
Бин, одновременная перекрестная публикация настоятельно не рекомендуется, пожалуйста, ознакомьтесь с практикой . PS: я не уверен, если этот вопрос по теме по cstheory, пожалуйста, также проверьте FAQ, чтобы понять сферу применения cstheory.
Каве
5
Машина "ничего не делать" может имитировать себя.
Макс

Ответы:

24

Не обязательно. Например, двумерный блочный клеточный автомат с двумя состояниями, в котором клетка становится живой только тогда, когда ее четыре предшественника имеют ровно две соседние живые клетки, может имитировать себя с коэффициентом замедления в два раза и взрывом в два размера, но не известно, что Тьюринг завершен. См . B36 / S125 «2x2» Life-Like Cellular Autoton Натаниэля Джонстона для получения дополнительной информации об этом блочном автомате и о правиле B36 / S125 для окрестности Мура, которое также способно моделировать этот блочный автомат.

Дэвид Эппштейн
источник
Что, если машина имеет некоторую меру сложности? Я думаю, что это не должно быть связано с полнотой по Тьюрингу ...
Джереми Кун
4
Но опять же, упомянутый вами блочный автомат все еще может быть завершен по Тьюрингу. Вы просто говорите, что подтекст не известен, чтобы быть правдой. Не то чтобы это представлял собой контрпример.
Джереми Кун
9
Если рассматривать только состояния блочных автоматов с конечным числом живых ячеек, то при таком ограничении все равно остается возможность имитировать себя таким же образом. Но ограниченный автомат, конечно, не является полным по Тьюрингу, потому что ни один шаблон не может избежать его ограничивающего алмаза, поэтому судьба каждого шаблона может быть определена только за экспоненциальное время.
Дэвид Эппштейн
25

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

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

    Смотри, Дэн Уиллард. Самопроверяющиеся аксиомные системы, теорема о неполноте и соответствующие принципы отражения . Журнал символической логики 66 (2001), стр. 536-596.

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

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

    Казушиге Теруи. Легкая аффинная теория множеств: наивная теория множеств полиномиального времени. Studia Logica, Vol. 77, № 1, с. 9-40, 2004.

    Я думаю, что эта статья более доступна после прочтения следующей статьи Ива Лафона:

    Y. Lafont, Мягкая линейная логика и полиномиальное время , Теоретическая информатика 318 (специальный выпуск о неявной вычислительной сложности) с. 163-180, Elsevier (2004)

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

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

Нил Кришнасвами
источник
1
Я нахожу ваш ответ захватывающим, @Neel. Не могли бы вы предложить хорошую отправную точку для меня, чтобы прочитать о (1) или (2)? Мне немного больше интересно узнать о (1), если это имеет значение.
Аарон Стерлинг
Меня больше интересует (2): насколько мощна эта теория множеств? Это связано с квинианскими "новыми фондами"?
cody
@Neel - Интересный ответ. Я также хотел бы то же самое, что и Аарон, - не могли бы вы предложить хорошую отправную точку для (1). Спасибо
Акаш Кумар
9

Рассмотрим следующую модель машины. Машина с кодом на входе всегда выдает .х 0ix0

Обратите внимание, что любая машина в этой модели является универсальной, так как для всех .MМ ' , хM(M,x)=M(x)=0M,x

Это явно не полный набор, но также и универсальные машины.

Дэвид Харрис
источник
Конечно, играет особой роли и может быть заменено любым неотрицательным целым числом. То есть каждый TM в наборе TM, который вычисляет данную постоянную функцию, универсален для этого набора - даже если этот набор TM не является полным по Тьюрингу. 0
Res
Я дал аналогичный ответ для кросс-поста на Math.SE, который не получил повышенных голосов. :)
Каве
@Kaveh: по иронии судьбы, кажется, что я неправильно оценил этот ответ как предшествующий вашему, и поэтому голосовал, редактировал и комментировал только здесь. Кросспосты могут быть такой болью.
Res
@res, я думаю, что на уровне сайтов создаются разные модели голосования. На math.se даже очень хороший ответ от других пользователей с высокими репутациями здесь не так уж и высоко оценен, поэтому я нахожу это нормальным. :) (Также мой ответ не так ясен и понятен, как ответ Дэвида здесь.)
Каве