Тьюринг-полные языки времени компиляции

[metaclass]

Что-то мне мозг гложет мысль. Если у нас язык шаблонов C++ или там система типов хаскеля тьюринг-полные - это же не означает что мы можем реализовать произвольные действия на них. Т.е. например описать две строки, конкатенировать их и вывести в виде одной строки. Собственно говоря, и машина тьюринга этого не умеет, в оригинале. Только если к ней прикрутить интерпретатор выходных значений, который бы умел выводить строки, тогда по идее можно такое сделать, в виде программы для нее.

Comments

[migmit.vox.com (from livejournal.com)]

Ну да. О чём я и говорю: никакое метапрограммирование не преодолевает фундаментальных недостатков нижележащего языка.

[a-lourier.livejournal.com]

Тьюринг-полнота означает, что можно реализовать любую функцию f:N->N. Ни о каких устройствах ввода-вывода речь не идет.

[blacklion.livejournal.com]

Ну, с любой вы погорячились :)

[a-lourier.livejournal.com]

Ага, точно. Когда пересдача? :)
Следовало читать: "любую вычислимую функцию".

[berezovsky.livejournal.com]

а чем такая конкатенация не подходит
http://imgur.com/kXuFt.jpg

[metaclass.livejournal.com]

Тут роль устройства вывода играет то, что мы смотрим на ленту, по идее.

[alexey-rom.livejournal.com]

Вывода нет. Но мы можем в каком-то формате (возможно, жутко неудобном) описать две строки и вычислить результат их конкатенации в том же формате.

[oxij.livejournal.com]

Имхо, Тьюринг-полнота означает, что можно сделать что-то эквивалентное этому «описать две строки, конкатенировать их и вывести в виде одной строки». А как там интерпретировать полученный результат — дело другое.

И ещё я сомневаюсь, что хаскелевская система типов Тьюринг-полна, ибо что-то мне подсказывает, что вывод типов можно свести к задаче останова.

[nivanych.livejournal.com]

> Если у нас язык шаблонов C++ или там
> система типов хаскеля тьюринг-полные -
> это же не означает что мы можем
> реализовать произвольные действия на них

Ну, SKI-комбинаторы можем сделать.
А значит, любые вычисления.
Но практически этим пользоваться крайне неудобно,
либо даже невозможно -- компилятор загнётся.