Получается, от реализации языка зависит, будет ли он тьюринг-полным? Разве

это не значит, что реализации создают диалекты того языка, который есть на бумаге?

ну, кажется, ограничение в виде максимального размера ArrayDeque это скорее деталь реализации, а не неполнота самого языка

Зависит не от реализации, а от спецификации языка. Если в спецификации Brainfuck никаких ограничений на размер памяти не указано — у него бесконечная память и он полон по Тьюрингу.

Тогда язык запросто может быть полным по Тьюрингу в теории и неполным - на практике?

А что, какой-то язык может быть полным по Тьюрингу "на практике"? Где-то есть бесконечная память? 😂

Разумеется. Конкретная реализация любого языка, к которой в принципе невозможно добавлять память (в виде дополнительных ячеек RAM, или ленты, или дисков и т.п.), теоретически не только не полна по Тьюрингу, а вообще эквивалентна... см. мой вопрос https://t.me/CompilerDev/121627 ;)

Например, в Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2013). "Introduction to Automata Theory, Languages, and Computation" это излагается немного не так: ————— If we examine a program such as Fig 8.2, we might ask whether it really searches for counterexamples to Fermat's last theorem. After all, integers are only 32 bits long in the typical computer, and if the smallest counterexample involved integers in the billions, there would be an overflow error before the solution was found. In fact, one could argue that a computer with 128 megabytes of main memory and a 30 gigabyte disk, has "only" 256³⁰¹²⁸⁰⁰⁰⁰⁰⁰ states, and is thus a finite automaton. However, treating computers as finite automata (or treating brains as finite automata, which is where the FA idea originated), is unproductive. The number of states involved is so large, and the limits so unclear, that you don't draw any useful conclusions. In fact, there is every reason to believe that, if we wanted to, we could expand the set of states of a computer arbitrarily. For instance, we can represent integers as linked lists of digits, of arbitrary length. If we run out of memory, the program can print a request for a human to dismount its disk, store it, and replace it by an empty disk. As time goes on, the computer could print requests to swap among as many disks as the computer needs. This program would be far more complex than that of Fig. 8.2, but not beyond our capabilities to write. Similar tricks would allow any other program to avoid finite limitations on the size of memory or on the size of integers or other data items. ————— Т.е. неограниченность решает, как я понимаю (ну и практическая полезность абстракции, см. второй параграф).

Да. С этим, вроде, никто и не спорит.

Ну, да - если каким-то белком читать очень длинную ДНК, то мы ограничены массой образования сверхновой 😁

Почему сверхновой? Как только массы хватит для образования любой звезды — оно начнёт светить вместо того чтобы транскрибировать... 🤷‍♀️

То есть это не тьюринг полнота

Полнота, полнота — потому что звезда является компилятором же. 🤣

Даже если является всё равно не полнота. Тьюринг полнота говорит что лента должна быть бесконечной. А звезда очень даже конечна.

OK, fair point.

А вот некоторые авторы считают, что нет, см. цитату https://t.me/CompilerDev/121653 Неограниченные ресурсы — не то же самое, что бесконечные. Кстати, конечность Вселенной уже кто-то доказал? ;)

А что, кто-то доказал её неограниченность? 😏

Тоже нет. Так что на вопрос физической возможности настоящей МТ нет однозначного ответа, я так понимаю. ;)

Всегда можно сбросить что-нибудь на чёрную дыру, и оно будет падать бесконечно долго и вытянется в бесконечно длинную спагетину... 😏

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

Сегодня ограничены, завтра — менее ограничены (и так далее). Никто не говорил, что МТ должна работать непрерывно, или выполнять шаги с какой-то заданной скоростью и т.п. ;)

Тут возникает разница между программой/алгоритмом и её конкретным выполнением, спецификацией и конкретной реализацией. Если в программе/спецификации не задано никаких ограничений по ресурсам — она неограничена, и нам ничего не остаётся как рассматривать/анализировать её как таковую — эквивалентную некоторой абстрактной машине Тьюринга. То, что конкретная реализация ограничена в ресурсах и является аппроксимацией к спецификации — отдельный вопрос, и мы можем анализировать границы применимости и строить иерархию аппроксимаций, и всякое такое прочее.

Ну это у вас [биологический] вид, да и Вселенная какие-то... некачественные ("большой разрыв" там какой-то и т.п., обожемой) — станьте получше и найдите себе уже Вселенную поприличнее, и наша MT™ будет прекрасно работать для вас! ;) Кроме шуток — https://t.me/CompilerDev/121669 , да.

В следующем году статье Саттера будет 20 лет. А народ ещё массово «пускает поезда под откос». https://www.cs.utexas.edu/~lin/cs380p/Free_Lunch.pdf