[algo][perl][fake?] Статический анализ ЯП

проблема остановки не разрешима для любого тьюринг-полного ЯП?

да

Соответственно тысячи языков не поддаются статическому анализу

нет

php тьюринг-полный. Но про него такой новости я не видел.

да и brainfuck'оподобных языков куча...

у тебя с логикой вообще как? как из того факта, что задача статического анализа perl5 является тьюринг-неразрешимой следует что-либо о статическом анализе любого другого языка?

С логикой у меня как раз всё ок.

что задача статического анализа perl5 является тьюринг-неразрешимой

Да, это так, но я говорил не об этом.
Проблема остановки неразрешима в общем случае для машины тьюринга => для любого тьюринг-полного языка.

Вот о чём я.

Получается, что перл - лишь частный случай. Наберётся ещё куча тьюринг-полных языков.

нет, с логикой у тебя очень плохо

ещё раз - какое отношение невозможность статического анализа perl5 имеет к другим языкам? и частным случаем чего ты считаешь perl5?

Проблема остановки неразрешима в общем случае для машины тьюринга => для любого тьюринг-полного языка.

Вот только задача статического парсинга для большинства других языков не сводится к задачи остановки, не?

:s/задачи/задаче

В первом посте: задача статического парсинга сводилась к проблеме остановки. Проблема остановки неразрешима для м.т. => неразрешима для тьюринг-полных ЯП. perl5 -частный случай тьюринг-полного ЯП. Тьюринг-полных ЯП полнО.

Достаточно?

вполне вероятно. Только я вот не могу понять: почему для других подобных языков она не будет сводится :(

> В первом посте: задача статического парсинга сводилась к проблеме остановки

Задача статического парсинга динамического языка.

Достаточно?

Нет :) То, что верно для подмножества ТП-языков, может быть неверно для полного множества :)

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

ты точно трезвый, ну?

почему для других подобных языков она не будет сводится :(

если у языка будет грамматика типа 0 по Хомскому, то задача его разбора так же будет сводится к задаче останова, и будет неразрешима для любого тьюринг-полного языка

АААА!!! Да сколько же можно? :)

Прибавь к предыдущему моему посту ещё 1 факт: в 1936ом Алан Тьюринг доказал неразрешимость этой задачи в общем случае для м.т., то бишь алгоритма, то бишь ТП-ЯП. (вот и всё множество подключили).

И да, задача не парсинга, а анализа... Чёт меня переклинило.

тут следовало бы добавить «в общем случае», вообще говоря. ну да мысль, я думаю, понятна

неразрешимость этой задачи в общем случае для м.т., то бишь алгоритма, то бишь ТП-ЯП

отсюда следует что ни один ТП-ЯП не может статически анализировать perl5, равно как и решать любую другую тьюринг-неразрешимую задачу. статический анализ подавляющего большинства современных ЯП вполне себе тьюринг-разрешим

Нет, я нетрезв... Но обычно это мне не мешало.

Грамматика типа 0 - это контекстно-зависимая?

хм... а другие языки не КЗ?.. Да... Что-то ни одного КЗ не припомню кроме перла...

Мб ты и прав.

Грамматика типа 0 - это контекстно-зависимая?

нет, это неограниченная. у нормальных языков грамматика контекстно-свободная

а пример языка с контекстно-зависимой грамматикой - C++; думаешь, почему разработка его компиляторов является такой болью в одном месте?

>> Грамматика типа 0 - это контекстно-зависимая?

http://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F...

> в 1936ом Алан Тьюринг доказал неразрешимость этой задачи в общем случае

Теперь тебе осталось доказать, что задача статического анализа _любого_ ТП-языка (а не только Перла) сводится к задаче останова.

Спасибо, прояснил этот момент. КЗ - это тип 1 :(. А 0 - да, неограниченные.

Что такое статический анализ языка? Давайте начнем с этого

Анализ программы без исполнения оной используя различные формализмы. Иногда сюда включают верификацию, но я предпочитаю разделять.

Это ж баян. Написать такую проверялку - задача со сложностью 50 в первом томе Кнута. Да и на ранних курсах даже нам это рассказывали

> если у языка будет грамматика типа 0 по Хомскому, то задача его разбора так же будет сводится к задаче останова, и будет неразрешима для любого тьюринг-полного языка

При чем тут сводимость чего-либо к проблеме остановки? Чтобы доказать неразрешимость задачи, надо, наоборот, показать, что проблема остановки (или другая алгоритмически неразрешимая проблема) сводится к ней.

Пардон, а отношение «сводимость» несимметричное?

Проблема разрешена, если что...

> Пардон, а отношение «сводимость» несимметричное?
Например, вычисление экстремума квадратного трехчлена сводится к задаче нахождения экстремума произвольной функции, но не наоборот.

> Пардон, а отношение «сводимость» несимметричное?

Ага. Например, я могу свести сортировку к полному перебору перестановок, но не наоборот.

Проблема разрешена, если что...

Речь идет об алгоритмической разрешимости. Проблема остановки алгоритмически неразрешима, то есть не существует алгоритма, позволяющего определить, остановится ли заданная программа на заданных исходных данных. К выражениям вроде «проблема, совпадают ли классы P и NP, далека от разрешения» это отношения не имеет :).

> остановится ли заданная программа на заданных исходных данных

Алгоритм, естественно, должен останавливаться и давать ответ (да или нет) для любых программ и любых исходных данных к ним.

Проблема не остановки разрешена, а моего временного тупняка, из-за которого я не мог понять, в чём же уникальность перл'а в этом случае.

код в студию

код в студию

Какой код?:)

Вся фишка в том, что решения у этой задачи нет, а дядя Кнут - шутник.