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

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

не нужно, просто как-то само собой ВНЕЗАПНО оказалось, что других машин у нас НЕТ. Т.е. либо вычислитель тьюринг-полный, либо — не полный. Третьего не дано.

Ну а регулярки они только для вспомогательных целей годны, писать на них код нельзя, а вот на brainfuck — можно(хотя и теоретически).

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

ты идиот или прикидываешься?

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

если не решается МТ, то значит детерминированного решения нет. Потому-что ВСЕ известные нам вычислители сводятся к МТ.

Т.е. может решается, но тогда вычислитель неизвестен, и он мощнее МТ. Ну или вычислитель не детерминированный, тогда он конечно может «попасть пальцем в небо».

Кроме того, в МТ не существует времени.

существует.

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

много. Смотри историю BWT, который сами авторы воспринимали как курьёз. И тем не менее, про программу bzip2 знаешь, да?

Потому-что ВСЕ известные нам вычислители сводятся к МТ.

точнее:

1. либо не дотягивают до MT

2. либо являются МТ

3. либо не являются детерминированными (тараканы, emulek, etc)

либо не являются детерминированными

И что с того?

существует.

нет. Это функция по сути. Формализм. Это только дети думают, что там что-то тарахтит внутри, а потом что то вываливается. На самом деле, это ф-ция, которая берет на вход программу и данные и вываливает результат. У функции нет времени. вход-выход точка.

он конечно может «попасть пальцем в небо».

это не попадание пальцем в небо. Это обычное решение. Например, я генерю рандомно числа в диапазоне 1-10, и вангую, что через приемлемое для меня время выпадет пятерка. Ты доказать, что она выпадет, не сможешь, но любому идиоту ясно, что прога выполнится. Так оно все и делается в реальной инженерной практике. Твоя прога, например, получает, сигнал с датчика давления, и открывает какой нибудь-клапан на атомном реакторе. у тебя программа детерменирована, хуля, if sygnal then open, без вариантов, доказал, епт, только вот проблемка, не факт, что сигнал то дойдет с датчика, провод могут у*бать, например, сдать на цветмет за пузырь водки. Вот из за таких детерминистов хреновых, случаются чернобыли переодически, потому что люди не воспринимают объективную реальность адекватно, у них в голове пердофункторы и монады вместо мозгов.

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

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

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

Бесконечная программа (регексп) вида «ab|aabb|aaabbb|....». Не?

Программа по определению конечна.

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

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

Много это тебе даст, как инженеру?

Это много дает ученым. Формализация классов P и NP делается через машину Тьюринга. Инженеры же пользуются результатами ученых, которые получены и с помощью машины Тьюринга в том числе.

нет. Это функция по сути. Формализм. Это только дети думают, что там что-то тарахтит внутри, а потом что то вываливается. На самом деле, это ф-ция, которая берет на вход программу и данные и вываливает результат. У функции нет времени. вход-выход точка.

Машина Тьюринга — это не функция :D

Машина Тьюринга может быть реализацией некоторой функции. Для одной и той же функции есть бесконечно много _разных_ машин Тьюринга, которые её реализуют. Некоторые работают быстрее, другие — дольше.

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

Нет, это не время, а детали реализации. никто там не сидит и не считает шаги.

Я считаю.

К тому же, если уж на то пошло, ответь тогда, один такт твоего времени «перемещение на одну ячейку вперед» == «перемещение с конца бесконечности в начало?»

Мне все равно, машина Тьюринга перемещается за один такт только на одну ячейку

Я считаю.

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

И, потом, основной смысл не в этом, а в том, что после того как ты подал МТ строку и программу на вход, оно не взаимодействует с внешним миром до вывода (остановки). Ты не можешь переписать программу во время выполнения.

Куда смотрит мебель? Почему шизофреник не в бане?

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

Демагогию тут разводишь ты.

И, потом, основной смысл не в этом, а в том, что после того как ты подал МТ строку и программу на вход, оно не взаимодействует с внешним миром до вывода (остановки). Ты не можешь переписать программу во время выполнения.

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

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

Нет не можешь, даже в теории. МТ определена и описана именно так, а не иначе. Возможно, ты что-то там изобретешь свое, но это уже будет не МТ.

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

Сам определил? Да не вопрос, строки тоже по определению конечны.

Нет не можешь, даже в теории. МТ определена и описана именно так, а не иначе. Возможно, ты что-то там изобретешь свое, но это уже будет не МТ.

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

Когда тебя уже по IP забанят?

Сам определил? Да не вопрос, строки тоже по определению конечны.

Строки — конечны, программы — конечны, языки — в общем случае бесконечны. Язык a^nb^n не является регулярным языком.

Когда тебя уже по IP забанят?

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

Строки — конечны, программы — конечны, языки — в общем случае бесконечны

Сам хоть понял что сказал? Русский язык бесконечен?

как можно по IP забанить, мягонький, если IP, в большинстве случаев, раздаются динамически?

У меня и еще много у кого статический.

Слив защитан, ибо ты перешел с нормального диалога на батхет.

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

Сам хоть понял что сказал? Русский язык бесконечен?

Вот когда ты дашь формальное определение русскому языку, тогда будем спорить. Но вообще да, бесконечен.

что понятие времени естественно вытекает из определения машины Тьюринга,

В таком случае, в ФП понятие времени естественно вытекает из определения LC-машины. Один такт — одна редукция.

В таком случае, в ФП понятие времени естественно вытекает из определения LC-машины. Один такт — одна редукция.

ок, ничего не имею против.

Вот когда ты дашь формальное определение русскому языку, тогда будем спорить

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

Это не то время, которое нам нужно. Нужна синхронизация с внешними событиями, а не эта параша.

не нужно тут никаких определений.

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

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

С чего это вдруг конечно?

Количество повторов А, АА, ААА, и комбинаций может быть бесконечным, да, но это касается в равной степени, как произвольной строки так и произвольного языка.

Что ты несешь?! У каждой отдельно взятой строки конечное число символов. Каждая строка, которая принадлежит языку, конечна. Язык же вполне может быть бесконечен.

Существует бесконечное число программ на языке Си, например.

Это не то время, которое нам нужно.

Откуда я знаю, какое время тебе нужно?

Нужна синхронизация с внешними событиями, а не эта параша.

Опять ты бессмыслицу несешь.

У каждой отдельно взятой строки конечное число символов.

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

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

Так-с... я все же попробую достучаться.

Вот тебе примеры строк из языка a^n:

a      -- длина 1
aa     -- длина 2
aaa    -- длина 3
aaaa   -- длина 4
...

У любой строки из языка конечное число символов. Но всего таких строк бесконечное число.

Заметь, в языке нет строки из бесконечного числа символов a.

Ага, а у каждой отдельно взятой бесконечной в обе стороны ленты МТ, конесное число ячеек.

Нет, у любой машины Тьюринга бесконечное число ячеек.

У тебя стоят часы, дома. Эти часы несинхронизированны с эталонными часами. У твоего соседа Васи — синхронизированы. Ты приходишь на работы в 8 часов по своему времени, а Вася, в 8 часов по московскому, но разница между вашими приходами — час, с точки зрения начальника, ибо у начальника время тоже синхронизировано с московским. Начальник тебе вставляет п*ды, несмотря на то, что у тебя есть свое время «в себе».

У любой строки из языка конечное число символов. Но всего таких строк бесконечное число.

У любой строки из языка конечное число символов, но всего таких строк бесконечное число.

Это утверждение так же справедливо. Более того, моё следует из твоего.

Я напомню, что ты утверждал изначально

Строки — конечны, программы — конечны, языки — в общем случае бесконечны

Где в этом контексте принципиальное отличие языка от не-языка? Я в упор не вижу.

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

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

Где в этом контексте принципиальное отличие языка от не-языка? Я в упор не вижу.

Язык — множество строк.

То есть, допустим, выражения на языке конечны, строки конечны, наборы как строк так и выражений — бесконечны. Что есть набор — комбинация строк, либо комбинация выражений? это тоже строка либо выражение. То есть, изначальная посылка несправедлива, ни строки ни выражения НЕ конечны, ибо сужествует их бесконечный набор, являющийся строкой/выражением

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

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

То есть, допустим, выражения на языке конечны, строки конечны, наборы как строк так и выражений — бесконечны. Что есть набор — комбинация строк, либо комбинация выражений? это тоже строка либо выражение.

Что такое набор, я не знаю?

У формального языка есть множество символов (алфавит) и множество слов(строк), которые принадлежат языку. Все.

Заметь, что с точки зрения формальных языков «съешь еще этих французских булочек» — одно слово.

То есть, изначальная посылка несправедлива, ни строки ни выражения НЕ конечны, ибо сужествует их бесконечный набор, являющийся строкой/выражением

Я же тебе уже и пример привел языка a^n.

Ты считаешь, что он содержит хоть одну бесконечную строку? Тогда приведи её.

Ты считаешь, что он конечен? Тогда скажи, сколько в нем строк или хотя бы дай оценку сверху.

А что толку, что я буду так считать, если это не соответствует реальности?

Какой реальности? Машина Тьюринга — модель, теория. Если для твоей реальности она не нужна, не мешай взрослым дядям, которым она нужна.

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

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

Если для твоей реальности она не нужна, не мешай взрослым дядям, которым она нужна.

Эти дяди только с виду взрослые, на самом деле, они забавляются со сказочными конями, которые к RL не имеют ровно никакого отношения

ознакомься

https://docs.google.com/file/d/0B79uetkQ_hCKTjRMN1JUVTl5M2s/edit?pli=1

для общего развития, а то я смотрю, тебя заклинило

Не беспокойся, ему до бана в реале уже недалеко. Болезнь-то прогрессирует.

Эти дяди только с виду взрослые, на самом деле, они забавляются со сказочными конями, которые к RL не имеют ровно никакого отношения

Эти дяди определили понятния классов P, NP и NP-полный. И благодаря этим дядям мы знаем, что многие задачи являются безнадежно трудными.

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

Ты считаешь, что он содержит хоть одну бесконечную строку? Тогда приведи её.

вот у тебя строка а

пиши такую программу

var=a
while(1) concat var a

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

Эти дяди определили понятния классов P, NP и NP-полный. И благодаря этим дядям мы знаем, что многие задачи являются безнадежно трудными.

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