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

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

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

One could argue that a computer with 128 megabytes of memory and a 30 gigabyte disk, has "only" 256301280000000 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.

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

Архив записей в блогах:
Где ты была сегодня, киска?У королевы у английской...Сегодня -  это, конечно, сильное преувеличение. Сегодня я сижу у компа, мучаюсь дурным кашлем, какой можно словить только в такую дикую жару, и пытаюсь высидеть до того момента, когда мне ...
Отечественный БОМЖ демонстрирует чудеса правоприменения и похвальной законопослушности. Сказано "ЗДЕСЬ", он здесь и есть: А находится это " ЗДЕСЬ " там: Кстати, картинка молельного дома дёрнута с сайта: 「 Картинка кликабельна 」 Солярно-Коловратную символику которого ...
Губернатор С-Петербурга Валентина Матвиенко  приняла решение, выдвинуть свою кандидатуру на пост спикера Чем запомнится Валентина Ивановна? Тем,что в ее бытность город находился в состоянии коллапса по крайней мере 2 последние ...
Ожидаемо нынешний понедельник после вчерашнего нереального подъёма, морального, энергетического и другого, вышел совершенно мутным. Но здесь во многом сыграла роль погода: только я успел ночью часа в три уснуть, как разразилась весьма родственная апокалипсису буря; конечно, я проснулся и ...
...