"Машина Тьюринга" - занятый термин и он описывает класс математических моделей. Понятно, что в этом классе есть конечные конкретные экземпляры, т.е. конкретные завершающиеся алгоритмы. Вопрос останова ставится про произвольную машину, и на него есть доказанный отрицательный ответ. Поэтому отдельные конечные машины отвечают на другой вопрос.
Если же выделять класс заведомо конечных машин, то его нельзя называть "машина Тьюринга", а следует придумать новый термин.

Нет.

Idris? 😂

разве Идрис неполный по тьюрингу? о_О

Вроде бы обычно опускают требование о бесконечной ленте, заменяя ее достаточно длинной?

Тотальное подмножество, очевидно, не полное. Я не смотрел, используются ли в компиляторе Idris 2 нетотальные функции. По идее, должно быть можно обойтись без них. @clayrat что там на самом деле в кодовой базе?

Что значит "обычно"? Кто так делает? В каком контексте?

а она должна быть достаточно длинной с какой стороны?

А вот это уже без разницы! 😂

а вдруг я хочу, имея адесацию в uint, обратиться к ячейке памяти с отрицательным адресом? 🤠

Тогда Вам сперва придётся закодировать в МТ uint'ы и присвоить адреса каким-то ячейкам по некоторому правилу, а потом уж обращаться. И отрицательные числа тоже придётся закодировать. 😉

Так делают люди, в контексте описания вычислительной способности языка и системы :) поскольку бесконечной памяти не бывает, строгая формулировка становится бесполезной из-за невозможности применить ее к реально существующим вещам

Т.е. а) в контексте вопроса об останове так не делают, и б) поскольку у реально существующих языков с GC нет понятия памяти как "наблюдаемой сущности", они оперируют такой же абстракцией потенциально неограниченной памяти, как и МТ. 😉

как наличие GC помешает, например, создать бесконечно большой связанный список?

Я про то и говорю, что не мешает. Как и МТ. 🤷‍♀️

Значит все-таки языки с GC на практике оперируют достаточно большой, но никогда не бесконечной памятью, о чем я собственно и говорю

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

Нет, это решается проекцией футамуры

Тогда давате выберем критерием простоту написания специализатора на заданном ЯП. 😂

Так, погодите, давайте синхронизируемся по пунктам. Я перестаю успевать за вашим полетом мысли :)

Может ли вычислительная система являться полной по Тьюрингу, если ее "лента" конечна?