Логическое противоречие

[PAV]

Я уже понял, в чем проблема. Смотрите. Начинаем с начала.

(1) - Атакуем завтра в 9 утра, как понял?
После этого сообщения (1) не будет еще атаковать, поскольку он не уверен, что (2) получил это сообщение.
(2) понимает, что (1) ждет подтверждения и не начнет атаку, покуда его не получит. Поэтому он посылает
(2) - Вас понял отлично, какая у Вас погода?
Но он понимает, что если это сообщение не дойдет, то (1) в атаку не пойдет. Поэтому ему нужно подтверждение, что сообщение получено. Если он не получит этого подтверждения, то атаку начинать не может.
(1) все это понимает и посылает подтверждение
(1) - Погода нормальная, как сам себя чувствуешь?
Но если это подтверждение не дойдет, то (2) в атаку не пойдет, как было написано выше. Поэтому он должен подтвердить... Ну и так далее.

[Antananarivu]

PAV
Полностью согласен. Видимо, чисто логически никакого противоречия здесь нет. Но все-таки последнее меня смущает:
в реальной ситуации после такого цикла сообщений

(1) - Атакуем завтра в 9 утра, как понял?
(2) - Вас понял отлично, какая у Вас погода?
(1) - Погода нормальная, как сам себя чувствуешь?
(2) - Чувствую себя нормально и т.д.

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

[Someone]

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

[Antananarivu]

Согласен, возможно, это и казуистика! Но представьте себе выражение лица первого генерала, если вдруг другой генерал не станет атаковать и более того, будет иметь на это "логически непротиворечивое оправдание!"

[Pointer]

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

2 Antananarivu.

Цитата:

оба знают, что каждое сообщение доходит с вероятностью 50%, а так как оба являются пессимистами по умолчанию предполагают, что последнее сообщение не дошло.

Противоречие содержится здесь - в форме двух взаимоисключающих условий задачи:
1) оба полагают вероятность успешной передачи своего последнего сообщения равной 0.5;
2) оба полагают вероятность успешной передачи своего последнего сообщения равной 0.
Можно разрешить это противоречие, представив собеседников полными дебилами, неспособными осознать противоречивость своих представлений. Но в этом случае любое наше предположение об их предположениях о содержании чужого экрана не будет противоречить логике, ибо что с них взять. :)

Цитата:

и думает: мое последнее сообщение не дошло, значит собеседник (2) видит экране пустым.

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

Ошибка содержится здесь - в форме ложного вывода об абсурдности предположения "пустой экран собеседника".
При вероятности успешной передачи сообщения равной $1/2$, предположение того, что не прошло ни одно из твоих сообщений, вовсе не является абсурдным. Вероятность его истинности равна $1/2^N$, где $N$ - количество отправленных сообщений.

Цитата:

представим себе этих самых генералов (см. выше). Сколько сообщений необходимо им друг другу переслать, для того чтобы оба были на 100% уверены, что атака состоится завтра в назначенное время. И если рассуждать математически получается, что N=бесконечности. Потому что если предположить, что необходимо N=n сообщений, то n-ное сообщение уже и не нужно, потому что, дойдет оно или не дойдет - уже не важно. Значит его можно было и не посылать.. значит необходимо всего n-1 сообщение и.т.д. Что-то здесь где-то не так, а вот что, я не понимаю...

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

Возвращаясь к нашим генералам.
Итак, требуется передать время атаки.
Поскольку рассматривается система связи с помехами, то абсолютно надёжного способа договориться здесь нет. Но и ни одно сообщение (подтверждение) не будет "ненужно", поскольку каждое увеличивает вероятность передачи данных. Больше сообщений - больше избыточность - больше надёжность.
С этой точки зрения, для передачи сообщения об атаке диалог вовсе не нужен. 1-й генерал просто повторяет своё сообщение столько раз, сколько успеет. И начинает атаку в том случае, если успел передать более одного раза (вероятность успешной передачи $>1/2$). В представленных условиях, никакой другой протокол связи не будет более эффективным.

Цитата:

в реальной ситуации после такого цикла сообщений

(1) - Атакуем завтра в 9 утра, как понял?
(2) - Вас понял отлично, какая у Вас погода?
(1) - Погода нормальная, как сам себя чувствуешь?
(2) - Чувствую себя нормально и т.д.

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

Появились какие-нибудь версии? :)

Не забывайте, пожалуйста, ставить $ вокруг формул. // нг

[qTorus]

Pointer писал(а):

1-й генерал просто повторяет своё сообщение столько раз, сколько успеет

Полностью согласен. Это и есть самая выгодная стратегия передачи сообщений. Единственный её недостаток заключается в неуверенности первого в том, что хотя бы одно сообщение дошло.

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

[qTorus]

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