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

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

это не значит, что ее не существует. Иначе не было бы никаких бесконечных списков.

Более того, рядов чисел бы не было.

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

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

это не значит, что ее не существует. Иначе не было бы никаких бесконечных списков.

Она существует, но вот в языке её нет.

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

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

это ты знакомые буквы в SICP ищещь? Молодец.

это ты знакомые буквы в SICP ищещь? Молодец

ЯННП

неоднократно слышал лб этом. Почему?

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

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

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

сдать на цветмет за пузырь водки.

Вот из за таких детерминистов хреновых

такие как я делают проверку на корректность данных. Если провода украли, то датчик выдаёт совершенно нездоровые данные(к примеру обычно 10..15В, а тут 100 или 0). Если данные выходят за рамки, то это значит только одно: мы все умрём провода украли. Программа передаёт управлению оператору, ну или делает ещё что-то адекватное(роняет аварийный замедитель в реактор к примеру). Всё это вполне детерминированно.

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

ППКС, однако недетерминированный алгоритм теоретически _может_ решать даже те задачи, что не по силам МТ. Конечно может и НЕ решать. И конечно доказать наличие решения невозможно.

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

не обязательно. Программа может быть и бесконечной, но тогда она должна быть созданна каким-то конечным кодом. К примеру ab|aabb|aaabbb|… создать на МТ несложно.

МТ — это то, что это модель с глобальным состоянием.

это не имеет значения. Глобальное состояние проще для анализа, вот и всё. Ну и ближе к реальному железу, т.к. ФП процессоров так и нет.

такие как я делают проверку на корректность данных. Если провода украли, то датчик выдаёт совершенно нездоровые данные(к примеру обычно 10..15В, а тут 100 или 0). Если данные выходят за рамки, то это значит только одно: мы все умрём провода украли. Программа передаёт управлению оператору, ну или делает ещё что-то адекватное(роняет аварийный замедитель в реактор к примеру). Всё это вполне детерминированно.

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

это не значит, что ее не существует. Иначе не было бы никаких бесконечных списков.

бесконечных списков не существует. Как и бесконечных строк.

бесконечных списков не существует. Как и бесконечных строк.

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

Это твое утверждение говорит лишь о том, что ты никогда не занимался серьезным проектированием, и не представляешь сложности реальных задач.

спасибо, поржал.

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

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

это обычный для него режим, не аварийный.

для датчика — аварийный. И если простая схемка(сложностью как у сливного бачка) это распознать не может, то однокристалка — просто обязана, иначеза кой ляд её вообще туда запихали?

это не имеет значения

Это имеет значение, ибо модель без глобального состояния может решать задачи, которые не под силу модели с глобальным. ФП тут вобще не причем. LC машина — это тоже модель с глобальным состоянием.

они существуют как абстракция.

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

А так, да, не существует ни чисел, не множеств (ни бесконечных, ни конечных), вообще ничего нет.

реально — перечисленных вещей действительно не существует. Это обстракции, но не просто абстракции, а _полезные_ абстракции.

К примеру бесконечности не существует, это факт. И тем не менее, часто поведение программы «в точки бесконечность» очень важно, ибо позволяет выбрать нужный алгоритм. Это именно то самое «О-большое». Такое представление отсеивает несущественные детали, оставляя только суть поведения.

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

тут речь идет о проектировании систем, просто наглядный пример. Если ты быдлкодеришка, тогда да, это не к тебе, но тогда непонятно, что ты делаешь в этом треде.

для датчика — аварийный.

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

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

Я определил язык, в котором её нет. Если ты не умеешь в русский язык, это твои проблемы.

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

пример задачи в студию.

Иди хотя бы википедию почитай

Формальный язык

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

Для датчика вообще нет никакого режима

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

просто наглядный пример.

попробуй ещё, если этот пример ты зафейлил.

Не, ты просто ни*я не понял, пример годный.

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

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

не может <…> начать заново с новыми данными

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

Вот тебе практический пример алгоритма: https://ru.wikipedia.org/wiki/Алгоритм_Брезенхэма#.D0.A0.D0.B8.D1.81.D0.BE.D0...

Как видишь, алгоритм рисует идеальную окружность x²+y²=r², причём в самом алгоритме нет ничего сложнее умножения. Разгадка проста: каждый раз изменение координат малое, потому достаточно линейной экстраполяции.

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

результат на момент снятия — это по определению не актуальный результат. актуальный — это на текущий момент, а не когда то там. А так, у нас получается, актуальный президент, по некоторым данным — это ельцин.

Как видишь, алгоритм рисует идеальную окружность x²+y²=r², причём в самом алгоритме нет ничего сложнее умножения. Разгадка проста: каждый раз изменение координат малое, потому достаточно линейной экстраполяции.

То что ты приводишь — это либо фуфел, либо ты ННП. Если изменения СРАЗУ заложены в алгоритм, это не тот случай. Тебе нужно корректировать изменения на лету, в рантайме.

пример задачи в студию.

да и чо вообще далеко то ходить. Проблема останова решается, в частных случаях.

результат на момент снятия — это по определению не актуальный результат. актуальный — это на текущий момент, а не когда то там.

ты точно идиот: где ты возьмёшь бесконечно быстрый процессор? Думаешь, отсутствие глобального состояния сведёт время к нулю? У меня для тебя плохие новости: наоборот, ФП код работает намного медленнее, несмотря на «отсутствие времени».

То что ты приводишь — это либо фуфел, либо ты ННП. Если изменения СРАЗУ заложены в алгоритм

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

Тебе нужно корректировать изменения на лету, в рантайме.

в данном алгоритме именно это и происходит.

да и чо вообще далеко то ходить. Проблема останова решается, в частных случаях.

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

Не никакой разницы, концептуально, конечна лента или нет. даже при наличии бесконечной ленты «реальная» машина не сможет вечно выполнять прогу, потому что есть износ, рано или поздно она на*ся. Это все демагогия. В абстракцию МТ эти понятия «реального» не заложены. Это модель. Модель которая работает безотносительно времени. А в RL есть ВРЕМЯ.

В абстракцию МТ эти понятия «реального» не заложены.

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

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

иди проспись, потом поговорим.

Не, я лучше засчитаю тебе слив.

Ты не понимаешь одной простейшей хрени, то что ты предусматриваешь, возможные варианты, они у тебя из головы родом, а не из RL. Что ты пишешь, когда все варианты заканчиваются? default: Error. То есть, из всего бесконечного пласта вариантов, ты выбираешь лишь мизерную часть. А Ъ — это когда нет никакого Error, а есть прога, которая сама адаптируется к ситуации, сама принимает решения, так-то, сынок.

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

Теорию вероятности ты ещё не изучал, наверное?

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

Нет абсолютно никакой гарантии что она выполнится даже на 1 000 000 шаге. А вот посчитать, как будет расти вероятность этого события можно.

забанили, ну да ладно. Может как анон зайдёт…

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

я ничего не предусматриваю, вообще _ничего_. Всё проще: код ищет зависимости в истории, а потом их применяет. К примеру:

1, 3, 5, 7, 9, 11, ?

Усложним задачу, и предположим, что есть n точек (x,y), как решить задачу экстраполяции/интерполяции в точке n+1?

Решение простое: будем считать, что наша функция приближёно равна многочлену степени n-1, y=G(x), а коэффициенты многочлена {g₀, g₁, g₂…} (всего n коэффициентов g).

Получаем систему из n линейных уравнений относительно g.

Решаем её любым удобным способом.

Получаем ответ, пользуясь найденным полиномом y=G(x), для любых (x,y).

Конечно результат преобразования зависит от расстояния до новых точек от старых, ну и конечно от зашумлённости данных.

Есть два пути, с помощью которых можно очень сильно улучшить наше предсказание:

1. добавить ещё данных. К примеру прогнозируя котировки акций аграрных компаний, неплохо добавить данные об уражаях, например картошки и т.п. Как прошлые, так и будущие (несложно нагуглить прогнозы урожайности).

2. при вычислениях учитывать не только вклад производной каждого порядка(в этом смысл коэффициентов G(x)=y, например в примере с нечётными числами у нас всего одна производная первого порядка равная 2), но и погрешность, которую она вносит. При этом нужно учитывать обратную связь, ведь курс зависит(в т.ч.) сам от себя. Т.е. если мы наблюдаем существенный взнос от производных высшего порядка, это говорит нам о нестабильности акций. Производные высшего порядка сильно зашумлены, и зависят больше от случайных причин. Ситуация будет развиваться непредсказуемо, и акции могут как обвалиться, так и наоборот круто подняться.

А Ъ — это когда нет никакого Error

дык у меня и есть Ъ. Просто не факт, что прогноз будет правильный, но он конечно будет. А его точность зависит исключительно от точности и полноты исходных данных. На бирже я не играю исключительно потому, что там есть игроки, данные которых заведомо более точнее и полнее. И против этого не поможет никакая математика. Да и интеллект тоже(в т.ч. естественный). Это просто развод лохов, которые эту математику не знают.

потому что Миллер нажрался в самолете, и пытался трахнуть стюардессу в сортире.

фишка в том, что ты про это не узнаешь вовремя. Вспомни Монику из орального кабинета. Сколько лет она платье хранила и молчала? А выползла она именно тогда, когда НУЖНО.

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

возможно ли строго доказать это в данном случае?

НЕТ.

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

НЕТ.

Мало того, на 100500-м шаге вероятность выпадения 5 равна 10%, даже если до этого пятёрок ни разу не было. Это типичный развод лохов, которые наивно полагают, что у ГСЧ «есть память», и что «снаряд дважды в одну воронку не падает». (правда, стоит отметить, что для «одноруких бандитов» это не так, и у них можно выиграть, используя стратегию прямо противоположную стратегии интеллектуального большинства. Однако, шибко долго этим заниматься не получается, меня в 90х где-то через месяц перестали пускать ВО ВСЕ заведения города, сейчас это вообще нереально, из-за этих ваших интернетов и видео-наблюдения).

Нет абсолютно никакой гарантии что она выполнится даже на 1 000 000 шаге. А вот посчитать, как будет расти вероятность этого события можно.

никак не будет. Как было 10%, так и будет 10%, если ГСЧ правильный. Вот вероятность того, что в серии из N было M или больше, она конечно растёт с ростом N.