Мы ежедневно рассуждаем о компьютерах, но вот простой эксперимент: без поиска по сети ответьте на вопрос «А что такое компьютер?». Обязательно ли нужен кремниевый процессор, чтобы некая штука называлась компьютером? Где граница между компьютерами и калькуляторами, например? В 1936 году на этот вопрос ответил великий Алан Тьюринг. Он описал «машину Тьюринга» — модель того, что можно назвать компьютером. Второе понятие — «полнота по Тьюрингу». Система полна по Тьюрингу, если умеет всё то же, что эта машина, то есть может выполнить любую программу. И вот тут начинается приключение: компьютер можно...