Для всех тех, у кого несчётность R вызывает сомнения

[AlexDem]

Xaositect в сообщении #279409 писал(а):

Интересно, как Вы будете строить эту свою конечную таблицу.

Не понял вопроса, как и более раннего возражения по поводу памяти под программу. Роль теории в программировании никто не преуменьшает, всегда полезно знать, что происходит. Но всё же - связь здесь не прямая, результаты именно что можно заимствовать, но не применять напрямую. Почему у программистов не сносит крышу, если программе пытаются подсунуть для обработки данные, которые банально не умещаются в память? По поводу построения таблицы - очень просто, занесу в один столбец все возможные на входе строки, а во второй - ответ "да" или "нет". Алгоритмически всё легко реализуется операторами "if... then... else..."

vek88 в сообщении #279414 писал(а):

3. И представьте себе ужас Вашего положения - вам тычут ... глюк.
4. Вы его устраняете, а Вам ... новый глюк.

Пролог я изучал когда-то, но уже успел забыть. И про указываемую Вами проблему, кажется, тоже слышал. Но в итоге я заменю весь код интерпретатора на такую же таблицу, которую построил выше для Xaositect и получу безглючную программу. По-моему, всё очевидно, не стоит только пытаться притянуть сюда теорию вычислимости насильно.

[vek88]

Ales в сообщении #279407 писал(а):

vek88 в сообщении #279400 писал(а):

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

А есть ли конкретные примеры? И зачем нужен этот Пролог?

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

Зачем нужен Пролог вообще? Покопайтесь в Интернете - там найдете ответ. Мне он был нужен здесь в качестве примера алгоритмически неразрешимой задачи.

[Ales]

Xaositect в сообщении #279424 писал(а):

Ales в сообщении #279422 писал(а):

Как то я искал минимум квадратичной формы на многомерном тетраэдре, (минимум дисперсии при заданном мат ожидании для инвестиционного портфеля). Теоретически эта задача элементарная. Практически же я ее не мог решить, придумал какой-то алгоритм типа спуска по градиенту. К счастью, сама задача не имела смысла.

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

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

[vek88]

Maslov в сообщении #279408 писал(а):

vek88 в сообщении #279400 писал(а):

А беда в том, что любой написанный Вами интерпретатор на каком-то запросе к этой программе сглючит - не даст правильного ответа!

А нельзя немного подробнее? Это какой-то глубокий теоретический результат или просто следствие правила "каждая программа содержит по крайней мере одну ошибку"?

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

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

А результат про интерпретатор (более строго про несуществование точного интерпретора) - это очевидное следствие. Ведь если задача алгоритмически неразрешима, то не существует и программа для ее решения. А, следовательно, любая программа для решения такой задачи обязана где-то глючить.

[Xaositect]

AlexDem в сообщении #279428 писал(а):

Не понял вопроса, как и более раннего возражения по поводу памяти под программу. Роль теории в программировании никто не преуменьшает, всегда полезно знать, что происходит. Но всё же - связь здесь не прямая, результаты именно что можно заимствовать, но не применять напрямую. Почему у программистов не сносит крышу, если программе пытаются подсунуть для обработки данные, которые банально не умещаются в память? По поводу построения таблицы - очень просто, занесу в один столбец все возможные на входе строки, а во второй - ответ "да" или "нет". Алгоритмически всё легко реализуется операторами "if... then... else..."

Ну, допустим, вам нужно, скажем, вычислить колмогоровскую сложность(классический пример невычислимой функции) для всех двоичных строк длины не более $10^3$. Вполне определенная задача на конечном множестве.
Начнем с того, что таких строк $2^{10^3}$, и на каждую у вас в табличке один if, ну да ладно, пусть не $10^3$, пусть $50$. Всего-то ~1000 терабайт.
Но это не самое страшное. Для того, чтобы табличку построить, нужно эту сложность для каждой строки все-таки как-то узнать. Ну, это не общая проблема, можно придумать модель, у которой константа в теореме Чейтина достаточно большая и найти в ней сложность. Но это потребует просто огромного перебора. Жизни не хватит, чтобы эту программу построить.

-- Пн янв 11, 2010 00:20:25 --

vek88 в сообщении #279429 писал(а):

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

Так десятая проблема Гильберта же. Дано уравнение вида $f(x_1,\dots,x_k) = 0$, $f$ - это полином. Определить, есть ли у него рациональные решения.

[AlexDem]

Xaositect в сообщении #279436 писал(а):

Но это потребует просто огромного перебора. Жизни не хватит, чтобы эту программу построить.

Хм, ну и что? Я не обещал, что будет легко...

-- Пн янв 11, 2010 00:21:59 --

Xaositect в сообщении #279436 писал(а):

Определить, есть ли у него рациональные решения.

Перебором определим, если множество потенциальных решений ограничено.

[Xaositect]

AlexDem в сообщении #279437 писал(а):

Перебором определим, если множество потенциальных решений ограничено.

Не, само решение находить не надо, надо сказать, есть оно или нет.

[vek88]

AlexDem в сообщении #279428 писал(а):

Пролог я изучал когда-то, но уже успел забыть. И про указываемую Вами проблему, кажется, тоже слышал. Но в итоге я заменю весь код интерпретатора на такую же таблицу, которую построил выше для Xaositect и получу безглючную программу. По-моему, всё очевидно, не стоит только пытаться притянуть сюда теорию вычислимости насильно.

Интересно как Вы это сделаете? Кто же Вам вычислит эту таблицу? Ведь интепретатора у Вас пока нет. Вручную, что ли?

[AlexDem]

vek88 в сообщении #279442 писал(а):

Вручную, что ли?

Я все свои программы пишу вручную, что делать... Или Вы хотите оспорить, что результат моей работы будет являться программой? Интересно...

[vek88]

AlexDem в сообщении #279443 писал(а):

vek88 в сообщении #279442 писал(а):

Вручную, что ли?

Я все свои программы пишу вручную, что делать... Или Вы хотите оспорить, что результат моей работы будет являться программой? Интересно...

If somebody says he knows all the answers,
It means that he does't know all the questions.

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

[AlexDem]

vek88 в сообщении #279444 писал(а):

Во-первых, таблица бесконечная.

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

vek88 в сообщении #279444 писал(а):

Вы не сможете вручную просчитать все ответы на все запросы даже за 1000 Ваших жизней.

Ну и что? Потомки продолжат..

Xaositect в сообщении #279439 писал(а):

Не, само решение находить не надо, надо сказать, есть оно или нет.

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

[Xaositect]

AlexDem в сообщении #279445 писал(а):

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

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

[Maslov]

vek88 в сообщении #279435 писал(а):

А результат про интерпретатор (более строго про несуществование точного интерпретора) - это очевидное следствие. Ведь если задача алгоритмически неразрешима, то не существует и программа для ее решения.

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

[vek88]

AlexDem в сообщении #279443 писал(а):

vek88 в сообщении #279442 писал(а):

Вручную, что ли?

Я все свои программы пишу вручную, что делать... Или Вы хотите оспорить, что результат моей работы будет являться программой? Интересно...

Виноват, забыл самое главное - то, с чего начали. Алгоритма то у Вас нет, т.е. нет метода составления Вашей таблицы. Ведь упомянутая мной Пролог-программа лишь а определенном смысле перечисляет факты, или строки Вашей таблицы.

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

1. Мой запрос-факт встретился в таблице. Вы даете ответ - да, запрошенный факт имеется в моей таблице.

2. Мой запрос отсутствует в Вашей таблице. И что же, позвольте спросить, в этом случае? Это значит, что Ваша программа зависла!?

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

А вообще то:

Всем давно пора уж спать.
Спи, а то вот встану,
Позову декана,
Спи, давно пора уж спать.

[AlexDem]

Я уже давно не спорю, а думаю, применима ли теория вычислимости к программисту

vek88 в сообщении #279454 писал(а):

Чувствуете, куда я клоню. Забудем про Пролог-программу и скажем проще. Пусть у Вас уже есть программа перечисления Вашей бесконечной таблицы. <...>:
1. Мой запрос-факт встретился в таблице. Вы даете ответ - да, запрошенный факт имеется в моей таблице.
2. Мой запрос отсутствует в Вашей таблице. И что же, позвольте спросить, в этом случае? Это значит, что Ваша программа зависла!?

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

vek88 в сообщении #279454 писал(а):

Виноват, забыл самое главное - то, с чего начали. Алгоритма то у Вас нет, т.е. нет метода составления Вашей таблицы.

Да, видимо, у меня зачастую нет метода составления таблицы, а вот алгоритм есть - это сама таблица. Или запрограммированная машина Тьюринга (пускай и неполноценная в виде конечного автомата) уже не является алгоритмом?..