Здравствуйте, D. Mon, Вы писали:

DM>Здравствуйте, vsb, Вы писали:

DM>Если я все правильно путаю, в качестве одного из примеров приводилась задача о замощении: имея несколько плоских фигур, можно ли ими как плиткой замостить всю бесконечную плоскость? Тот же Пенроуз известен тем, что нашел красивые примеры, когда несколькими очень простыми плитками можно замостить всю плоскость, да так, что рисунок получается непериодический (с периодическими все довольно просто и не так интересно). Доказательство невычислимости легко нагугливается по словам "задача о замощении".

А что тут не так? Пенроуз нашел решение для нескольких частных случаев. В общем случае задача алгоритмически неразрешима.

Например, алгоритмически неразрешима проблема остановки машины Тьюринга. Что не мешает мне легко доказать, что следующий код зацикливается:

  for(;;);