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]

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

[yatur]

В С - принципиально отличается. Нельзя же nponeccop пишет про размер указателя.

Во всяких си-шарпах, джавах и джаваскриптах указатели неявные. Теоретически их можно реализовать как угодно, хоть строкой переменного размера. Впрочем, в C# есть IntPtr.Size, но это скорее нужно для общения с миром С, и если его выкинуть, мало что изменится.

В С указатели - это по определению целые числа фиксированной битности. sizeof(int*) не может меняться в рантайме. Поэтому память в С принципиально конечна. А диск нет - можно открыть себе текстовый файл и писать в него сколько влезет, ничто не мешает ему быть больше максимального размера, адресуемого указателем.

[aklepatc]

Разумно. Спасибо!