GhostCoders wrote:

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

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

Курилка wrote:

>> > Докажи.
> .>Диагонализацией доказывается.
> Ну вот и докажи
Да то же доказательство, что для действительных чисел. Построить таблицу "всех" формальных языков и выбирать с каждым элементом неравный язык. В общем в таком док-ве есть некие тонкие моменты, проще свести к действительным числам и сослаться уже на доказанную теорему.

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

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

.>GhostCoders wrote:

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

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

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

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

Плюс если алгоритм долго выполняется это не значить что он завис. Если же он перешел в одно из предыдуших состояний,
100% что он завис.

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

GC>Тут стирается граница между анализом и выполнением.
А не должна.

GC>Можно скажем ожидать зависания на на всех строках программы, а только на тех где есть условные переходы.
GC>Запоминать состояние не всех переменных, о только тех, которые влияют на состояние переменных, участвующих в условии.
GC>Незнаю насколько это
Повторюсь: с массивами что делать? Не всех переменных — хорошо, только срезать из них множно будет немного.
Отсюда, например, не срезать ни i, ни j, ни k:

for ( int i = 0; i < x; ++i ) {
    for ( int j = 0; j < i; ++j ) {
        for ( int k = 0; k < j; ++k ) {
            // ...
        }
    }
}

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

AF>Повторюсь: с массивами что делать? Не всех переменных — хорошо, только срезать из них множно будет немного.
AF>Отсюда, например, не срезать ни i, ни j, ни k:

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

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

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

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

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

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

А цитированое выше вообще не понимаю, зачем Вы привели. Если количество состояний системы бесконечно, то какая разница, есть у неё ввод/вывод или нет? Фактически и на современных компьютерах большое число состояний (которые могут повторяться, но потом переходить в отличные от прошлых разов состояния) можно получить, всего лишь добавив ввод/вывод.

---

Я теперь понимаю, почему Вы не хотели принимать пример с числом "пи". Анализатор просто не сможет его разгрызть.
GhostCoders, не закрывайте глаза на контрпримеры, коих приводили уже множество.

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

Не надо больше, всё равно это уже немногим интересно

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

GC> Хочется сказать, что многие программисты, изучая в институте машину Тьюринга,
GC> конечно слышили о проблеме неразрешимости, так же как и о "вечном двигателе" и попытках создать его.
GC> Но есть одно НО, машина Тьюринга бесконечна, для конечных машин, проблема зависания все же
GC> РАЗРЕШИМА, хотя бы в теории. Про это обычно забывают, и в английской вики про это пишут,
GC> что это распространенное заблуждение, что неразрешимость проблемы машины Тьюринга переносят
GC> на конечные компьютеры. http://en.wikipedia.org/wiki/Halting_problem — сомтрите "Common pitfalls".

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

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

AF>>Повторюсь: с массивами что делать? Не всех переменных — хорошо, только срезать из них множно будет немного.
AF>>Отсюда, например, не срезать ни i, ни j, ни k:

FR>Да не нужно массивов, достаточно рекурсивных функций фибоначи или аккермана, там переменных то пара штук, но комбинаторный взрыв на числе вызовов, никакой памяти это проанализировать не хватит.

Та я уже не знаю, что ещё в пример привести
Те примеры, на которые "анализатор" не может вразумительно ответить, GhostCoders пропускаются. А работает "анализатор" в "простейших случаях": что считать простейшими случаями — непонятно... Там чуть ли не одного цикла достаточно, чтобы случай резко перестал быть простейшим. А, спрашивается, зачем такой анализатор, который должен искать зависания но не может анализировать циклы?

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

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

AF>>>Повторюсь: с массивами что делать? Не всех переменных — хорошо, только срезать из них множно будет немного.
AF>>>Отсюда, например, не срезать ни i, ни j, ни k:

FR>>Да не нужно массивов, достаточно рекурсивных функций фибоначи или аккермана, там переменных то пара штук, но комбинаторный взрыв на числе вызовов, никакой памяти это проанализировать не хватит.

AF>Та я уже не знаю, что ещё в пример привести
AF>Те примеры, на которые "анализатор" не может вразумительно ответить, GhostCoders пропускаются. А работает "анализатор" в "простейших случаях": что считать простейшими случаями — непонятно...

простейшие случаи — это

1. программа зависает с периодом смены состояний не очень большим (ну скажем до миллиарда на наших компьютерах)
2. тратит на выполнение не больше миллиарда шагов

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

>>> Докажи.
.>>Диагонализацией доказывается.
К>Ну вот и докажи
http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

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

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

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

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

http://www.netfunny.com/rhf/jokes/01/Jun/pi.html

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

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

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

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

Например анализируемая программа использует N бит данных и состоит из C строк кода.
Анализатору надо в этом случае O((2^N)*C) бит памяти (в худшем случае).

Поэтому Анализатор не может анализировать сам себя.

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

К>>Расскажи.
FR>Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
FR>невозможны в машине Тьюринга, за подробностями гугли Пенроуза.
Ррррр!!!!! Почему всегда Пенроуза цитируют вместе с упоминанием чуши?

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

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

К>>Плюс я не уверен, что принципы TFP не применимы к квантовым вычислениям (хотя зарекаться не буду, т.к. не очень в них разбираюсь)
FR>Насколько я понимаю никто пока ни доказал что квантовые вычисления эквивалентны машине Тьюринга, обратное тоже не доказано.
"Квантовые вычисления" вообще — это расплывчатое понятие.

Все существующие и планируемые системы квантовых компьютеров — равномощны МТ и могут быть симулированы на обычном компьютере.

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

GC>Например анализируемая программа использует N бит данных и состоит из C строк кода.
GC>Анализатору надо в этом случае O((2^N)*C) бит памяти (в худшем случае).

Легко написать однострочную программу которая использует комбинаторно растущую память:

inline int fib(int n)
{
       return n<2 ? 1 : fib(n-1)+fib(n-2);
}

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

C>Все существующие и планируемые системы квантовых компьютеров — равномощны МТ и могут быть симулированы на обычном компьютере.

Мне казалось что нет, наверно склероз подвел, или воздейcтвие Пенроуза

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

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

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

GC>> Хочется сказать, что многие программисты, изучая в институте машину Тьюринга,
GC>> конечно слышили о проблеме неразрешимости, так же как и о "вечном двигателе" и попытках создать его.
GC>> Но есть одно НО, машина Тьюринга бесконечна, для конечных машин, проблема зависания все же
GC>> РАЗРЕШИМА, хотя бы в теории. Про это обычно забывают, и в английской вики про это пишут,
GC>> что это распространенное заблуждение, что неразрешимость проблемы машины Тьюринга переносят
GC>> на конечные компьютеры. http://en.wikipedia.org/wiki/Halting_problem — сомтрите "Common pitfalls".

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

Это меня и настрораживает. Мне кажется, что парадокс брадобрея можно применить и к другим объектам, да к чем угодно!
Замените, свого "алгоритм" в доказательстве Тьюринга любым другими словом и понятием и получается, что мы прийдем к такому же результату!

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

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

GC>>Например анализируемая программа использует N бит данных и состоит из C строк кода.
GC>>Анализатору надо в этом случае O((2^N)*C) бит памяти (в худшем случае).

FR>Легко написать однострочную программу которая использует комбинаторно растущую память:
FR>

FR>inline int fib(int n)
FR>{
FR>       return n<2 ? 1 : fib(n-1)+fib(n-2);
FR>}
FR>

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

во вторых есть рекурсия, а где есть рекурсия есть и стек, и указатель стека.
стек частно бывает достаточно большого объема (ну скажем 256KB или даже намного более).
Так что данная программа использует около ~5-10 строк кода (набольшое число, я согласен),
и достаточно большое число памяти, которое мы вынуждены все-равно ограничить. Скажем 256*8*1024 бит данных для
стека.

Поэтому АНАЛИЗАТОР должен иметь O( 2^(256*8*1024)*10 ) бит данных для анализа

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

GC>простейшие случаи — это

GC>1. программа зависает с периодом смены состояний не очень большим (ну скажем до миллиарда на наших компьютерах)
GC>2. тратит на выполнение не больше миллиарда шагов

Миллиард? Та она на рекурсии быстрее загнётся или в тех же циклах! Я приводил пример трёх вложенных циклов в которых ещё каждый зависит от второго. Не доживёт "анализатор" до миллиарда шагов, не доживёт! >_< У Вас не будет int8, у Вас будет в реальных условиях int64, double и много-много вложенных вызовов функций/циклов!

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

Например анализируемая программа использует N бит данных и состоит из C строк кода.
Анализатору надо в этом случае O((2^N)*C) бит памяти (в худшем случае).

Поэтому Анализатор не может анализировать сам себя.

>_<:

for ( int64_t i = 0; i < x; ++i ) {
    for ( int64_t j = 0; j < i; ++j ) {
        for ( int64_t k = 0; k < j; ++k ) {
            printf ( ... );
        }
    }
}

(что-то мне подсказывает, что O((2^N)*C) неверна, но проверять уже не буду).

Программа (не считая printf) использует N = 64 * 3 == 192 бит памяти, состоит из, скажем, 4 строк кода. Немного, правда?

Считаем по формуле: ((2 в степени 192 (ой!)) * 4) бита памяти. 2 в 192 это 6.2771017353866808e+057, вроде бы 6277101735386680763835789423207666416102355444464034512896 бит памяти. Умножаем на 4. Получаем 2,5108406941546723055343157692831e+58 или 25108406941546723055343157692830665664409421777856138051584 бит памяти. Делим на CHAR_BIT на платформе x86 (8), получаем:
3,1385508676933403819178947116038e+57 или 3138550867693340381917894711603833208051177722232017256448 байт памяти. Если я нигде не ошибся, то это 2,9230032746618058364073696654318e+48 или 2923003274661805836407369665432566039311865085952 гигобайт памяти. Для Вас это небольшое число? Если да, подарите мне HDD или флешку с таким объёмом памяти
Четыре строки, всего 192 бита памяти! А уже нереальный, не бесконечный, но стремящийся к бесконечности объём памяти в худшем случае.
Более реалистичный пример:

for ( int i = 0; i < x; ++i ) {
    printf ( "%d", i );
}

((2 ^ 32) * 2 ) == 4294967296 * 2 == 8589934592 бит памяти или 1073741824 байт памяти или 1 гигобайта памяти. 1 гигобайт для простого цикла? А т.к. Вы проверяете перебором всех вариантов, то худший случай всё равно будет.

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

>>> однако каков будет по твоему критерий останова?
.>>А у тебя какой?
GC>Если мы перешли в предыдущее состояние, в котором раньше уже были — то значить зависли.
Примитивно. Вот скажем возьмём простейшую функцию:

int64 fibonnachi(int64 n)
{
  return n==0||n==1 ? 1 : fibonnachi(n-2) + fibonnachi(n-1);
}

проанализируй её своим анализатором.

>>> например наш алгоритм выполняется, выполняется.... как определить что он
>>> завис?
.>>Ограничить максимальное количество шагов.
GC>В твоем случае ты всегда будешь дожидаться этого максимального числа шагов, чтобы определить зависание алгоритма.
GC>В моем это возможно намного раньше.
Неочевидно. Ведь он у тебя будет памяти жрать немеряно, а жрать память — тоже время нужно. Засвопит у тебя всё.
Ну ладно, даже допустим ты создал оптимизированный brute force, который в некоторых случаях работает быстрее решения в лоб. И что?

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