м-д доказательства от противного к "парадоксу лжеца"

[Андрей АK]

Ираклий в сообщении #264023 писал(а):

Похоже, Вы не очень понимаете, что такое кодирование.

Здесь кодирование не применяется. Да и не принципиально.
Но если вы хотите все свойства алгоритма закодировать в числа ... то для данного конкретно алгоритма (m=n) вам придётся использовать бесконечно большие числа (поскольку это бесконечно большой алгоритм(в смыле количества слов языка требующихся для его записи)) и далее см. рассуждение о том, что бесконечно большие алгоритмы не учавствуют в этом перечислении и на него нет ссылки, (т.е. нет кода).

[Ираклий]

Андрей АK в сообщении #264025 писал(а):

Но если вы хотите все свойства алгоритма закодировать в числа ...

У слова "синий" тоже бесконечно много свойств. Оно двухсложное, русское, означает цвет и т.д. и т.п. Но главное - у него конечное число символов. Поэтому мы можем закодировать его натуральным числом.

Алгоритм - это текст, конечный текст. Любой конечный текст можно закодировать натуральным числом. Причем этот текст можно будет однозначно по этому числу востановить.

Андрей АK в сообщении #264025 писал(а):

Здесь кодирование не применяется.

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

Цитата:

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

[Андрей АK]

Ираклий в сообщении #264027 писал(а):

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

Цитата:

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

Мало ли что там имеется в виду.
Конечным числом символов ЭТОТ алгоритм не закодируешь.
Это утверждение можно и не доказывать (доказывать должен тот, кто утверждает обратное).
Но можно и попытатся доказать: треугольная структура нумерации пар натуральных чисел предполагает , что в каждом случае вызова ,алгоритмом A, какого из собственных вызовов, кодируются все подвызовы:
Вот кодируется обработка алгоритмом A ,каких-то алгоритмов n01,n02,n03 без параметров ... назовем это ссылкой нулевого порядка:
A(n01,-),A(n02,-),A(n03,-),...
Ссылки первого порядка:
A(A,n01),A(A,n02),A(A,n03),... - это проверка алгоритмом A самого себя на остановку ... с переданными параметрами - ссылки нулевого порядка.
Ссылки второго порядка:
(A,A(A,n1)), (A,A(A,n1)),(A,A(A,n1)),...
И так далее.
Поскольку все вышеперечисленные алгоритмы отличаются один от другого ... то для каждого из них потребуется уникальный код для кодирования, причем, длина такого кода для ссылки порядка N будет больше , чем для ссылки порядка n-1 на какую-то конечную величину c>1. (поскольку для каждого нового набора "ссылок" ,более высокого порядка, нам будут требоваться все новые и новые кода, которые можно взять только из все больших по размеру чисел, да и их сложность постоянно возрастает).
Далее, "идеальный" вариант (который нас интересует и код которого мы хотим узнать) - это предел порядка ссылок к бесконечности - когда алгоритм вызывает самого себя бесконечное число раз , получаем оценку размера этого алгоритма: он больше чем, "размер нулевой ссылки+ n*c" , при n - стемится к бесконечности, а с>1.

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

[Ираклий]

Андрей АK в сообщении #264108 писал(а):

Мало ли что там имеется в виду.
Конечным числом символов ЭТОТ алгоритм не закодируешь.

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

Андрей АK в сообщении #264108 писал(а):

алгоритм , вызывающий самого сабя,

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

[Андрей АK]

Ираклий в сообщении #264130 писал(а):

Андрей АK в сообщении #264108 писал(а):

Мало ли что там имеется в виду.
Конечным числом символов ЭТОТ алгоритм не закодируешь.

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

Похоже на заклинание.
Если дадите честное-причестное слово, что не бывает - то мне будет достаточно.

Ираклий в сообщении #264130 писал(а):

Андрей АK в сообщении #264108 писал(а):

алгоритм , вызывающий самого сабя,

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

Вызывает/ обрабатывает/ ссылается/ вызывает для обработки/ ... - какая разница?
Если это единственное возражение, то ладно , убедили ... заменю слово "вызывает" на "обрабатывает"... потом как ни будь ...

[man]

Андрей АK в сообщении #263933 писал(а):

Т.е. определение/создание множества m1 выглятит так:
m1=M|x(P(x)=1)
x-связаная переменная пробегающая все существующие множества (кроме m1)
P - порождающий признак, проверяющий x на удовлетворение условию.

А как Вам такая формула m1=M|x(P(x)=$\varnothing$) ?

Андрей АK в сообщении #263933 писал(а):

К стати, если я поставлю перед ним тот-же самый "квантор порождения" ...
m2=M|y(P(y)=1) ; m1=M|x(P(x)=1)
то при "втором проходе" множество m1 (не m2) уже будет считатся созданым и существующим ... но это уже получим другое множество (с четной степенью порождающего квантора) в качестве элемента содержащее "похожее на него" (на m2) множество m1 ... однако созданное при помощи квантора нечётной степени (т.е. совершенно другого множества).

У Вас множества m2=M|y(P(y)=1) ; m1=M|x(P(x)=1) равны ? Если нет, то как Вы собираетесь отличать какому из множеств принадлежит число $1$ - $\mathbb {N}_1$ или $\mathbb {N}_2$ например ?

Андрей АK в сообщении #264108 писал(а):

Вывод: алгоритм , вызывающий самого сабя, записывается бесконечным набором символов.

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

[Андрей АK]

man в сообщении #264722 писал(а):

А как Вам такая формула m1=M|x(P(x)=$\varnothing$) ?

Ну ... почему бы и нет?

man в сообщении #264722 писал(а):

У Вас множества m2=M|y(P(y)=1) ; m1=M|x(P(x)=1) равны ? Если нет, то как Вы собираетесь отличать какому из множеств принадлежит число $1$ - $\mathbb {N}_1$ или $\mathbb {N}_2$ например ?

А при чем здесь число?
Если мне надо узнать, принадлежит ли элемент множеству, я обращусь к определению и , если множество m2 создано позже m1 то m2 к m1 не принадлежит, все остальные члены у них общие (в том чисте и 1, если она удовлетворяет признаку).

man в сообщении #264722 писал(а):

Андрей АK в сообщении #264108 писал(а):

Вывод: алгоритм , вызывающий самого сабя, записывается бесконечным набором символов.

Если бы так, не было бы проблемы останова. Если считать, что есть бесконечные алгоритмы, то проблема останова для них не актуальна - они не остановятся на любом входе.

С чего вы взяли, что бесконечный алгоритм никогда не остановится?
Вот вам контрпример:
Пусть A-бесконечный алгоритм.
Тогда A1 = IF(true then return 1 else return A) - тоже бесконечный алгоритм, который ,однако, остановится сразу после первого действия (вернёт единицу).

man в сообщении #264722 писал(а):

К тому же, как с Вашими "множествами", так и с "алгоритмами" - как Вы будете отличать какой алгоритм передан на вход, тот же самый или такой же ?

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

[Maslov]

Андрей АK в сообщении #265088 писал(а):

Пусть A-бесконечный алгоритм.

До тех пор, пока мы не определимся с понятиями, мы так и будем говорить каждый о своём. Если не трудно, объясните, пожалуйста, что такое "бесконечный алгоритм". А начать, я думаю, лучше с определения, что такое в Вашем понимании просто "алгоритм".

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

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

[man]

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

До тех пор, пока мы не определимся с понятиями, мы так и будем говорить каждый о своём.

Поддерживаю, пока мы говорим на разных языках.

Андрей АK в сообщении #265088 писал(а):

man в сообщении #264722 писал(а):

А как Вам такая формула m1=M|x(P(x)=$\varnothing$) ?

Ну ... почему бы и нет?

Вы не сказали, как обстоят дела с остальными кванторами, они настолько же "уникальны", что идентичные формулы (с заменой $x$ на $y$) порождают разные, неравные множества ? Формулу я привел потому, что не понял, из чего Вы собираетесь порождать пустое множество ? Если заменить в аксиоме пустого множества $\forall x$ на $\forall y$, по-Вашему, получатся разные, неравные множества ? Как же Вы его собираетесь определять ? Сакральным символом ?

Андрей АK в сообщении #265088 писал(а):

man в сообщении #264722 писал(а):

У Вас множества m2=M|y(P(y)=1) ; m1=M|x(P(x)=1) равны ? Если нет, то как Вы собираетесь отличать какому из множеств принадлежит число $1$ - $\mathbb {N}_1$ или $\mathbb {N}_2$ например ?

А при чем здесь число?
Если мне надо узнать, принадлежит ли элемент множеству, я обращусь к определению и , если множество m2 создано позже m1 то m2 к m1 не принадлежит, все остальные члены у них общие (в том чисте и 1, если она удовлетворяет признаку).

Действительно, при чем здесь числа – у Вас их еще нет, Вам как раз и нужно их определить. Давайте посмотрим на Ваши формулы с этой стороны:
m=M|x(P(x)=q) ; n=M|y(P(y)=q)
$m\in n$ или $n\in m$ ?
Изменив последовательность формул на n=M|x(P(x)=q); m=M|y(P(y)=q); получим совершенно другие множества. Так я понимаю ?

Андрей АK в сообщении #265088 писал(а):

man в сообщении #264722 писал(а):

Андрей АK в сообщении #264108 писал(а):

Вывод: алгоритм , вызывающий самого сабя, записывается бесконечным набором символов.

Если бы так, не было бы проблемы останова. Если считать, что есть бесконечные алгоритмы, то проблема останова для них не актуальна - они не остановятся на любом входе.

С чего вы взяли, что бесконечный алгоритм никогда не остановится?
Вот вам контрпример:
Пусть A-бесконечный алгоритм.
Тогда A1 = IF(true then return 1 else return A) - тоже бесконечный алгоритм, который ,однако, остановится сразу после первого действия (вернёт единицу).

Приведите пример конечного алгоритма.

Андрей АK в сообщении #265088 писал(а):

man в сообщении #264722 писал(а):

К тому же, как с Вашими "множествами", так и с "алгоритмами" - как Вы будете отличать какой алгоритм передан на вход, тот же самый или такой же ?

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

Начните с определений, если хотите, чтобы вас понимали.

[Андрей АK]

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

До тех пор, пока мы не определимся с понятиями, мы так и будем говорить каждый о своём. Если не трудно, объясните, пожалуйста, что такое "бесконечный алгоритм". А начать, я думаю, лучше с определения, что такое в Вашем понимании просто "алгоритм".

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

-- Ср ноя 25, 2009 15:26:56 --

man в сообщении #265187 писал(а):

Вы не сказали, как обстоят дела с остальными кванторами, они настолько же "уникальны", что идентичные формулы (с заменой $x$ на $y$) порождают разные, неравные множества ?

Где вы увидали, что при замене x на y порождаются разные множества?
Существенен порядок выполнения квантора порождения, а не то какие там используются символы (x или y или z).
Пустое множество порождается, если ни одно из существующих множеств не удовлетворяет порождающему признаку.
P(x)=1 - означает, что предикат P в применении к множеству (или числу) x , возвращает единицу.
Ваш вариант P(x)=<пустое множество> - я не отверг (по определению предикаты могут возвращать только 1 или 0) потому-что у меня есть по этому поводу идеи, что предикаты возвращают не только 1 и 0 - множество их ответов можно расширить (и это не нечеткая логика).
Но это уже уклонение от темы... не хочу эту мысль сейчас развивать.

man в сообщении #265187 писал(а):

Действительно, при чем здесь числа – у Вас их еще нет, Вам как раз и нужно их определить. Давайте посмотрим на Ваши формулы с этой стороны:
m=M|x(P(x)=q) ; n=M|y(P(y)=q)
$m\in n$ или $n\in m$ ?
Изменив последовательность формул на n=M|x(P(x)=q); m=M|y(P(y)=q); получим совершенно другие множества. Так я понимаю ?

Да так.

man в сообщении #265187 писал(а):

Приведите пример конечного алгоритма.

A(x) = if(x>0 then return 1 else return 0) - конечный алгоритм (т.е. алгоритм конечного размера кода).

[hurtsy]

Андрей АK

Цитата:

Пока произносится утверждение, оно ещё не существует.

Произносится только то, что сформировано уже, как мысль, т.е. уже существует.

Цитата:

Следовательно налицо нарушение принципа причинности

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

[man]

Андрей АK в сообщении #265231 писал(а):

man в сообщении #265187 писал(а):

Вы не сказали, как обстоят дела с остальными кванторами, они настолько же "уникальны", что идентичные формулы (с заменой $x$ на $y$) порождают разные, неравные множества ?

Где вы увидали, что при замене x на y порождаются разные множества?
…

Андрей АK в сообщении #265231 писал(а):

man в сообщении #265187 писал(а):

…
m=M|x(P(x)=q) ; n=M|y(P(y)=q) …
Изменив последовательность формул на n=M|x(P(x)=q); m=M|y(P(y)=q); получим совершенно другие множества. Так я понимаю ?

Да так.

Андрей АK в сообщении #265231 писал(а):

…
Существенен порядок выполнения квантора порождения, а не то какие там используются символы (x или y или z).
Пустое множество порождается, если ни одно из существующих множеств не удовлетворяет порождающему признаку.
…

1)Какие множества существуют, пока не порождено пустое, из чего Вы их порождали ?
2)Алгоритм порождения пустого множества конечный или бесконечный (остановиться он или нет) ?

Андрей АK в сообщении #265231 писал(а):

…
P(x)=1 - означает, что предикат P в применении к множеству (или числу) x , возвращает единицу.
Ваш вариант P(x)=<пустое множество> - я не отверг (по определению предикаты могут возвращать только 1 или 0) потому-что у меня есть по этому поводу идеи, что предикаты возвращают не только 1 и 0 - множество их ответов можно расширить (и это не нечеткая логика).
Но это уже уклонение от темы... не хочу эту мысль сейчас развивать.

Придется…
Пока я не вижу, как Вы собираетесь отличать Ваши множества – признаки, от обычных множеств и как Вы их собираетесь сравнивать между собой и друг с другом.
Вы так и не ответили на несколько вопросов:

man в сообщении #264722 писал(а):

У Вас множества m2=M|y(P(y)=1) ; m1=M|x(P(x)=1) равны ?

man в сообщении #265187 писал(а):

m=M|x(P(x)=q) ; n=M|y(P(y)=q)
$m\in n$ или $n\in m$ ?

И еще один:
Вы задаете (порождаете множества): m=M|x(P(x)=q) ; n=M|y(P(y)=q)
Я такие: n=M|y(P(y)=q); m=M|x(P(x)=q)
Ваше множество $m$ и мое множество $m$ равны ?

Андрей АK в сообщении #265231 писал(а):

man в сообщении #265187 писал(а):

Приведите пример конечного алгоритма.

A(x) = if(x>0 then return 1 else return 0) - конечный алгоритм (т.е. алгоритм конечного размера кода).

Очень ценное уточнение, надеюсь Вы не собираетесь привести алгоритм бесконечного размера кода ? Хотя Вы вроде бы уже пытались такой привести в предыдущих сообщениях, но фактически только запутались в применении понятия бесконечности к алгоритмам. Разницу между конечный и остановится понимаете ?
Определитесь все-таки, что значит алгоритм и что вы понимаете под "бесконечным алгоритмом".

[Андрей АK]

hurtsy в сообщении #265289 писал(а):

Андрей АK

Цитата:

Пока произносится утверждение, оно ещё не существует.

Произносится только то, что сформировано уже, как мысль, т.е. уже существует.

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

[Maslov]

Андрей АK в сообщении #265231 писал(а):

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

Т.е., ирациональное число - это алгоритм? А рациональное - тоже алгоритм? А натуральное?

[Андрей АK]

man в сообщении #265299 писал(а):

1)Какие множества существуют, пока не порождено пустое, из чего Вы их порождали ?

Думаю, самые первые (элементарные) множества могут быть порождены только перечислением.
Т.е. никаких бесконечно-больших чисел не существует... поскольку их невозможно перечислить.
Возможно, правда, зациклить перечисление : N(k) = N(k-1)+1
Такая рекурсия не противоречит принципу причинности.
А вот такая противоречит: N(k) = N(k)

man в сообщении #265299 писал(а):

2)Алгоритм порождения пустого множества конечный или бесконечный (остановиться он или нет) ?

Это уже частные случаи.
Если применяется к конечному множеству - то остановится (проверив каждый элемент), если к бесконечному - то зависит от алгоритма (возможно можно сразу доказать, что ни одно множество/элемент не может удовлетворять порождающему признаку , тогда за конечное время алгоритм возвращает пустое множество.

man в сообщении #265299 писал(а):

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

Можно сравнением членов, а можно сравнением признаков.
Тут вероятно надо разработать теорию иерархии алгоритмов.
Алгоритмы можно разбить на те, которые могут обрабатываться параллельно, и те которые не могут этого делать (только последовательно), поскольку имеют в своём коде иерархические ссылки друг на друга.
Так же и два множества получаются сравнимыми - если их пораждающие алгоритмы разпараллеливаются и несравнимыми в противном случае.
Т.е. если в кванторе порождения множества m1 присутствует ссылка на множество m2 - то эти два множества несравнимы, и их порождающие алгоритмы не распараллеливаются, причем m2 считается множество более верхнего уровня, чем m1 (m2 порождается раньше чем m1).
Если же никакого упоминания в m1 множества m2 нет ... то для того чтоб эти два множества были равны необходимо и достаточно, чтоб у них были одинаковые признаки и одинаковые исходные множества (верхнего уровня на которых действуют кванторы порождения).

man в сообщении #265299 писал(а):

Вы задаете (порождаете множества): m=M|x(P(x)=q) ; n=M|y(P(y)=q)
Я такие: n=M|y(P(y)=q); m=M|x(P(x)=q)
Ваше множество $m$ и мое множество $m$ равны ?

Они не равны ... но не потому что там x , а там y, а потому, что у вас n порождается после m, а у меня наоборот ... однако, если алгоритмы друг на друга не ссылаются и возможно параллельное создание ... то эти два множества равны (поскольку имеют один и тот-же порождающий признак и область значений).
PS
Ах да - они и не могут друг на друга сослаться - иначе это уже были бы разные признаки ... т.е. это абсолютно равные множества (n=m=m=n).

man в сообщении #265299 писал(а):

Определитесь все-таки, что значит алгоритм и что вы понимаете под "бесконечным алгоритмом".

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

-- Ср ноя 25, 2009 22:00:40 --

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

Андрей АK в сообщении #265231 писал(а):

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

Т.е., ирациональное число - это алгоритм? А рациональное - тоже алгоритм? А натуральное?

Почему бы и нет?
Любое число - алгоритм (если только не ссылка на алгоритм).