Я жду определенного ответа на заглавный вопрос.
Существует ли набор правил, который переводит любую программу в конфигурацию конечных фигур на бесконечной доске, например, если черно-белые играют только легальные ходы, игра заканчивается за конечное время, если программа останавливается?
Правила те же, что и в обычных шахматах, за исключением правила 50 ходов, обменов и рокировки.
И какое минимальное количество различных типов фигур (т. Е. Самой простой игры) необходимо для того, чтобы игра, похожая на шахматы, была завершена на тюринг? (Каждый тип фигуры имеет набор разрешенных ходов, который инвариантен при переводе).
Есть ли какая-то часть, которую мы можем добавить в игру, чтобы доказать, что она завершена?
computability
turing-machines
board-games
halting-problem
recreational
Охотники на троллей
источник
источник
Ответы:
Я также думаю, что очень похожий вопрос задавался ранее, я думаю сначала здесь: /mathpro/27967/decidability-of-chess-on-an-infinite-board/63684 Вот мой обновленный и измененное мнение.
Я думаю, что проблема не решена полностью, но ответ почти наверняка да. У меня нет доказательств для шахмат, так как у меня нет возможности проектировать определенные конфигурации, но я думаю, что они должны существовать. И даже если они этого не делают, для некоторых шахматоподобных игр они, безусловно, делают, что показывает, что попытки доказать разрешимость должны быть неверными. Позже я понял, что здесь есть мой аргумент, очень похожий на мой: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006, но мои доказательства показывают, что на самом деле достаточно двух счетчиков и, возможно, мой более подробно.
Сокращение основывается на понятии стековой машины. Машина стеков, имеющая только два стека и использующая алфавит стека, состоящий только из одной буквы, может имитировать любую машину Тьюринга. (Некоторые люди называют этот детерминированный конечный автомат с двумя счетчиками.) Поэтому нашей целью было бы моделировать любую такую машину с шахматной позицией. Я вижу два пути для этого.
я, Создайте две отдельные конфигурации, так что обе имеют начальную часть и движущуюся часть, которая может изменяться (для сохранения состояния). Кроме того, движущиеся части будут связаны, например. ладьями, которые могли бы поставить мат, если их освободили, поэтому, если один из них перемещает 1, другой должен перемещать k и так далее.
ii. Создайте одну конфигурацию, которая в зависимости от своего состояния перемещает l по горизонтали и -k по вертикали. Кроме того, поместите ладью в (0,0), которая никогда не будет двигаться, но могла бы гарантировать, что конфигурация может «почувствовать», когда она вернется к пустому счетчику.
Таким образом, все, что осталось сделать, - это разработать такие конфигурации, что, я думаю, должно быть возможно с некоторыми усилиями и знанием шахмат. Кроме того, обратите внимание, что в обоих случаях конструкция использует кусок, диапазон которого не ограничен, интересно, действительно ли это необходимо. В качестве первого шага я предложил дать положение, эквивалентное гипотезе Коллатца: /mathpro/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture
источник
Вчера я погуглил, чтобы проверить состояние этой проблемы, и нашел новый (2012) результат:
Дэн Брумлев, Джоэл Дэвид Хэмкинс и Филипп Шлихт. Проблема бесконечных шахмат в мате решаема (2012)
Так что проблема бесконечных шахмат в математике не может быть полной по Тьюрингу.
Разрешимость бесконечных шахмат без каких-либо ограничений на число ходов для мате кажется все еще открытой.
источник