Тени разума

13

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

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