Вопрос по тьюринг-полноте

[new_1]

В вики написано:

Цитата:

В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию.

А далее:

Цитата:

Полными по Тьюрингу являются также неограниченные грамматики.

Ячетнепонел, а что, грамматика у нас уже стала исполнителем?

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

[arseniiv]

Язык программирования — это не только язык в смысле множества «правильных» программ, но и какие-то описания того, какой эффект может произвести каждая из них. И вот тут уже можно связать каждую программу тьюринг-полного языка с каждой штукой из чего-то другого тьюринг-полного. (Что статья пишет про грамматики, не могу прокомментировать.)

-- Вс май 04, 2014 23:45:00 --

Посмотрите на всякий случай английскую вики-статью про неограниченные грамматики: http://en.wikipedia.org/wiki/Unrestricted_grammar. Там связь, вроде, явно описана.