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

ЯП - это набор правил, соответствующий некоторой грамматике, а не исполнитель.

Нее, ЯП сам же и исполняет программу, значит он и есть исполнитель.

Нее, ЯП сам же и исполняет программу, значит он и есть исполнитель.

Ты чо, идиот, с дуба рухнул? Марш уроки учить.

Нее, ЯП сам же и исполняет программу, значит он и есть исполнитель.

ИМХО, исполнитель, это некая машина, «понимающая» язык.

Там как всегда опасная для мозгов хрень написана.

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

Спасибо, Вы, как всегда, выручаете.

А правильно ли я понимаю, что термин «тьюринг-полный ЯП» — это тоже не совсем корректный термин, правильно было бы говорить о полноте исполнителя этого ЯП, возможно, в совокупности с самим ЯП, (по аналогии с самой машиной тьюринга, которая содержит в себе алфавит)? Т.е. исполнитель == машина + язык, именно он, как аналог МТ является (или не является) тьюринг-полным?

Тьюринг-совместимая машина — удовлетворяющая полноте по Тьюрингу.

Машина это совокупность исполнителя и языка (грамматики). Если расширить язык на тьюринг-машине, то он останется «тьюринг-совместимым». То есть имеется в виду, что он изначально уже был на тьюринговой машине.

Если берётся марковская модель исполнения, то там машина уже изначально тьюринговая. Многие автоматы тоже тьюринговые.

Т.е. исполнитель == машина + язык

Даже, точней машина + текст программы на языке

//fixed

там машина уже изначально тьюринговая

В каком смысле «изначально»? В смысле, что машина, вычисляющая марковские алгориФмы, эквивалентна МТ?

Если расширить язык на тьюринг-машине, то он останется «тьюринг-совместимым». То есть имеется в виду, что он изначально уже был на тьюринговой машине.

Ну, если расширить машину Поста до машины Тьюринга (для этого, видимо надо прикрутить ничего не значащие свистоперпделки), то эта (получившаяся) Тьюринг-машина останется, видимо, Пост-совместимой.

Для произвольной неограниченной грамматики полным и безошибочным спеллчекером может быть только некоторая машина Тьюринга.

принадлежность слова неограниченной грамматике - алгоритмически неразрешимая проблема.