GhostCoders wrote:

> Я хочу вам показать одну вещь.
> Есть БОЛЬШАЯ разница между абстрактным алгоритмом вообще и его
> реализаией на реальной вычислительной машине.
Кто бы мог подумать?!

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

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

> наш же реальный переполнится в какой-либо переменной, после
> максимального значения, переменная установиться в значение 0.
Переполнится когда? И почему ты решил, что обязательно переполнится? А вдруг не переполнится, просто закончит работу через 10^1000 лет?

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

Курилка wrote:

> Ну по идее есть же Гёделева нумерация
> <http://en.wikipedia.org/wiki/Goedel_numbering&gt; (базис доказательства
> теоремы Гёделя), так что вполне себе счётно.
Так это для некоего заданного формального языка (т.е. is a set of words, i.e. finite strings of letters, or symbols).

Но количество самих формальных языков — несчётно.

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

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

В системах реального времени например. Даже могу дать гарантию что алгоритм будет выполняться не дольше чем
N шагов.

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

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

.>Курилка wrote:

>> Ну по идее есть же Гёделева нумерация
>> <http://en.wikipedia.org/wiki/Goedel_numbering&gt; (базис доказательства
>> теоремы Гёделя), так что вполне себе счётно.
.>Так это для некоего заданного формального языка (т.е. is a set of words, i.e. finite strings of letters, or symbols).

.>Но количество самих формальных языков — несчётно.

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

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

.>GhostCoders wrote:

>> Я хочу вам показать одну вещь.
>> Есть БОЛЬШАЯ разница между абстрактным алгоритмом вообще и его
>> реализаией на реальной вычислительной машине.
.>Кто бы мог подумать?!

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

Да так оно и есть. Мой алгоритм будет анализировать его тоже много времени, практически бесконечно.

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

Курилка wrote:

> Докажи.
Диагонализацией доказывается.

> По-моему для языков можно также ввести нумерацию (формального
> доказательства не дам ) и получим счётное множество счётных множеств.
Счётное множество счётных множеств — счётно.

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

GhostCoders wrote:

>> > С помощью простейшего языка я методом перебора могу тебе дать гарантию
>> > что он не зависнит, например, на 10000 входных значений.
> .>Молодец. Только зачем это нужно?
> В системах реального времени например. Даже могу дать гарантию что
> алгоритм будет выполняться не дольше чем
> N шагов.
Кому это нужно? Для таких тривиальных алгоритмов с 10000 значений проще заполнить таблицу в памяти, будет занимать всего 10кб.

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

> Да так оно и есть. Мой алгоритм будет анализировать его тоже много времени, практически бесконечно.
И накой он тогда?

> Но есть случаи когда мой алгоритм полезен. Это например, когда алгоритм
А я тоже алгоритм придумал — если в программе встречается число 42, то она зависнет.

> зацикливается со сравнительно небольшим временем работы. Такие зацикливания можно определять и делать для них юнит тесты
Вот у тебя есть алгоритм, который на вход берёт 2 числа длиной до 1000 десятичных цифр и выдаёт на выходе их произведение. Но из-за ошибки он зависает на числах 42*12345678901234567890. Оцени шанс, что твой алгоритм найдёт эту пару.

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

.>GhostCoders wrote:

>>> > С помощью простейшего языка я методом перебора могу тебе дать гарантию
>>> > что он не зависнит, например, на 10000 входных значений.
>> .>Молодец. Только зачем это нужно?
>> В системах реального времени например. Даже могу дать гарантию что
>> алгоритм будет выполняться не дольше чем
>> N шагов.
.>Кому это нужно? Для таких тривиальных алгоритмов с 10000 значений проще заполнить таблицу в памяти, будет занимать всего 10кб.

Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать

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

>> Да так оно и есть. Мой алгоритм будет анализировать его тоже много времени, практически бесконечно.
.>И накой он тогда?

Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать

>> Но есть случаи когда мой алгоритм полезен. Это например, когда алгоритм
.>А я тоже алгоритм придумал — если в программе встречается число 42, то она зависнет.

>> зацикливается со сравнительно небольшим временем работы. Такие зацикливания можно определять и делать для них юнит тесты
.>Вот у тебя есть алгоритм, который на вход берёт 2 числа длиной до 1000 десятичных цифр и выдаёт на выходе их произведение. Но из-за ошибки он зависает на числах 42*12345678901234567890. Оцени шанс, что твой алгоритм найдёт эту пару.

Вероятность будет мизерной.

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

GC>Да так оно и есть. Мой алгоритм будет анализировать его тоже много времени, практически бесконечно.

Об этом как раз и говорил Тьюринг — подобные анализаторы бесполезны, т.к. будут работать столько же по времени, сколько и алгоритм >_<

Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать

Какая разница, существует ли бесполезный анализатор или нет? Да и какой это "анализатор", честно говоря... Когда он не анализирует, а выполняет алгоритм. Что он ещё делает — см. ниже.

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

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

Это я уже давно знаю. Я смогу доказать что такие методы есть и работают.

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

т.е. что есть метод, который на все 100% для любого алгоритма всё раскажет и покажет?

Думаю, что из релиза Вы бы выкинули полный перебор всех вариантов, а таки сделали бы анализатор, который по условиям if и циклов подбирал бы только граничные значения (скажем, на условие if ( a < 0 ) { ... } можно взять два граничных значения: a < 0 (a == -1) и a > 0 (a == 1)). Да, это хорошая идея — если состояния начали повторяться, значит, код зависнет. Да, количество состояний конечно! Нельзя перехитрить такой анализатор, только сделать так, чтобы он "анализировал" до конца света... Или исчерпал всю свободную память.
Но Вы же сами говорили, что в отличие от машины Тьюринга, память у компьютеров ограничена. В какой такой памяти Вы будете хранить состояния вычислений?

int64_t func ( int64_t const a, int const b ) {
    for ( int64_t i = 0; i < b; ++i ) {
        if ( a + i + b == SOMETHING_CONST ) {
            return i;
        }
    }
    return 0;
}

Здесь всего лишь одна переменная, всё остальное — константы. Но всё равно, Вы задумались, где будете хранить максимум 2^64 8-байтных состояний этой простейшей функции?
А так:

double func2 ( double const a ) {
    for ( double i = 0; i < a; i += 0.000001 ) {
        double b = 42 * sqrt ( a + i );
        double c = 16 - b + i;
        if ( ( b * 2. ) - ( c / 2. ) + pow ( 2., i ) == SOMETHING_CONST ) {
            return i;
        }
    }
    return 0;
}

Это сколько памяти надо? Изменяются i, изменяется b, c тоже изменяется! А количество вызовов? При достаточно большом "a" это сколько памяти под состояния уйдёт и сколько она будет сравниваться с предыдущими? А если эти два метода вызываются из третьей функции? Или хотя бы первый метод вызывается пару раз из третьей функции.

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

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

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

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

Вдогонку: ещё один пример, который не возьмёшь методом, основанным на сохранении состояний.
Сортировка массивов.
Да, обычная сортировка, хоть пузырьком, хоть быстрая.
Если, скажем, размер массива 5 миллиардов элементов (64-битная система), а для индексы использованы 32-битные — то она может зависнуть... Но прежде зависнет/грохнется анализатор, который не смог переварить такой объём данных. Это при том, что сортировка довольна элементарна (тот же пузырёк) и в самой программе, в большинстве случаев, используется для коротких массивов...

GhostCoders wrote:

> Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать
Существует способ перебрать 10000 значений? Алгоритм brute force думаю придумали сотни лет назад.

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

GC>Можете дать ссылку на такой Аттрактор? Очень интересно

здесь

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

FR>>Склероз мне подсказывает теорему Кантора
К>А толку?
FR>>И этот же склероз подсказывает что Геделева нумерация как раз и выделяет счетное подмножество вычислимых формул из общего несчетного множества формул вообще (под формулой имеется в виду отображение счетного множества на четное же множество)
К>Ничего она не выделяет, какие-то это твои домыслы. А счётное множество счётных множеств (наверное, ты это имел в виду под отображением) ровно также счётно. Тебя ведь не удивляет тот факт, что мощность множества рациональных чисел счётно?

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

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

.>Курилка wrote:

>> Докажи.
.>Диагонализацией доказывается.
Ну вот и докажи

>> По-моему для языков можно также ввести нумерацию (формального
>> доказательства не дам ) и получим счётное множество счётных множеств.
.>Счётное множество счётных множеств — счётно.

.>Какой бы мы язык не вводили, он всегда будет определять не более, чем конструктивное множество объектов.
.>Скажем, все действительные числа описать формальным языком нельзя.

Т.е. ты говоришь, что есть формулы, которые записываются не языком, а чем-то ещё?
Приведи пример.

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

К>Т.е. ты говоришь, что есть формулы, которые записываются не языком, а чем-то ещё?
К>Приведи пример.

Та же проблема останова. Ее нельзя выразить в виде алгоритма. Но существовать как абстрактной формуле ей никто ни запрещает.

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

GC> Смысл в следующем. Что цикл зависания не может превосходить число внутренних состояний такой машины.

То есть твой анализатор практически бесполезен

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

.>GhostCoders wrote:

>> Ну существует же анализатор в принципе-то.... вот это я пытаюсь доказать
.>Существует способ перебрать 10000 значений? Алгоритм brute force думаю придумали сотни лет назад.

однако каков будет по твоему критерий останова?

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

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

AF>Какая разница, существует ли бесполезный анализатор или нет? Да и какой это "анализатор", честно говоря... Когда он не анализирует, а выполняет алгоритм. Что он ещё делает — см. ниже.

Тут стирается граница между анализом и выполнением.
У нас есть M состояний (к сожаления M бывает часто огромным).
Из каждого состояния S (которое есть элемент множества M) мы детерминированно переходим
в другое состояние S*.
Есть подмножество M, которое есть начальные состояния (отличаются лишь входными данными).
Есть подмножество M, которое есть конечные состояния (на последней строке алгоритма, отличаются лишь состоянием резудьтирующих и временных переменных).

Рисуем М точек и соединяем их направленными стрелками. Получаем граф выполнения программы.
Если в графе есть циклы, значить здесь есть потенциальные зависания.
Зависания есть если в такой цикл можно попасть из какого-либо начального состояния.

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

Есть быстрый способ проверить переходим ли мы из состояния S в состояние S* (за один шаг).
Однако нет быстрого способа определить наличие циклов в таком графе.


AF>Вот если бы анализировался исходный код, проверялись граничные условия, что-нибудь_ещё,_что_неизвестно_и_поэтому_нет_решения_проблемы_останова и всё это без запуска целевой программы... Тогда бы я понял поднятую здесь шумиху, разговоры о математике, ссылки на статьи и т.п.

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

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

AF>Получается что так.
AF>[/q]
AF>Получено решение не для общего случая, а для частного — когда система "замкнута". Неразрешимая проблема осталась таковой.

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


Бесконечная лента хранит в каждой ячейке символ. Так что полное состояние системы бесконечно.

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

AF>>

AF>>"Если где-либо в дробной части числа "пи" встречается последовательность цифр 84327411834783744390087539249 — завершить цикл"

AF>>Что на это скажет анализатор?

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

Есть способ быстрого вычисления произвольной двоичной цифры числа пи без вычисления предыдущих цифр (см. ссылку здесь). Предлагается его запрограммить и прогнать через анализатор. Десятичную последовательность "843274118..." искать тяжеловато. Предлагается определить, содержится ли в двоичном представлении числа пи представление (например, Windows-1251) фразочки "Алан Тьюринг что-то накосячил со своей теоремой".