Блог

В «Нет серебряной пули» Фред Брукс утверждает, что «Программные системы имеют на порядки больше состояний, чем компьютеры», что усложняет их проектирование и тестирование (а чипы и так довольно сложно тестировать!).

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

Подразумевает ли Брукс какое-то конкретное значение, которое я упускаю? Или у компьютера действительно меньше потенциальных состояний, чем у программных систем, которые он может запускать?

Что ж, давайте сначала подумаем о машинах Тьюринга.

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

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

Чтение описания машины Тьюринга — это то же самое, что чтение программы, хранящейся в памяти.

В этом смысле, если считать за количество состояний аппаратного обеспечения количество состояний в блоке управления, и если программное обеспечение является описанием машины Тьюринга, записанным на ленте, то да, конечное аппаратное обеспечение может имитировать бесконечное программное обеспечение, но программное обеспечение наверняка содержит машины Тьюринга с большим количеством состояний, чем то, которое его имитирует.

Однако, если вы рассматриваете как состояние все состояние вычисления, т. е. включая состояние ленты, то вы правы: каждое моделирование соответствует определенным возможным состояниям в этом смысле, и есть много состояний, которые недействительны или недоступны.

Точно так же современные компьютеры состоят из набора аппаратных средств, которые реализуют этот блок управления, а затем памяти, которая является нашей лентой. Если вы не рассматриваете состояние памяти как часть состояния аппаратного обеспечения, то применимо то же самое: конечный компьютер, при наличии достаточного объема памяти, мог бы выполнять все возможные программы на всех возможных входных данных, однако его управляющие части ограничены.

При этом я бы не стал воспринимать такие утверждения слишком буквально или слишком серьезно… Суть проста: количество состояний в программных системах растет чрезвычайно быстро.