Магия: Сбор Тьюринга завершен?

Я знаю, что это очень специфический вопрос, и я сомневаюсь, что на него ответит любой, кто еще не знаком с правилами Магии. Перекрестная публикация на Draw3Cards . Вот исчерпывающие правила игры Magic: The Gathering . Смотрите этот вопрос для получения списка всех магических карт. У меня вопрос - игра Turing Complete?

Для более подробной информации, пожалуйста, смотрите сообщение на Draw3Cards .

Алекс Черчилль (@AlexC) опубликовал решение, которое не требует сотрудничества между игроками, а скорее моделирует полное выполнение универсальной машины Тьюринга с двумя состояниями и 18 символами ленты. Для получения подробной информации см. Https://www.toothycat.net/~hologram/Turing/ [ архив ].

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

Сначала полное описание проблемы с сайта Draw3Cards:

Положительный ответ будет состоять из следующих компонентов:

1. Вычислимая функция fM от машин Тьюринга до упорядоченных волшебных колод (где порядок библиотеки имеет значение)
2. Две четко определенные детерминированные и вычислимые стратегии для игры в Магию (которые не зависят от колоды). Давайте назовем их Стратегия TS (Стратегия Тьюринга) и Стратегия IS (Стратегия ввода).
3. Вычисляемый способ для кодирования любой строки нулей и единиц в качестве колоды Magic Input. Одним из таких способов было бы взять число Гёделя в строке и поместить столько островов во входную колоду.

Дополнительное условие, которое должно быть выполнено, таково: учитывая TM Turing Machines, давайте рассмотрим результат игры Magic между стратегией TS, играющей с колодой fM (TM), против стратегии TI, играющей с колодой fI (I), когда библиотеки не тасуется до начала игры. Эту игру должен выиграть первый игрок, если и только если TM (I) = true.

Итак, вот идея. У нас есть 2 игрока, A и B. B предоставит вход, в то время как A непосредственно реализует машину Тьюринга. Колоды будут состоять почти полностью из земли, но также и из карты Gemstone Array, чтобы уничтожить сжигание маны. А будет иметь 3 типа земель: острова, горы и леса. Основная идея состоит в том, чтобы использовать повернутую землю для представления 1, а неиспользуемую землю для представления 0. Острова будут использоваться для представления состояния ленты, горы - для индексации текущего положения вдоль ленты, а леса - для представления внутреннего состояния 24. символ 2 состояния машины Тьюринга (я считаю, что есть универсальный благодаря Рогожину).

Колоды располагаются следующим образом: колода А: артефакт драгоценного камня; 6 лесов (с плюс дополнительный лес); Для m = 0 до бесконечности: островов, за которыми следуют 1 горы. Обратите внимание, что количество гор (которые могут быть как повернуты, так и нет) всегда является числом, необходимым для индексации каждого острова, плюс состояние остановки.2 м + $2^5 = 32 > 24$$2^{m+1}$

Колода B: артефакт драгоценного камня; 6 лесов (с плюс дополнительный лес); Для m = 0 до бесконечности: Входные земли, за которыми следуют 1 горы. Еще раз обратите внимание, что число гор (которые могут быть повернуты или нет) всегда является числом, требуемым для индексации каждого острова, удерживаемого A, плюс состояние остановки. Входными землями считаются равнины (для представления 0 во входной строке), Болото (для представления 1 во входной строке) и острова (которые используются после достижения конца входной строки.2 м + $2^5 = 32 > 24$$2^{m+1}$

Стратегия: A и B разыгрывают по одной земле за ход в том порядке, в котором они разыгрываются. Когда каждый рисует 4 леса, они играют артефакт драгоценного камня. Примечание А идет первым, поэтому уже имеет Остров, когда Б дро играет свою первую входную карту.

A и B просто продолжают размещать свои карты в порядке, пока B не исчерпает свои Равнины и Болота и не разыграет свой первый Остров. На его следующем пути, A для всех, кого я касаюсь его ih Остров, если Bs ith Входная Земля была болотом. А инициализирует свою машину Тьюринга, нажимая на свои первые Лес и Гору. Если он нажал нечетное количество карт, он нажимает на свой дополнительный форрест и использует всю эту ману, чтобы добавить жетоны в массив драгоценных камней. С этого момента игра продолжается следующим образом: B использует свой ход, чтобы просто отразить состояние маны А. B стучит по i-му входному полю, если i-й остров А повернут. Точно так же B стучит по своему i-му Лесу (Горе), если i-ый Лес (Гора) задействован. Как A всегда выбирает четное количество карт, так и B, и мана используется для добавления жетонов в Gemstone Array.

На ходу А вся мана А становится неиспользованной, поэтому А смотрит на состояние маны Б, представляет состояние маны А на предыдущем ходу. A применяет правило перехода в соответствии с универсальным (24,2) автоматом к состоянию B, чтобы получить его новое состояние.

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

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

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

Алекс Черчилль, Стелла Бидерман и Остин Херрик опубликовали эту статью, показывающую, что магия завершается

Abstract — Magic: The Gathering - популярная и сложная игра в карты о магических боях. В этой статье мы показываем, что оптимальная игра в реальной магии, по крайней мере, так же трудна, как и проблема остановки, решая проблему, которая была открыта в течение десятилетия [1], [10]. Для этого мы представляем методологию для встраивания произвольной машины Тьюринга в игру Магии так, чтобы первый игрок гарантированно выиграл игру, если и только если машина Тьюринга остановится. Наш результат относится к тому, как разыгрывается настоящая Магия, может быть достигнут с использованием стандартных колод для турниров и не зависит от стохастичности или скрытой информации. Наш результат также весьма необычен в том, что все ходы обоих игроков вынуждены в строительстве. Это показывает, что даже распознать, кто выиграет игру, в которой ни один из игроков не принял нетривиальное решение для остальной части игры, невозможно решить. В заключение мы обсудим последствия для единой вычислительной теории игр и замечания по поводу возможности игры на такой доске в турнирных условиях.