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

[vesoliy]

Фраза "Это утверждение - ложное"

Встретил в интернете такое рассуждение:

Предположим фраза "Это утверждение - ложное" - логическое утверждение. Тогда:

1. Оно либо истинно либо ложно.
2. Если оно истинно то оно ложно. Если оно ложно то оно истинно. Таким образом оно и истинно и ложно (либо ни то ни другое).

Получается противоречие. Значит фраза "Это утверждение - ложное" не является логическим утверждением.

Теперь мой вопрос: рассуждение 2. основанно на том предположении что фраза "Это утверждение - ложное" - логическое утверждение. Если в результате получается что это не так, не "разрушает" ли это логичность самого доказательства?

[meduza]

http://ru.wikipedia.org/wiki/Парадокс_лжеца + тамошний список литературы

[Андрей АK]

Я вообще считаю, что утверждение не может быть направлено на само себя.
Так-же как и на утверждение ... которое ещё не произнесено.

"Я лгу", точно так-же неправомерно, как и "Через минуту я солгу".

Пока произносится утверждение, оно ещё не существует.
Следовательно налицо нарушение принципа причинности (т.е. дело вовсе не в противоречивости аппарата логики).

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

Существует ли какие ни будь другие варианты доказать "теорему о неполноте" не используя "парадокс лжеца"?

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

[Maslov]

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

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

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

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

Существует ли какие ни будь другие варианты доказать "теорему о неполноте" не используя "парадокс лжеца"?

Какое отношение теорема о неполноте имеет к парадоксу лжеца? При доказательстве теоремы о неполноте строится формула, содержащая утверждение о своей собственной невыводимости (а вовсе не о ложности), и никакого парадокса там и близко нет.

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

Ведь в "парадоксе лжеца" допущено нарушение глобального методического/надматематического принципа

А Вы можете дать строгую формулировку этого "глобального методическо/надматематического принципа"?

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

а следовательно и доказательство любых теорем с его применением некорректно.

И всё-таки, какие теоремы доказываются с помощью парадокса лжеца?

[Ираклий]

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

Существует ли какие ни будь другие варианты доказать "теорему о неполноте" не используя "парадокс лжеца"?

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

Что касается альтернативных доказательств теоремы о неполноте, то рекомендую:
http://www.mathnet.ru/php/presentation.phtml?eventID=7&option_lang=rus
Три лекции под названием "Теорема Гёделя о неполноте и четыре дороги, ведущие к ней". (Инициалы лектора - ВАУ - вполне соответствуют его мастерству чтения лекций!)

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

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

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

[Андрей АK]

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

Какое отношение теорема о неполноте имеет к парадоксу лжеца? При доказательстве теоремы о неполноте строится формула, содержащая утверждение о своей собственной невыводимости (а вовсе не о ложности), и никакого парадокса там и близко нет.

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

И так во всех "парадоксах".
Поэтому я и спрашиваю: без нарушения "принципа причинности" нельзя обойтись?

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

А Вы можете дать строгую формулировку этого "глобального методическо/надматематического принципа"?

Ну раз это "надматематический принцип" то и формулировка не обязательно должна быть математической.
Например такой: "Ни одно следствие не может быть собственной причиной".

Если где-то это нарушается, то там и возникает парадокс.

[Maslov]

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

В том числе и прочие парадоксы, как то: ... "Проблема остановки алгоритма"

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

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

Например признак,включает ли множество всех множеств само себя, присваивается множеству ДО ТОГО как само это множество формируется - но ведь пока мы не составили полный список членов множества , мы не можем определить - включает ли это множество само себя.

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

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

Ну раз это "надматематический принцип" то и формулировка не обязательно должна быть математической.
Например такой: "Ни одно следствие не может быть собственной причиной".

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

[Андрей АK]

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

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

В "проблеме остановки" предположение о подстановки функции в себя саму - это и есть попытка использовать "парадокс Лжеца".
Но не так как в "Лжеце" а вывернув его наизнанку.
Т.е. в "Лжеце" мы прямо используем определение высказыванием собственной истинности.
А вот в "проблеме остановки" происходит попытка выдать доказательство за парадокс - КАК БЫ подставить функцию в саму себя.
Перейду к конкретике:
Пусть Q(X) - функция определяющая останавливается ли X или зацикливается.
Тогда при попытки этой функции определить это свойство для самой себя возникает противоречие.
Но тут есть одно но!
Почему-то в доказательсте "забывают" про параметры функции.
При подстановки функции самой в себя надо учитывать и какая функция была передана в Q в качестве параметра.
Т.е. получаем не Q(Q) ... а Q(Q(X)) и дальше Q(Q(Q(X))).
Это все разные функции - ведь остановится алгоритм или нет зависит не только от самой функции, но и от переданных в неё параметров!
Значит никакого противоречия (парадокса) нет и быть не может!
Просто невозможно подставить функцию саму в себя - при каждой новой подстановке это будет уже другая функция.
Единственный вопрос: а может ли быть бесконечная череда подстановок: Q(Q(Q(Q ... и так до бесконечности - это единственный вариант когда Q(Q(...))=Q(...)
Но вот такие действия и должны запрещать наши "надматематические принципы".
Возможно для этого случая (Q(Q(Q(Q ) существует свой ,отдельный глобальный принцип (если только его невозможно вывести из принципа причинности) запрещающий бесконечные зацикленные подстановки.

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

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

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

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

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

Ну раз это "надматематический принцип" то и формулировка не обязательно должна быть математической.
Например такой: "Ни одно следствие не может быть собственной причиной".

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

Ну ... "я не тактик, я - стратег ..." (с)
(Тем хуже для математики)

[Maslov]

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

Перейду к конкретике:
Пусть Q(X) - функция определяющая останавливается ли X или зацикливается.
Тогда при попытки этой функции определить это свойство для самой себя возникает противоречие.
Но тут есть одно но!
Почему-то в доказательсте "забывают" про параметры функции.

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

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

Для бесконечных множеств мы просто составляем список элементов с бесконечно большой скоростью.

Поподробнее этот процесс опишите, пожалуйста (например, для $\mathbb{R}$). Последовательно список составляете, элемент за элементом?

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

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

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

[Андрей АK]

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

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

Перейду к конкретике:
Пусть Q(X) - функция определяющая останавливается ли X или зацикливается.
Тогда при попытки этой функции определить это свойство для самой себя возникает противоречие.
Но тут есть одно но!
Почему-то в доказательсте "забывают" про параметры функции.

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

Есть много вариантов "проблемы остановки" (как и "теорем о неполноте") ... но проанализировав каждую, во всех можно найти завуалированное применение бесконечных вложений.
Для примера могу разобрать тот вариант что в Википедии:
[url]http://ru.wikipedia.org/wiki/Проблема_остановки[/url]

Цитата:

Все конечные последовательности символов из некоторого алфавита можно пронумеровать. Выпишем сначала все символы из алфавита, потом все последовательности из двух символов, потом - из трех и т.д. Любая конечная последовательность когда-нибудь встретится в этом списке. Позиция, на которой она встретится - это и будет ее номер. Рассмотрим алгоритмы, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Алгоритм может рано или поздно остановиться и выдать результат, или же не остановиться никогда (например, из-за бесконечного цикла или бесконечной рекурсии). Каждый алгоритм можно записать в виде конечной последовательности символов на некотором языке программирования, поэтому у каждого алгоритма есть номер. Все пары натуральных чисел тоже можно пронумеровать. Представим, что все пары выписаны в виде таблицы: на первой строке находятся все пары, первый элемент которых равен 1, на второй строке находятся все пары, первый элемент которых равен 2 и т.д. Мы можем обойти эту таблицу по диагоналям, выписывая все пары в ряд: (1,1),(1,2),(2,1),(1,3),(2,2),(3,1) и т.д. Позиция, на которой встретится некоторая пара - это и будет ее номер. И наоборот, каждому номеру соответствует какая-то пара чисел. Назовем Анализатором гипотетический алгоритм, который получает на вход номер пары натуральных чисел, интерпретируемых как номер алгоритма N и его входные данные X, и:
останавливается и возвращает 1, если алгоритм с номером N останавливается, получив на вход X
останавливается и возвращает 2, если алгоритм с номером N не останавливается, получив на вход X

А теперь найдём подвох:
Когда анализатору передаётся (в качестве параметра) номер другого алгоритма+параметры (m,n), то по одному номеру (номерам) наш анализатор ни за что не определит, остановится алгоритм или нет.
Сам номер ему ни о чем не скажет (поскольку назначался произвольно и независимо от алгоритма/параметров, который он нумерует)
Для работы анализатору надо получить конкретное описание алгоритма.
Т.е. он должен перейти по ссылке и извлечь это описание (где они там хранятся) и ... точно также получить описание параметров.
Предположим, что в качестве исследуемой функции (m) оказался сам же анализатор ... которому в качестве параметров (n) было некое число... также равное m (n=m).
Ну допустим, что описание алгоритма одинаково для всех пар чисел начинающихся на m , поэтому описание алгоритма можно получить без длительных поисков ... но вот про параметры этого сказать нельзя.
Поскольку число n - это всего лишь число, то мы должны отправится в ячейку под номером n и узнать - что там скрывается.
Если окажется что в этой ячейке находится очередная ссылка на другую ячейку (m1,n1) то следует пройти по ней и уже там попытатся узнать какие параметры все-же переданы нашему анализатору, и так до тех пор пока не упремся в тупиковую ветвь.

Для случая же n=m мы имеем ... зациклившуюся базу номеров с бесконечным переходом по ссылкам.

Т.е. тот самый случай бесконечного вложения: Q(Q(Q(Q(...
В нашем случае: (m,(m,(m,(m, ... здесь бесконечное число вложений...)))

Т.е. все тот-же вариант бесконечного зацикливания.

Естественно мы приходим к выводу о невозможности выполнения данной процедуры ... но означает ли это доказательство невозможности существования анализатора?
Нет!
Здесь дефект сидит в выбранной нумерации, а не алгоритме анализатора.
Т.е. рассмотрен только частный случай невозможности написания алгоритма, который бы корректно работал с некорректной базой данных (графом с циклическими ссылками).

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

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

Для бесконечных множеств мы просто составляем список элементов с бесконечно большой скоростью.

Поподробнее этот процесс опишите, пожалуйста (например, для $\mathbb{R}$). Последовательно список составляете, элемент за элементом?

Нет, просто беру и пишу некое уравнение с признаком принадлежности к множеству ... с учетом того, что в этом уравнении не должно упоминаться само множество для которого составляется уравнение.
(Как в логическом выражении не должно присутствовать свободной переменной под знаком квантора , связывающего переменную с тем-же названием).
Назовем это уравнение: "уравнение порождения множества".
Т.е. составление множества - это такой-же квантор что и кванторы всеобщности и существования (не знаю как они на math пишутся поэтому - словами) и внутри этой процедуры не должно быть значка самого этого порождаемого множества.
И кроме того считается, что под этим "квантором порождения" (в списке проверяемых множеств), самого "порождаемого множества" не существует и ,следовательно, к нему не требуется применять нашего "порождающего признака".

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

К стати, если я поставлю перед ним тот-же самый "квантор порождения" ...

m2=M|y(P(y)=1) ; m1=M|x(P(x)=1)

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

Не такая уж и "особая" математика - небольшое расширение мат. логики.

[Maslov]

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

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

С чего Вы взяли, что за описанием параметров надо куда-то отправляться?
$n$ - это не никакой не номер ячейки, это все параметры алгоритма, упакованные в одно число. Мы никоим образом не ограничены в размере этого числа, поэтому можем засунуть в него всё, что угодно, например, всё содержимое винчестера или всё содержимое всех винчестеров в обитаемой части Вселенной.

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

Не такая уж и "особая" математика - небольшое расширение мат. логики.

Это абсолютно особая математика. Вы готовы написать аксиомы Вашей теории множеств и формализовать логику (в частности, задать термы, связки, предикаты, кванторы, правила вывода и т.п.)?
Потом, правда, придется ещё построить арифметику и ещё очень много чего. А главное, не очень понятно, из-за чего весь сыр-бор. Из-за того, что Вам не нравятся доказательства от противного?

[Ираклий]

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

Сам номер ему ни о чем не скажет (поскольку назначался произвольно и независимо от алгоритма/параметров, который он нумерует)
Для работы анализатору надо получить конкретное описание алгоритма.
Т.е. он должен перейти по ссылке и извлечь это описание (где они там хранятся) и ... точно также получить описание параметров.

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

2) Дальнейшие Ваши рассуждения (если я правильно Вас понял) предполагают, что найдя описание алгоритма и востановив его входные данные, наш анализатор должен запустить этот алгоритм на этих входных данных. Если он (анализатор) так сделает, то действительно может возникнуть та бесконечная цепочка самовызовов, о которой Вы говорите. Но наш анализатор вовсе не обязан запускать этот алгоритм! Он, например, может пройтись по тексту (описанию) этого алгоритма в поисках вхождения в него строки "while(1);" (такая строка в Си означает бесконечный цикл) и если найдет такую строку, то может сразу выдать ответ, что алгоритм зациклится. Если же не найдет, то предпримет еще какие-то действия для выяснения того, остановится алгоритм или нет.

[Андрей АK]

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

С чего Вы взяли, что за описанием параметров надо куда-то отправляться?
$n$ - это не никакой не номер ячейки, это все параметры алгоритма, упакованные в одно число. Мы никоим образом не ограничены в размере этого числа, поэтому можем засунуть в него всё, что угодно, например, всё содержимое винчестера или всё содержимое всех винчестеров в обитаемой части Вселенной.

Если у каждого номера (рядом с ней) находится её полное описание, то если мы подсчитаем объем этого описания, то получим что нам потребуется зарезервировать под него бесконечно большое количество места.
Действительно, вызов анализатора с параметрами A(m,m) означает вызов: A(A(m,m),A(m,m)) - но и подобную конструкцию мы не можем передать нашему анализатору, поскольку ,по прежнему, присутствует число m - которое "символизирует" собой все тот же самый вызов - анлиз аназизатором ячейки номер m и само по себе не должно сообщаться анализатору.
Т.е. "развернутая" запись подобного алгоритма представляет собой бесконечно вложенный фрактал:
A(A(A(A(..,..),A(..,..)),A(A(..,..),A(..,..))),A(A(A(..,..),A(..,..)),A(A(..,..),A(..,..))))
Не знаю, договаривались ли мы включать в перечисление ,кроме алгоритмов конечного размера, ещё и бесконечно большие алгоритмы?
Думаю их участие не подразумевается.
А раз бесконечно большие алгоритмы не учавствуют (да их и не пересчитаешь - их несчетное множество) то и числа для m-> A(m,m) в нашем перечислении НЕ СУЩЕСТВУЕТ!
Т.е. в нашем списке такого алгоритма нет - не предусмотрено.

-- Пт ноя 20, 2009 23:17:01 --

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

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

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

[venco]

Безотносительно к остальному придерусь только к возможности анализа без испольнения.

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

Он, например, может пройтись по тексту (описанию) этого алгоритма в поисках вхождения в него строки "while(1);" (такая строка в Си означает бесконечный цикл) и если найдет такую строку, то может сразу выдать ответ, что алгоритм зациклится.

И ошибётся:

Используется синтаксис C

int main()
{
  if ( 1 == 2 ) {
    while (1);
  }
  return 0;
}
 

Гораздо интереснее другой пример (можете заменить другой, ещё не решённой проблемой):

Используется синтаксис C

int main()
{
  for ( Number c = 1; ; ++c ) {
    for ( Number a = 1; a < c; ++a ) {
      for ( Number b = 1; b < c; ++b ) {
        if ( a*a*a+b*b*b == c*c*c ) {
          return 0;
        }
      }
    }
  }
}
 

[Ираклий]

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

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

Похоже, Вы не очень понимаете, что такое кодирование.
1) Возьмите цвет вашего телефона и напишите его на бумаге (например, "синий").
2) Замените каждую букву на ее номер в алфавите, получится конечная последовательность чисел (19,10,15,10,11).
3) Выпишите по порядку несколько первых простых чисел - столько, сколько чисел в предыдущей последовательности (2,3,5,7,11).
4) Возведите первое простое число в степень, показатель которой равен первому числу в последовательности из пункта (2), второе число - в степень, равную второму числу и т. д. со всеми выписанными простыми числами. И всё это перемножьте. ($2^{19}\cdot3^{10}\cdot5^{15}\cdot7^{10}\cdot11^{11}$).

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

-- Сб ноя 21, 2009 04:06:35 --

venco в сообщении #264004 писал(а):

Безотносительно к остальному придерусь только к возможности анализа без испольнения.

Что алгоритм ошибется это понятно, разумеется. Строка "while(1);" может быть в недостежимом участке кода, как в Вашем примере. Можно считать, что это лишний раз подтверждает несуществование рассматриваемого анализатора