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

Пример не очень хороший - не объясняет всей бесполезности. Можно постепенно повышать до 128-bit, 256-bit и т.д - и язык все еще остается не тьюринг-полным.
Фокус тьюринг-полноты получается только если ∞-bit (или если разрешить увеличивать количество памяти в рантайме).

Про неполноту C интересно послушать c учетом hdd+network.

> Пример не очень хороший - не объясняет всей бесполезности.

Он и не должен объяснять всей бесполезности. Это просто пример полезного неполного языка.

> Фокус тьюринг-полноты получается только если

Там 100500 разных вариантов есть

> если разрешить увеличивать количество памяти в рантайме

а на рантайм нам плевать, важен не рантайм а семантика. На Хаскеле я могу написать тотальную функцию сложения натуральных, а на Си, используя только память - нет. Можно с этого начать.

> Про неполноту C интересно послушать c учетом hdd+network.

Да чего уж там. Можно прямо ленту прикрутить устройством ввода-вывода. void moveLeft(); void moveRight(); void writeBool(bool b); bool readBool(); вполне хватит :)

Edited at 2018-03-04 06:23 (UTC)

> На Хаскеле я могу написать тотальную функцию сложения натуральных, а на Си, используя только память - нет.

А можно подробнее? Что такого магического может Хаскель, чего не может С? Скажем, что не дает мне написать на С интерпретатор Хаскеля, который использует только память, и проинтерпретировать им эту самую тотальную функцию?

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

Edited at 2018-03-07 04:53 (UTC)

> Что такого магического может Хаскель, чего не может С?

Дело не в "может", а в спецификации. Нам плевать на то что кто может и что там в рантайме. Важен не рантайм, а семантика.

Спецификация хаскеля гарантирует мне, что в семантике у

data Nat = Zero | Succ Nat

у типа Nat нет ни максимального элемента, ни зацикливания.

Попробуйте на Си написать длинное число и я скажу как, используя спецификацию Си, узнать, какое у этого представления максимальное значение на данной архитектуре.

В качестве простой аналогии - в джаваскрипте нельзя узнать размер указателя. Поэтому можно написать тупой список типа

{ { next : { next : null } }

и у него по спецификации не будет максимального кол-ва элементов, он будет изоморфен самому настоящему натуральному числу

> и хранить его в виде потенциально бесконечного
> с списка сегментов.

я написал "используя память". А так-то можно прямо ленту машины Тьюринга внешним устройством подключить, с только операциями относительного сдвига головки, я уже писал.

В-общем лента-устройство это чит :) И если мы его разрешаем то у нас сразу весьма экзотические ЯП становятся тьюринг-полными


Edited at 2018-03-07 07:18 (UTC)