Turing Completeness

[aklepatc]

Unconventional take on Turing completeness: https://www.quora.com/Does-a-programming-language-have-to-be-Turing-complete/answer/Andrii-Melnykov?share=77ae4ec9&srid=uCFpz.
And a little more of the same in Russian: https://nponeccop.livejournal.com/588087.html#comments.

Comments

[yatur]

Я читал ленту сплошняком, не заметил, кто автор, и решил, что тебе, наверное, это будет интересно почитать. Но уже поздно. Разве что, в интересах Тьюринг-полноты ты не читаешь собственных постов :)

Бесконечность во всех ее проявлениях вообще коварная штука. Замечание про 64-битный С очень верное. А вот насчет невозможности написать на С тотальную функцию сложения натуральных чисел я не совсем понял. Что такого волшебного может Хаскель, что не может С, даже при условии, что "мы используем только память"?

[aklepatc]

Я даже не понял, почему стандартный C - Turing complete. Память то всё равно конечна.
Для меня находка автора в том, что не всякий "настоящий" язык должен быть Turing complete.
Наивная идея, которая у многих осталось со школы. Приятно подкорректировать собственное укоренившееся заблуждение.

[yatur]

Стандартный С может лезть на диск, который потенциально бесконечен. Реализовать ленту можно операциями fseek() со смещением 1 и -1

[aklepatc]

Кажется, должно быть что-то ещё (другое)... Ведь потенциально бесконечный (на самом деле конечный) диск концептуально ничем не отличается от "очень большой" (на самом деле конечной) памяти.