Опираясь на технологии искусственного интеллекта, компьютеры сегодня могут вести убедительные беседы с людьми (спасибо, ChatGPT), сочинять песни, писать картины, играть в шахматы, диагностировать болезни - и это лишь несколько примеров их технологического мастерства.
Эти успехи могут быть восприняты как свидетельство того, что вычисления не имеют границ. Чтобы понять, так ли это, важно понять, что делает компьютер мощным.
Есть два аспекта мощности компьютера: количество операций, которые его аппаратное обеспечение может выполнять в секунду, и эффективность алгоритмов, которые он выполняет. Скорость аппаратного обеспечения ограничена законами физики. Алгоритмы - по сути, наборы инструкций - пишутся людьми и преобразуются в последовательность операций, которые может выполнить компьютерное оборудование. Даже если бы скорость компьютера могла достичь физического предела, вычислительные препятствия остаются из-за ограничений алгоритмов.
К таким препятствиям относятся проблемы, которые невозможно решить на компьютере, и проблемы, которые теоретически решаемы, но на практике находятся за пределами возможностей даже самых мощных версий современных компьютеров. Математики и компьютерщики пытаются определить, является ли проблема решаемой, пробуя ее на воображаемой машине.