Субтьюринговый полный класс вычислительных моделей

Question

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

Рассмотрим следующую неформальную модель:
Язык A определяет конечный набор вентилей NAND, их соединения друг с другом, и какие вентили получают входные данные и которые выводятся.

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

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

Является ли язык А и все другие системы, которые могут моделировать любой конечный автомат, Тьюрингом завершенным? Есть ли для них отдельный класс или есть возможность его определить?

Answer 1

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

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

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