Здравствуйте, мыщъх, Вы писали:

М>насколько я понял, доказательства для общего случая не существует.
Общий случай в вакууме не ясен.
М>а что вы думаете?
Если можно представить цикл в виде некоей функции, то можно попробовать раскрыть неопределённость. Самое сложное тут это представить цикл как функцию или набор функций. Можно попробовать выразить цикл через рекуррентную последовательность и как-то её обработать, после чего получить некоторые признаки циклов которые могут быть вычислены за бесконечное время или даже конечно время.

Здравствуйте, мыщъх, Вы писали:

М>а что вы думаете?

И, кстати, если бы я получил посылку от Джа, то задумался бы скорее о выполнении конечного цикла за бесконечное время

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

Q>Тем не менее, очень интересно взглянуть на статьи, о которых говорил мыщъх.

Одна из наиболее известных на эту тему: http://arxiv.org/pdf/math/9808093.pdf

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

_>не можем определить конечность или бесконечность алгоритма в общем случае?

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

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

KV>Мы не можем _разрешить_ бесконечность его выполнения не выполнив его. Дать же определение бесконечному циклу в терминах теории множеств нам это совершенно не мешает.

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

Бывают ли бесконечные алгоритмы?

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

S>Я не очень понимаю, как вы получили 1/k из k/pow(2, k).

Я привел пример того, что даже если k-й член ряда — бесконечно мал, это не гарантирует его сходимость

S>Скажем, сумма ряда 1/k символической оптимизации не поддаётся. А вот если речь идёт об арифметике даблов, то начиная с конкретного K0 мы получаем при делении floating underflow и дальнейшее суммирование бессмысленно.

Это проблема даблов. Гармонический ряд ведет себя как логарифм (есть даже формула которая позволяет выразить его частичную сумму как логарифм n + константа).

Здравствуйте, __kot3, Вы писали:
__>Я привел пример того, что даже если k-й член ряда — бесконечно мал, это не гарантирует его сходимость
Это в символьной математике. А в математике даблов (которой оперирует большинство промышленых языков программирования) никаких бесконечно малых нет.

S>>Скажем, сумма ряда 1/k символической оптимизации не поддаётся. А вот если речь идёт об арифметике даблов, то начиная с конкретного K0 мы получаем при делении floating underflow и дальнейшее суммирование бессмысленно.

__>Это проблема даблов. Гармонический ряд ведет себя как логарифм (есть даже формула которая позволяет выразить его частичную сумму как логарифм n + константа).
Спасибо, я в курсе, как себя ведёт гармонический ряд — матан мне преподавали

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

_>Твое определение бесконечного по времени цикла требует того чтобы цикл априори был бесконечным, иначе это будет определение конечного цикла
Простите, это наукообразная чушь.
Определение бесконечного цикла не требует никакой "априорности". Это если под словом "определение" имеется в виду definition, а не detection.
Определение — очень простое: если для любого целого N на итерации номер N цикл всё ещё не закончился остановом, то это — бесконечный цикл.
_>Бывают ли бесконечные алгоритмы?

10 GOTO 10

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

_>>Твое определение бесконечного по времени цикла требует того чтобы цикл априори был бесконечным, иначе это будет определение конечного цикла
S>Простите, это наукообразная чушь.
Не эксперт в этой области и просто хочу понять. И у меня есть подозрения, что кто-то что-то не договаривает, а по моему мировоззрению, неполная информация есть ложь.


S>Определение бесконечного цикла не требует никакой "априорности". Это если под словом "определение" имеется в виду definition, а не detection.
S>Определение — очень простое: если для любого целого N на итерации номер N цикл всё ещё не закончился остановом, то это — бесконечный цикл.

Что такое целое число в терминах МТ? Чем отличается дефинишн конечного алгоритма от детекшн в МТ? Кажется у этой проблемы есть общеизвестное название?

_>>Бывают ли бесконечные алгоритмы?

S>
S>

S>10 GOTO 10
S>

Это _алгоритм_ в какой-то теории? Или неизвестно что?
Я знаю, что есть бесконечное множество алгоритмов (которые конечны по определению)? А вот про бесконечные алгоритмы не слышал?

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

S>Это в символьной математике. А в математике даблов (которой оперирует большинство промышленых языков программирования) никаких бесконечно малых нет.

Это лишь означает, что в математике даблов нельзя посчитать частичную сумму более чем 10^16 членов этого ряда. Если нужно суммировать меньшее количество, то думаю все получится, если начинать суммировать с конца.

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

_>Что такое целое число в терминах МТ?
То же самое, что и в обычной алгебре.

_>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
Всем.

_>Кажется у этой проблемы есть общеизвестное название?
Да, halting problem, она же — проблема останова.
_>Это _алгоритм_ в какой-то теории? Или неизвестно что?
_>Я знаю, что есть бесконечное множество алгоритмов (которые конечны по определению)? А вот про бесконечные алгоритмы не слышал?
Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
Ну так halting problem как раз в том, чтобы понять, глядя на "вычислительный метод" (в терминологии Кнута), является ли он алгоритмом или нет.
Тьюринг доказал, что невозможно построить алгоритм, который бы с уверенностью определял, завершится ли произвольная МТ за конечное количество шагов на произвольном вводе.

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

__>Это лишь означает, что в математике даблов нельзя посчитать частичную сумму более чем 10^16 членов этого ряда. Если нужно суммировать меньшее количество, то думаю все получится, если начинать суммировать с конца.
Это означает, что одна и та же формула имеет разную семантику в символьной математике и в математике даблов.
Точно так же, как 5000000000+5000000000 в арифметике даст десять миллиардов, а в арифметике uint даст десять миллиардов по модулю 2^32.
Как трактовать такие формулы — выбор компилятора. Mathematica и Wolfram Alpha трактуют её одним образом; компилятор С++ — другим.

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

_>>Что такое целое число в терминах МТ?
S>То же самое, что и в обычной алгебре.
Жду конфигурацию МТ, которая строит целые числа (-inf, +inf), пока без алгебры.

_>>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
S>Всем.
А именно?

_>>Кажется у этой проблемы есть общеизвестное название?
S>Да, halting problem, она же — проблема останова.
_>>Это _алгоритм_ в какой-то теории? Или неизвестно что?
_>>Я знаю, что есть бесконечное множество алгоритмов (которые конечны по определению)? А вот про бесконечные алгоритмы не слышал?
S>Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
Неформальное? Вроде как раз у бесконечных алгоритмов большие проблемы с формализацией.

S>Ну так halting problem как раз в том, чтобы понять, глядя на "вычислительный метод" (в терминологии Кнута), является ли он алгоритмом или нет.
S>Тьюринг доказал, что невозможно построить алгоритм, который бы с уверенностью определял, завершится ли произвольная МТ за конечное количество шагов на произвольном вводе.
То есть Тьюринг показал, что доказательство конечности алгоритма должно входить в определение конкретного алгоритма, иначе это не алгоритм.

Здравствуйте, fin_81, Вы писали:
_>Жду конфигурацию МТ, которая строит целые числа (-inf, +inf), пока без алгебры.
Что такое "строит"?

_>>>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
S>>Всем.
_>А именно?
Определение — это формальная конструкция, описывающая свойства определяемого объекта.
Детектирование — это процесс проверки конкретного объекта на предмет наличия соответствующих свойств.

S>>Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
_>Неформальное? Вроде как раз у бесконечных алгоритмов большие проблемы с формализацией.
Ну да, неформальное. Собственно МТ, ЧРФ, и лямбда-исчисление и появились в результате попыток формализовать понятие "алгоритм".
У Тьюринга аналогом понятия алгоритм как раз является конкретная МТ. Любая МТ описывает некое вычисление. В том числе и та, которая аналогична 10 GOTO 10.
К сожалению, не все такие вычисления когда-либо заканчиваются.

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

_>>Жду конфигурацию МТ, которая строит целые числа (-inf, +inf), пока без алгебры.
S>Что такое "строит"?
Например упорядоченное множество {1,2,3} можно представить как {|,||,|||}. Как построить множество целых чисел?

_>>>>Чем отличается дефинишн конечного алгоритма от детекшн в МТ?
S>>>Всем.
_>>А именно?
S>Определение — это формальная конструкция, описывающая свойства определяемого объекта.
S>Детектирование — это процесс проверки конкретного объекта на предмет наличия соответствующих свойств.

S>>>Вы намекаете на неформальное определение алгоритма, которое подразумевает конечность?
_>>Неформальное? Вроде как раз у бесконечных алгоритмов большие проблемы с формализацией.
S>Ну да, неформальное. Собственно МТ, ЧРФ, и лямбда-исчисление и появились в результате попыток формализовать понятие "алгоритм".
S>У Тьюринга аналогом понятия алгоритм как раз является конкретная МТ. Любая МТ описывает некое вычисление. В том числе и та, которая аналогична 10 GOTO 10.
S>К сожалению, не все такие вычисления когда-либо заканчиваются.

В общем ясно, у нас разное понимание алгоритма. К сожалению, дальнейший разговор для меня не имеет смысла как бесконечный "алгоритм" 10 goto 10.

Здравствуйте, fin_81, Вы писали:
_>Например упорядоченное множество {1,2,3} можно представить как {|,||,|||}. Как построить множество целых чисел?
что такое {|, ||, |||}? Последовательность состояний ленты в МТ?

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

_>у нас разное понимание алгоритма.

У вас с Тьюрингом — определенно разное

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

KV>У вас с Тьюрингом — определенно разное

Алгоритм по Тьюрингу должен вычисляться (вычисляться с достижением конечного состояния) на машине Тьюринга. Это аксиома. Вроде.

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

_>Алгоритм по Тьюрингу должен вычисляться (вычисляться с достижением конечного состояния) на машине Тьюринга. Это аксиома. Вроде.

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

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

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

Написанный ответ куда-то пропал. Писать не хочу. В общем сдаюсь. Пусть будет как будет.