Comments | nponeccop: Тьюринг-полнота говно и у неё нет пиписьки

nponeccop

Тьюринг-полнота говно и у неё нет пиписьки

Mar 03, 2018 19:30

Теперь и на кворе: http://qr.ae/TU8m84

Попытался там насрать своими старыми идеями о том что тьюринг-полнота - это совершенно бесполезное свойство. Интересно, кстати, что если налетят любители идеи, что С неполон (я считаю, что он неполон "на самом деле"), у меня для них есть домашняя заготовка.

fp, programming

Comments 4

ext_991586 March 4 2018, 02:27:21 UTC

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

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

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

nponeccop March 4 2018, 05:19:52 UTC

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

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

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

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

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

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

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

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

yatur March 7 2018, 04:42:10 UTC

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

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

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

nponeccop March 7 2018, 06:53:53 UTC

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

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

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

data Nat = Zero | Succ Nat

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