Полная и вычислительная мощность Тьюринга

В одной из лекций профессор упомянул, что современные компьютеры не имеют такой вычислительной мощности, как машина Тьюринга, потому что у них нет бесконечной памяти, и, поскольку ни у одного компьютера нет бесконечной памяти, машина Тьюринга недостижима и просто представляет верхний предел. вычислительной техники. Существует ли мера или определение того, какие проблемы (или класс проблем) лежат за пределами досягаемости нашей вычислительной мощности?

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

Однако это не очень хорошая модель для изучения вычислимости, в действительности модель машины Тьюринга работает намного лучше, и именно поэтому мы используем ее для изучения вычислений на реальных компьютерах. Машине Тьюринга на самом деле не нужно бесконечное количество памяти, ей нужен только неограниченный объем памяти. Например, мы можем предоставить дополнительную память компьютеру со временем (поскольку компьютеру требуется все больше и больше памяти), и тогда у нас будет что-то похожее на машину Тьюринга. Если мы предположим, что у нас есть неограниченное количество времени и памяти для завершения наших вычислений, то машина Тьюринга в принципе довольно хорошо отражает эту концепцию вычислимости.

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

$\mathsf{P}$$\mathsf{P}$$\mathsf{BPP}$$\mathsf{BQP}$

Вы можете рассмотреть линейный ограниченный автомат, и соответствующие языки являются контекстно-зависимыми языками . См. Иерархию Хомского, чтобы узнать, какие языки недоступны для таких автоматов.

Кстати, в некотором смысле некоторые «недостижимые» проблемы теперь стали доступны из-за ограниченных вычислительных мощностей!

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

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

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

В строгом смысле этого слова нет: класс физически реализуемых компьютеров строго менее мощный, чем класс машин Тьюринга. Он строго менее мощный, чем класс конечных автоматов.