Полагаю, вы можете внести ограниченную память в определение. Что-то вроде
Язык программирования для данной архитектуры (!) Является ограниченно завершенным по Тьюрингу, если для каждой машины Тьюринга существует программа, которая либо
a) имитирует машину Тьюринга и возвращает тот же результат (если возвращается машина Тьюринга) или
b) в какой-то момент полностью использует хотя бы один доступный ограниченный ресурс (например, память) и возвращает произвольный результат.
Вопрос в том, действительно ли помогает это интуитивное определение или лучше предположить, что ваша архитектура имеет неограниченную память (даже если она на самом деле конечна). Обратите внимание, что вам даже не нужно стараться, чтобы удовлетворить ограниченную полноту Тьюринга (как определено выше), если вы просто войдете в бесконечный цикл, который каждый раз использует один байт, вы нашли свою программу для all Машины Тьюринга.
Кажется, проблема в том, что вы не можете закрепить конкретные свойства реализации. Например, если у вас есть 500K RAM, вы можете выразить программу, которая вычисляет 1+1, но, возможно, вы не знаете, кто знает.
Я бы сказал, что такие языки, как Haskell и Brainfuck (да, я серьезно) на самом деле являются Turing Complete, потому что они абстрагируют ресурсы. В то время как такие языки, как C ++, являются только ограниченно завершенными по Тьюрингу, потому что в какой-то момент адресное пространство указателей исчерпано, и невозможно адресовать больше данных (например, отсортировать список из 2 ^ 2 ^ 2 ^ 2 ^ 100 элементов).