Почему компьютеры не летают

itman — 20.10.2011 Наверное практически каждый из нас сталкивался с ситуацией, когда начальство утверждало, что программирование - это несложная работа, потому что для любой проблемы можно написать программу! Однако, это в корне неверно. Дело в том, что существует только счетное количество программ и несчетное количество задач, для описаний которых можно использовать конечный алфавит. Как несложно видеть, большинство задач - нерешаемо! То, что большая часть практических задач (но далеко не все) действительно можно запрограммировать, - это следствие того, что многие интересные задачи простые и имеют регулярную структуру (вольное изложение Хопкрофта со товарищи)

Для тех, кто любит упрощать (а такие уже отметились в комментариях), Хопкрофт также объясняет, почему неверно считать компьютер конечным автоматом. Тут уж, простите, я не буду заниматься переводов, а процитирую оригинал:

One could argue that a computer with 128 megabytes of memory and a 30 gigabyte disk, has "only" 256^301280000000 states, and is thus a FA. However, treating computers as FA is unproductive. The number of states involved is so large, and the limits so unclear, that you don't draw any useful conclusions. In fact, there is every reason to believe that, if we wanted to, we could expand the set of states of a computer arbitrarily... If we run out of memory, the program can print a request for a human to dismount its disk, store it, and replace it by an empty disk. As time goes on, the computer could print requests to swap among as many disk as the computer needs...
Similar tricks would allow any other program to avoid finite limitations on the size of memory or on the size of integers or other data items.

Оставить комментарий

Популярные посты:

• Архив