Здравствуйте, Sinclair, Вы писали:

S>Он и не должен ничего опровергать. Это другой алгоритм, который применяется к другой машине.
Верно. И выдаёт результат не относящийся к сабжу.

S>·>И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
S>Эмм, кто-то из нас невнимательно читает.
S>

S>В состав машины Тьюринга входит неограниченная в обе стороны лента

Это не _определение_ МТ. Открой мат-формализацию МТ и ткни пальцем где там ∞.

S>Как только мы ограничиваем ленту, существование Анализатора перестаёт быть опровергнутым.
И перестаёт быть МТ и формализацией алгоритма.

S>·>Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.
S>Эмм, вы сейчас предположили, что существует некий алгоритм, который проверяет произвольную программу для ограниченной машины Тьюринга на предмет соответствия её некоему регулярному выражению, причём за N ресурсов. Я правильно понял?
Нет. Я сказал, что проще тупо запустить регулярку и подождать когда она закончится, чем запускать её под твоим циклоанализатором который просто интерпретирует эту же регулярку дважды и не даёт никакого полезного результата.

S>·>Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.
S>А то. У вас есть более эффективный алгоритм, который обнаруживает циклы в конечном автомате?
Зацикливаться конечный автомат не может. Он всегда завершает свою работу.

S>·>Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.
S>Нет, не ошибка. "Эмуляция" в данном случае эквивалентна некоему оракулу. То есть мы не даём машине бесконечную память, мы просто переносим проблему реализации бесконечности куда-то ещё.
Это ты что-то сочиняешь. Оракл это вполне определённая конструкция в ТА: https://en.wikipedia.org/wiki/Oracle_machine
Машине Тьюринга не надо давать бесконечную память (что бы это ни значило) — посмотри на сам формализм МТ. Надо просто выполнять движение головки вправо-влево.

S>·>Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.
S>Это просто означает, что "решение" при помощи полного перебора вообще решением не является.
Для некоторых задач — является. Начали перебирать и таки нашли решение.

S>·>Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.
S>"Забить в базу" не так легко, как кажется.
Потому что сабж.

S>1. выражение "алгоритм a^n+b^n=c^n" не имеет смысла — тут нет алгоритма. Это всего лишь некоторая формула. Если вы под "алгоритмом" имеете в виду пошаговое вычисление выражения сравнения aⁿ+bⁿ с сⁿ, где a, b, c — положительные целые, а n — целое, большее 2х, то да — мы можем подставить в результат false без честного вычисления. После чего можно продолжить свёртку программы — в частности, в ветвлении на основе этого результата мы можем целиком выбросить одну из веток, что, потенциально, позволит нам сделать ещё какие-то выводы.
Я имею в виду программу for(a,b,c,n in 2..){if(a^n+b^n=c^n) print(1);} — напечатает ли эта программа "1"? Поможет ли твой циклодетектор ответить на этот вопрос?

S>2. алгоритм вычисления этой формулы может быть запрограммирован по-разному. Простого "побитового" сравнения кода программы недостаточно — нужно доказать, что некое вычисление эквивалентно этой формуле. Если я не ошибаюсь, то это — частный случай теоремы Райса. Так что упс.
Это частный случай сабжа (точнее этот вопрос сводится к сабжу).
И ты немного путаешь опять. Для неких вычислений доказать эквивалентность таки можно алгоритмически. Невозможно построить алгоритм, который сравнит любые данные вычисления. Т.е. результатом любой возможной реализации алгоритма проверки эквивалентности будет "да", "нет", "хз". Всё ровно так же как и с твоим циклодетектором. Потому что сабж.

S>·>Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.
S>Для любого реального компьютера существует некоторое N, начиная с которого числа становятся невыразимыми.
Так назови его, если сможешь. Вон некоторые до Graham's number досчитали. Ты почему-то считаешь, что числа непременно надо поразрядно представлять. Можно и символьные выражения использовать. Число записанное как "2^1000" — занимает всего 6 байт.
А достаточно в коде появится int64 счётчику и твой циклодетектор станет абсолютно бесполезен на практике. Что и происходит в большинстве реальных случаев, твой анализатор будет отвечать "цикл не найден" почти всегда. Вот это уже подлянка Райса.

S>·>Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?
S>Ни в какой. Эта МТ не останавливается.
S>А если мы запустим такую программу на МТ c ограниченной лентой, то HALT будет выполнен автоматически в момент сдвинуть головку вправо, когда головка упрётся в край ленты.
Только это уже другая программа будет. Т.е. вместо исходной задачи f(n) ты неявно анализируешь f(n), n<N, но почему-то заявляешь, что результат анализа даёт информацию об исходной задаче.

S>·>Ещё раз повторю. Это эквивалентные ограничения.
S>·>Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".
S>Проблема — в том, что применение подобной манипуляции к коду, который до неё не зацикливался, сделает его "зацикливающимся". Какой смысл в таком "детекторе"?
Ровно такой же, какой в твоём циклодетекторе.

Здравствуйте, Sinclair, Вы писали:

S>Он и не должен ничего опровергать. Это другой алгоритм, который применяется к другой машине.
Верно. И выдаёт результат не относящийся к сабжу.

S>·>И — самое важное!!! В определении МТ не используется "бесконечная лента". Нигде!
S>Эмм, кто-то из нас невнимательно читает.
S>

S>В состав машины Тьюринга входит неограниченная в обе стороны лента

Это не _определение_ МТ. Открой мат-формализацию МТ и ткни пальцем где там ∞.

S>Как только мы ограничиваем ленту, существование Анализатора перестаёт быть опровергнутым.
И перестаёт быть МТ и формализацией алгоритма.

S>·>Угу, что и делает его бесполезным и даже вредным в данном случае, как минимум. Зачем тратить N*K ресурсов, если достаточно N.
S>Эмм, вы сейчас предположили, что существует некий алгоритм, который проверяет произвольную программу для ограниченной машины Тьюринга на предмет соответствия её некоему регулярному выражению, причём за N ресурсов. Я правильно понял?
Нет. Я сказал, что проще тупо запустить регулярку и подождать когда она закончится, чем запускать её под твоим циклоанализатором который просто интерпретирует эту же регулярку дважды и не даёт никакого полезного результата.

S>·>Ну так эта твоя "реальная машина отключённая от сети" по сути и есть регексп, конечный автомат, точнее.
S>А то. У вас есть более эффективный алгоритм, который обнаруживает циклы в конечном автомате?
Зацикливаться конечный автомат не может. Он всегда завершает свою работу.

S>·>Верно. Т.е. "Невозможно дать значение 2^64+1 программе, написанной на языке с 64-разрядными указателями" — ошибка.
S>Нет, не ошибка. "Эмуляция" в данном случае эквивалентна некоему оракулу. То есть мы не даём машине бесконечную память, мы просто переносим проблему реализации бесконечности куда-то ещё.
Это ты что-то сочиняешь. Оракл это вполне определённая конструкция в ТА: https://en.wikipedia.org/wiki/Oracle_machine
Машине Тьюринга не надо давать бесконечную память (что бы это ни значило) — посмотри на сам формализм МТ. Надо просто выполнять движение головки вправо-влево.

S>·>Это ты сейчас знаешь что свелось и все карты не нужно. А до того как это стало известным, кроме как перебора ничего не было.
S>Это просто означает, что "решение" при помощи полного перебора вообще решением не является.
Для некоторых задач — является. Начали перебирать и таки нашли решение.

S>·>Т.е. теперь точно известно, что алгоритм a^n+b^n=c^n — не останавливается. Т.е. теперь в базу можно забить правило "нашли такое выражение — точно знаем, что цикл бесконечный" и гонять на бесконечных числах не требуется.
S>"Забить в базу" не так легко, как кажется.
Потому что сабж.

S>1. выражение "алгоритм a^n+b^n=c^n" не имеет смысла — тут нет алгоритма. Это всего лишь некоторая формула. Если вы под "алгоритмом" имеете в виду пошаговое вычисление выражения сравнения aⁿ+bⁿ с сⁿ, где a, b, c — положительные целые, а n — целое, большее 2х, то да — мы можем подставить в результат false без честного вычисления. После чего можно продолжить свёртку программы — в частности, в ветвлении на основе этого результата мы можем целиком выбросить одну из веток, что, потенциально, позволит нам сделать ещё какие-то выводы.
Я имею в виду программу for(a,b,c,n in 2..){if(a^n+b^n=c^n) print(1);} — напечатает ли эта программа "1"? Поможет ли твой циклодетектор ответить на этот вопрос?

S>2. алгоритм вычисления этой формулы может быть запрограммирован по-разному. Простого "побитового" сравнения кода программы недостаточно — нужно доказать, что некое вычисление эквивалентно этой формуле. Если я не ошибаюсь, то это — частный случай теоремы Райса. Так что упс.
Это частный случай сабжа (точнее этот вопрос сводится к сабжу).
И ты немного путаешь опять. Для неких вычислений доказать эквивалентность таки можно алгоритмически. Невозможно построить алгоритм, который сравнит любые данные вычисления. Т.е. результатом любой возможной реализации алгоритма проверки эквивалентности будет "да", "нет", "хз". Всё ровно так же как и с твоим циклодетектором. Потому что сабж.

S>·>Но это не значит, что они ограничены. Что все числа, начиная с некоторого N, не выразимы на реальном компьютере.
S>Для любого реального компьютера существует некоторое N, начиная с которого числа становятся невыразимыми.
Так назови его, если сможешь. Вон некоторые до Graham's number досчитали. Ты почему-то считаешь, что числа непременно надо поразрядно представлять. Можно и символьные выражения использовать. Число записанное как "2^1000" — занимает всего 6 байт.
А достаточно в коде появится int64 счётчику и твой циклодетектор станет абсолютно бесполезен на практике. Что и происходит в большинстве реальных случаев, твой анализатор будет отвечать "цикл не найден" почти всегда. Вот это уже подлянка Райса.

S>·>Наконец-то ты на верном пути. Именно, что выполнение команды HALT! Расскажи в какой момент анализируемая твоим "динамическим анализатором" МТ вида "Q0: записать один, сдвинуть головку вправо, перейти в Q0" выполнит halt?
S>Ни в какой. Эта МТ не останавливается.
S>А если мы запустим такую программу на МТ c ограниченной лентой, то HALT будет выполнен автоматически в момент сдвинуть головку вправо, когда головка упрётся в край ленты.
Только это уже другая программа будет. Т.е. вместо исходной задачи f(n) ты неявно анализируешь f(n), n<N, но почему-то заявляешь, что результат анализа даёт информацию об исходной задаче.

S>·>Ещё раз повторю. Это эквивалентные ограничения.
S>·>Смотри. У тебя есть такой код: while(true)print(1);. И типа твой циклодетектор что-то там найдёт. Если у тебя есть ограничение по памяти, то ты можешь просто слегка (алгоримтически тривиально) модифицировать этот код в такой while(true){allocateOneByte();print(1);}} и без всякого циклодетектора понять, что код "зациклился".
S>Проблема — в том, что применение подобной манипуляции к коду, который до неё не зацикливался, сделает его "зацикливающимся".
Не понял с чего это вдруг. В худшем случае, просто будет требовать в константу раз больше памяти.

S>Какой смысл в таком "детекторе"?
Ровно такой же, какой в твоём циклодетекторе.