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

DM>>1. Вычислимость и теоремя Геделя о неполноте. Компьютер принципиально ограничен вычислимыми функциями, человек же порой решает задачи, которые выглядят невычислимыми (действительно ли они таковы — еще вопрос).

vsb>Пример такой задачи можно? Никогда не решал ни одну задачу, выглядящую невычислимой.

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