?

Log in

No account? Create an account
Тьюринг-полнота говно и у неё нет пиписьки - Дважды мудак [entries|archive|friends|userinfo]
Декларативное рулит

Site Meter

[ website | Мой сайт ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Тьюринг-полнота говно и у неё нет пиписьки [мар. 3, 2018|19:30 pm]
Andy Melnikov
[Tags|, ]

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

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

Comments:
From: nsin real
2018-03-04 02:27 am
О, рад видеть, что кому-то еще не нравится бездумное применение Тьюринга :-)

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

Про неполноту C интересно послушать c учетом hdd+network.
(Ответить) (Thread)
[User Picture]From: nponeccop
2018-03-04 05:19 am
> Пример не очень хороший - не объясняет всей бесполезности.

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

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

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

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

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

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

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

Edited at 2018-03-04 06:23 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: yatur
2018-03-07 04:42 am
> На Хаскеле я могу написать тотальную функцию сложения натуральных, а на Си, используя только память - нет.

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

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

Edited at 2018-03-07 04:53 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: nponeccop
2018-03-07 06:53 am
> Что такого магического может Хаскель, чего не может С?

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

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

data Nat = Zero | Succ Nat

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

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

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

{ { next : { next : null } }

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

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

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

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


Edited at 2018-03-07 07:18 (UTC)
(Ответить) (Parent) (Thread)