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

Какая невыносимо печальная у тебя жизнь.

Регулярки неспособны парсить циклические структуры данных, а Тьюринг -способен.

Если имеется ввиду единоразовое применение этих функций, то с ними.

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

О, привет, анонiмус :)

Спасибо анонимусу и cord, в целом — ясно, все дело в циклах. Эт, в принципе, фигня, я думал, там что-то серьезней. Спасибо.

Само регулярное выражение - это всего лишь строка. Она не является ни полной ни не полной тьюрингу. Это вообще не вычислитель.

Вычислитель это как раз функция match, которая получает на вход регулярное выражение и строку, и проверяет, соответствует или нет строка выражению.

Почему же функция match не является полным по тьюрингу вычислителем? Потому что есть контрпример, например.

Не существует регулярного выражения такого, с помощью которого функция match позволит определить принадлежит ли произвольная строка языку L={(^n)^n, n-любое натуральное число}.

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

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

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

Спасибо, Ваш ответ заставил призадуматьсяю НО!

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

Гы. Это какая то хренотень, по-моему. Тут функция match является машиной. Это черный ящик, реализация которого нас ниибет, для нас важно поведение. То же самое что с МТ. Итак, подаем на вход МТ строку исходного текста программы(re) и данные — строку. Подаем на вход МТ текст программы и данные — строку. В чем разница? допустим, строка, поданная в качестве данных MT — сама является программой для МТ. Как МТ может однозначно сказать, является ли поданная на вход строка программой для нее или нет?

Сама программа - это всего лишь строка. Она не является ни полной ни не полной тьюрингу. Это вообще не вычислитель.

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

Хорошо😊 Тогда пусть будет так: ... принадлежит ли строка языку регулярных выражений. Так понятнее?

Ну красавчик, все верно.

Это классический случай программирования управляемого данными. Какой бы ты регексп не написал всегда можно пустить ему на вход не те данные. Проще говоря в данном случае алгоритм это регексп + входные данные. Сам по себе регексп это половина программы. Естественно одна регулярка не решает вообще ничего. Можно только предположить её поведение и то на ограниченных наборах данных.

UPD: кстате из вики: Примерами неполных по Тьюрингу формализмов являются конечные автоматы. А регулярки это частный случай конечных автоматов.

Ага, только я тебе по секрету скажу, полными по тюрингу называют языки программирования.

принадлежит ли строка языку регулярных выражений. Так понятнее?

Понятно, все как и выше объяснили, короче, это невозможно сделать за один проход. если есть циклы или goto, re превращается в тьюринг-полный язык. Это, видимо, эквивалентно машине тьюринга, которая не может возвращать головку назад.

Это классический случай программирования управляемого данными.

Я вот этого тоже до конца не понимаю, если честно. Допустим, есть исполнитель, есть язык, есть данные. Исполнитель берет на вход текст языка и текст данных и выполняет программу. Это общий случай для любого языка, оптимизации, препроцессоры — это все можно не рассматривать, сути это не меняет. Таким образом любое программирование является программированием управляемым данными. Данные управляющие исполнителем тут — это текст программы. Я иного варианта не вижу просто. Поэтому, программирование управляемое данными — это нонсенс. Оно все такое, имхо.

Если надо серьезней - то регулярка не умеет хранить состояние (из-за чего и не может циклы). replace по идее дает такую возможность.

*Вычислитель регулярки, т. е. match.

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

Чтобы лучше понять, что такое программа, управляемая данными представь себе например видеокодек. Ты же не будешь возражать, что можно снять исходники линукса на видео? С другой стороны кодек понятия не имеет о том, что он воспроизводит. Его вход чётко детерминирован форматом. Изображение же может быть любым. А вот у регулярок может быть любой вход. Вплоть до того, что ты опечатался в имени файла и подсунул бинарь.

И вычислители тоже. А что такое язык программирования?

А что такое язык программирования?

Это правила написания текста для вычислителя.

Посмотри уже наконец на нормальные алгорифмы Маркова. И таблеточки принять не забудь, а то деградируешь слишком быстро.

Допустим. Тогда это должен быть, быть набор лексических, синтаксических и семантических правил для вычислителя. Семантические правила, если следовать вашей же логике, и определяют вычислитель. Лексические и синтаксические правила, следуя вашей же логике, определяют множество строк. Значит ЯП это множество строк плюс вычислитель.

ЯП полон по тьюрингу, если на нем можно записать любую вычислимую функцию. Этот означает, что для любой вычислимой функции во множестве строк из описания ЯП найдётся такая, для которой вычислитель из описания ЯП вычисляет её. Это все следуя вашей же логике.

В вашем случае ЯП это множество регулярных выражений (строк) плюс функция match (вычислитель). Регулярные выражения это просто строки. Они ни полные, ни не полные по тьюрингу... 😊

Match это вычислитель. Будучи добавленным к языку (множеству строк) он даёт вам ЯП. Когда вы рассуждаете о полноте по тьюрингу этого ЯП вы на самом деле рассуждаете о полноте по тьюрингу вашего вычислителя. Как то так. Это для полноты картины.

Значит ЯП это множество строк плюс вычислитель.

Вычислитель туда не входит.

Регулярные выражения это просто строки. Они ни полные, ни не полные по тьюрингу...

Регулялярные вражения — это язык.

Вы же сами сказали, что ЯП это набор правил для вычислителя. Какие строки могут подаваться ему на вход и как он на них реагирует. Следовательно... 😊

Язык это по определению простое множество строк над некоторым алфавитном, ничего больше. Поэтому мне и стало интересно, что вы имеете ввиду под языком программирования?

И если мы используем такое определение языка (а не «набор правил для вычислителя»), то что будет означать фраза «можно записать любую вычислимую функцию на этом языке»? Как построить однозначное соответствие между множеством строк и множеством вычислимых функций?

означать фраза «можно записать любую вычислимую функцию на этом языке

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

Вы же сами сказали, что ЯП это набор правил для вычислителя. Какие строки могут подаваться ему на вход и как он на них реагирует. Следовательно...

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

Как построить однозначное соответствие между множеством строк и множеством вычислимых функций?

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

ну... регулярки не могут парсить выражения a^nb^n, а машина Тьюринга — может.

Вы же сами сказали, что ЯП это набор правил для вычислителя

И я сказал, не то что это набор правил для вычислителя, а то что

Это правила написания текста для вычислителя.

написания текста. Пишет текст не вычислитель, вычислитель интерпретирует этот текст.

a^nb^n

это что за «выражение»? Че то я не вижу проблемы спарсить эту строку? В чем подвох?

Ты должен парсить

ab
aabb
aaabbb
aaaabbbb
....

Но не пропускать

aab
abbb
aabbb
...

То есть, сначало идет какое-то количество символов a, затем такое же количество символов b.

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

Следующие утверждения эквивалентны:

- функция вычислима на машине Тьюринга

- функция вычислима на машине Поста

- функция вычислима нормальным алгоритмом Маркова

- функция вычислима в лямбда-исчислении

Потому и говорят просто «вычислимая функция»

Ну да, тут дело в возвратах. Это уже тут говорили.

Да, можно продолжить еще:

-функция вычислима на перлом

-функция вычислима си

-функция вычислима васей

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

Потому и говорят просто «вычислимая функция»

Говорят, кстати, именно потому, что именно Тьюринг ввел этот сомнительный «термин», это от него пошло. И это все не отменяет его абсолютной бессмысленности. Нет никакой «вычислимости», это конь.

Почему демагогия? Это точное формально определенное понятие.

Есть примеры как вычислимых функций, так и невычислимых.

Говорят, кстати, именно потому, что именно Тьюринг ввел этот сомнительный «термин», это от него пошло. И это все не отменяет его абсолютной бессмысленности. Нет никакой «вычислимости», это конь.

Надо же, жопа есть, а слова такого нет.

Математика она такая, определение дали, значит «вычислимость» есть.

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

Это точное формально определенное понятие.

пруфец будет?

Есть примеры как вычислимых функций, так и невычислимых.

Есть примеры да. Есть пример функций вычислимых на A, есть вычислимых на B. А этих вычислителей бесконечное множество, и у каждого своя вычислимость.

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

Говорят, кстати, именно потому, что именно Тьюринг ввел этот сомнительный «термин», это от него пошло. И это все не отменяет его абсолютной бессмысленности. Нет никакой «вычислимости», это конь.

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

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

Как обычно в математике, слово «можешь» может означать что угодно, например то, что Over9000 кодеров будут решать задачу 100500 лет, и так и не решат.

пруфец будет?

Тебе написать определение вычислимой функции?

Есть примеры да. Есть пример функций вычислимых на A, есть вычислимых на B. А этих вычислителей бесконечное множество, и у каждого своя вычислимость.

«Функция вычислима» == «Функция вычислима на МТ» == «Функция вычислима алгоритмом Маркова» == ...

Есть примеры да. Есть пример функций вычислимых на A, есть вычислимых на B. А этих вычислителей бесконечное множество, и у каждого своя вычислимость.

пруфец будет?

Допустим, есть некоторая ф-ция, невычислимая на МТ, но вычислимая на машине X. Языки А, B и С эквивалентны МТ, а языки D, E, F эквивалентны X. А есть машина Y которая вычисляет ф-цию, невычислимую на X. И так далее. Что нам дает соответствие МТ? Зачем оно нам?

Тебе написать определение вычислимой функции?

НЕ надо, я сам

Вычислимые функции — это множество функций, которые могут быть реализованы на машине Тьюринга

Воистину, Петросян отдыхает. Я переведу на русский:

Вычислимые на машине Тьюринга функции — это множество функций, которые могут быть реализованы на машине Тьюринга

пруфец будет?

Тысячи их, лол. Возьми для начала, хоть МТ с оракулом, например.

Так уж получилось, что упоминаемые в топике вычислители эквивалентны. А если Вася придумает более мощный, пусть поделится.

Знаете, а натуральных чисел нет. Потому что единицы нет. Единицу придумал Тьюринг, и назвал её единицей. А все натуральные числа определяются через единицу. Но это конь, потому что Пост придумал двойку, а единица это половина двойки. А завтра Вася придумает тройку, а единица это треть тройки. И таких миллионы, и у каждого свой способ получить единицу.

Воистину, Петросян отдыхает. Я переведу на русский:

Откуда же ты такой взялся?

«Вычислимая функция» == «вычислимая на машине Тьюринга»

Это определение. Точка. Если это оскорбляет твои чувства верующего, то это твои проблемы, просто забудь о машинах Тьюринга и все.

... свой способ получить свою единицу и свои собственные натуральные числа. Так что единого множества натуральных чисел нет! 😊

Первые решаются на МТ, вторые не решаются

Тут все дело в том, что если задача не решается на МТ, это не значит, что она вообще не решается. Привязка к МТ нам ничего не дает существенного, ни в теоретическом ни в практическом плане.

В старых бумагах по ИИ я частенько натыкался на иное: эффективная вычислимость. Это нечто, соответствующее бритве Оккамы. Вот эта вещь, могла бы действительно иметь какой-то смысл.

Кроме того, в МТ не существует времени. Ну, допустим, задача решаема на МТ, но в реальности, ты будешь вычислять ее over миллиард лет. Много это тебе даст, как инженеру?