Zagadka. Kto się skusi?

[R3615]

Super  
Zatem czas na prawdziwy problem:

Zakładamy, że Los odpowiada zgodnie z pewną regułą, którą można zapisać w postaci prostego algorytmu (tzn. np. okresowy, a nie typu binarnego rozwinięcia liczby Pi). W ten sposób otrzymujemy jakiś ciąg zer i jedynek, gdzie zero traktujemy jako kłamstwo, zaś jedynkę jako prawdę.

Problem: Jaka jest najmniejsza liczba pytań, które trzeba zadać, aby rozpoznać trzy boginie.  

Upraszczam, gdyż w ogólnej postaci problem nadaje się co najmniej na doktorat z algorytmicznej złożoności obliczeniowej.  

[Neratin]

Super  
Zatem czas na prawdziwy problem:

Zakładamy, że Los odpowiada zgodnie z pewną regułą, którą można zapisać w postaci prostego algorytmu (tzn. np. okresowy, a nie typu binarnego rozwinięcia liczby Pi). W ten sposób otrzymujemy jakiś ciąg zer i jedynek, gdzie zero traktujemy jako kłamstwo, zaś jedynkę jako prawdę.

Problem: Jaka jest najmniejsza liczba pytań, które trzeba zadać, aby rozpoznać trzy boginie.  

Upraszczam, gdyż w ogólnej postaci problem nadaje się co najmniej na doktorat z algorytmicznej złożoności obliczeniowej.  

Z tym doktoratem to chyba 'trochę' przesadziłeś. Skoro nie znamy algorytmu, według którego odpowiada Los, to i tak trzeba założyć, że odpowiada losowo, jak w oryginalnej (trudniejszej) wersji zagadki. A tę wersję zagadki rozwiązuje się w trzech pytaniach...

[R3615]

Hmmm... Obawiam się, że nie przesadziłem. Czytałem jeszcze raz i wszystko się zgadza. Popatrzmy na to wszystko tak:

Zagadnienie pierwsze, jak można zakładać, rozwiązał już Inquisitor_Matematicus:

Wiem jak zadając najwyżej 4 pytania zlokalizowac wszystkie. O ile los mówi naprzemian

W sposób naturalny rodzi się więc pytanie, czy istnieje rozwiązanie ogólniejszych problemów i jaka jest minimalna liczba pytań, potrzebna do określenia kim są boginie. Zatem zadanie drugie może dotyczyć ciągu odpowiedzi wyroczni np. (ttn)ttnttn... , (ttnn)ttnnttnn...., albo czegoś w stylu (tnttntnn)tnttntnntn.... Ciekaw jestem, po prostu, jak ta  liczba zależy od długości ciągu generującego (okresu podstawowego), jak zależy od sposobu generowania ciągów t i n (gramatyki w bardziej złożonych przypadkach), a w wersji hard - jaka jest złożonośc problemu i jaki ma związek z innymi problemami (redukcje).  

Do obeznanych z tematem:    Sorry, że brzmi strasznie ale to zapewne wpływ godzin wysiedzianych przy tłuczeniu Botzmannem komiwojażera i upychania genetyką klocków do pudełka.  
Wybaczcie mi więc pierwsze skojarzenie z niedeterministyczną maszyną Turinga.  

[Neratin]

Hmmm... Obawiam się, że nie przesadziłem. Czytałem jeszcze raz i wszystko się zgadza. Popatrzmy na to wszystko tak:

Zagadnienie pierwsze, jak można zakładać, rozwiązał już Inquisitor_Matematicus:

Wiem jak zadając najwyżej 4 pytania zlokalizowac wszystkie. O ile los mówi naprzemian

Obawiam się, że nie. Po pierwsze, _prawidłowe_ rozwiązanie nie zależy od takich założeń, po drugie, zawiera 3 pytania. Inquisitor Matematicus tego rozwiązania nie znalazł.

W sposób naturalny rodzi się więc pytanie, czy istnieje rozwiązanie ogólniejszych problemów i jaka jest minimalna liczba pytań, potrzebna do określenia kim są boginie.

Tak, istnieje. Ogólniejszym problemem jest to zagadka sformułowana powyżej, która nie zawiera ograniczenia naprzemienności odpowiedzi Losu. I ten problem ma rozwiązanie.

Zatem zadanie drugie może dotyczyć ciągu odpowiedzi wyroczni np. (ttn)ttnttn... , (ttnn)ttnnttnn...., albo czegoś w stylu (tnttntnn)tnttntnntn....

No ale tłumaczyłem przecież, że niezależnie od tego, jak wygląda ten ciąg wyroczni, i tak da się zmieścić w trzech pytaniach - a więc mielibyśmy ciągi maksymalnie trzyelementowe (aczkolwiek w prawidłowym rozwiązaniu nie pytamy się tej samej bogini trzykrotnie).

Ciekaw jestem, po prostu, jak ta  liczba zależy od długości ciągu generującego (okresu podstawowego),

Od długości akurat nie zależy. W najgorszym wypadku znajdziesz rozwiązanie po 3 pytaniach, zejście poniżej tej wartości wymagałoby już znajomości konkretnego schematu odpowiedzi Losu.

jak zależy od sposobu generowania ciągów t i n (gramatyki w bardziej złożonych przypadkach), a w wersji hard - jaka jest złożonośc problemu i jaki ma związek z innymi problemami (redukcje).  

Złożoność problemu - O(c). Nie znam żadnych interesujących problemów z tej klasy.

Do obeznanych z tematem:    Sorry, że brzmi strasznie ale to zapewne wpływ godzin wysiedzianych przy tłuczeniu Botzmannem komiwojażera i upychania genetyką klocków do pudełka.  
Wybaczcie mi więc pierwsze skojarzenie z niedeterministyczną maszyną Turinga.  

?

Nie rozumiem, co ma do tego NTM.

[Inquisitor_Matematicus]

Po nie przespanej nocy sadze że jednak 3 pytania sa mozliwe. Pod warunkiem że Prawda i Fałsz są przyszłowidzące, prawda mam mozliwość "zwracania wartości 0 lub 1" tak samo faułsz.

wyobrazmy sobie trójkąt:

x -> y -> z -> x

Zadajemy pytanie x dotyczace y: "Y odpowie na moje pytanie 0 czy 1?"
Załózmy że z jest losem i odpowie 1 to y jeżeli jest fauszem odpowie 0 jeżeli prawdą odpowie 1 i x jezeli jest faułszem odpowie 0 i x jeżeli jest prawdą to odpowie 0. Los może odpowiedzięc jeszcze nie więc sytuacja się lekko zmieni.

Z tego jeteżmy wstanie rozróznić kto jest kto. Co otym myslicie?

[zaciekawiony]

Ja zakładałem że los jest nieprzewidywalna nawet dla siebie samej, tak jak dla prawdy i kłamstwa,ale nic mi nie wyszło z tego.
Jeśli by w twoim rozwiązaniu 0 to był nie a 1 tak, to każda z boginek odparła by Da, bo tak i nie to w ichnim jezyku Da
Swoją drogą jak niby boginki rozumieją nasze pytania skoro mówią własnym językiem?
Weż to rozwiązanie nieco rozwiń, i jeszcze podaj jakie pytania miał byś zadać Y

[Inquisitor_Matematicus]

Rozwiązanie jest niestety błędne. Daje mozliwość zakażdym razem zorientowania się gdzie jest "Prawda".

Inaczej: pytanie, czy możemy zadać pytanie na które nieda się uzyskac odpowiedzi prada czy faułsz: da czy ja.

Zadajemy pierwszej bogini pytanie: Czy to zdanie jest prawdziwe czy fauszywe? Dajemy zdanie które niemozna okreslić czy jest prawdziwe czy fauszywe.

Trafiamy na boginię: los - uzyskamy odpowiedź bo los zawsze odpowiada da lub ja. Nastempnej bogini zadajemy pytanie: Czy Warszawa jest stolica Polski? W zaleznosci od odpowiedzi to jest prawda lub faułsz.

Trafiamy na boginie: prawdę lub fausz. nie otrzymujemy odpowiedzi zadajemy pytanie czy:Czy Warszawa jest stolica Polski? . Dzieki temu rozrużnimy boginię prawde lub fałusz.

Zadajemy pytanie nastepnej bogini: Czy to zdanie jest prawdziwe czy fauszywe? Dajemy zdanie które niemozna okreslić czy jest prawdziwe czy fauszywe. Otrzymujemy odpowiedż jest to los  nie otrzymujemy to musi być to prawda albo fałsz ale już wiemy że jedno znich zostało odkryte i wykluczamy.

I co  o tym sądzicie?


 Uprzedzam ma 38 stopni gorączki więc moglem coś przeoczyć.

[Neratin]

Rozwiązanie jest niestety błędne. Daje mozliwość zakażdym razem zorientowania się gdzie jest "Prawda".

Inaczej: pytanie, czy możemy zadać pytanie na które nieda się uzyskac odpowiedzi prada czy faułsz: da czy ja.

Nie, nie możemy. Nie możemy np. zadać pytania 'czy jutro będzie padać deszcz'.

Trafiamy na boginię: los - uzyskamy odpowiedź bo los zawsze odpowiada da lub ja.

Każda bogini zawsze odpowiada da lub ja. Tylko że Los albo kłamie, albo mówi prawdę. Nie ma więc pytań, na które potrafi odpowiedzieć tylko Los.

[zaciekawiony]

O ile dobrze pamiętam Ja znaczy nie wiadomo co, a nie Fausz.

[Inquisitor_Matematicus]

Też mi się tak wydawało no trudno.

[R3615]

Dobrze. Ustalmy fakty.

1. Podstawą do rozwiązania zagadki jest prawo wyłączonego środka.
2. Zagadka została sformułowana w ten sposób po to, aby uzmysłowić jakie problemy mogą nas czekać jeśli zakwestionujemy powyższą zasadę.
3. Buduje się pytania w formie równoważności (ang. iff = wtedy i tylko wtedy)
4. Poprawne rozwiązanie nie wymaga wiedzy o tym, co znaczy Da oraz Ja (wprowadzone poprawka do oryginalnego sformułowania).
5. Pierwsze pytanie ma odkryć Prawdę lub Kłamstwo; drugie (zadane P lub K) ma odkryć Los; trzecie odróżnić P od K.

A teraz uwagi:

1. W mojej propozycji rozwinięcia problemu jest okres warunkowy: jeżeli X stwierdził Y, to możliwe jest Z.
2. Uwaga o np. logikach modalnych ma taki sens: nie obowiązuje prawo wyłączonego środka, jak więc rozumowania w tych logikach radzą sobie z takim problemem. Odpowiedź negatywna stawia w złym świetle intuicjonizm, nieprawdaż? Jakże więc ta kreatura jeszcze żyje?  
3. Równoważność jest złożeniem dwóch implikacji: a=b oznacza a->b i b->a. Gdzieś tu znajdziemy zbłąkany problem implikacji ścisłej i implikacji materialnej. W oryginalnym rozwiązaniu dotyczy to połączenia dwóch różnych przedmiotów: np. natury słowa Da i wiedzy z geografii.

Na koniec inne "problemy":

1. Załóżmy, że mamy zdanie P(x)=>~P(y), x jest różne od y, P(x) oznacza predykat "x jest prawdziwe", stąd ~P(y) oznacza "y jest fałszywe". W naszym świecie mamy zdania, które stoją z prawej strony jakiejś implikacji i z lewej. Jak zatem można rozumieć następujące zdanie zbudowane na powyższym schemacie:
  (prawa strona tej implikacji jest prawdziwa) => (lewa strona tej implikacji jest fałszywa)
2. Czy można powiedzieć, że własność, która zachodzi dla każdego n naturalnego, przysługuje całemu zbiorowi liczb naturalnych? Jest to częsty błąd w formułowaniu zasady indukcji matematycznej. Problem jest taki:
Jak wiadomo każdy skończony podzbiór zbioru liczb naturalnych można  ponumerować od końca, np. {1,2,3,4} można ustawić w kolejności (4,3,2,1). P(1) zachodzi w sposób oczywisty, zakładamy P(n) dla pewnego n>1, widać od razu, że nasze uporządkowanie dla P(n+1) to (n+1, P(n)).
Czy to oznacza, że zbiór wszystkich liczb naturalnych można uporządkować ustawiając liczby od końca? Raczej nie.  
3. Zauważyłem, że mało kto zwraca uwagę na takie "banalne szczegóły" jak zdanie: pewnik wyboru jest równoważny zdaniu X na gruncie teorii ZFC. Na tym gruncie tak, ale na innym nie koniecznie.

To tyle na dobry początek.  

[Neratin]

Możesz powiedzieć, skąd wziąłeś fakty, które ustaliliśmy (szczególnie tezy 1, 2, 3 i 5)? I co ma reszta postu (rzucane ni z gruszki ni z pietruszki mądre sformułowania o wyżarzaniu, maszynach Turinga, ZFC, częstych błędach w formułowaniu indukcji matematycznej i banalnych szczegółach na które mało kto zwraca uwagę) do rzeczy?

[R3615]

The Hardest Logic Puzzle Ever
By George Boolos

GEORGE BOOLOS IS Professor of Philosophy at MIT and one of the founders of the field of “Provability Logic.” He is the author of The Logic of
Provability (Cambridge, 1993) and, with Richard Jeffrey, Computability and Logic (Cambridge, 1974).

The puzzle: Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions
in their own language, in which the words for “yes” and “no” are “da” and “ja,” in some order. You do not know which word means which.

Autor : Raymond Smullyan

The extra twist of not knowing which are the gods’ words for “yes” and “no” is due to the computer scientist John McCarthy.

Podobna dyskusja: http://www.racjonalista.pl/forum.php/s,13951
Podobna dyskusja: http://www.zagadki.mamy.org/zagadki/
Podobna dyskusja (bardziej naukowym językiem): http://www.physicsforums.com/showthread.php?t=81066
Obrazkowe rozwiązanie: http://www.muzg.uz.zgora.pl/pliki/muzgnzs.pdf
http://ww.umk.pl/~jacekm/rozdkog.pdf - Logika kognitywna i reguły domyślania się (tamże bibliografia i dalsze cele poszukiwań).
http://en.wikipedia.org/wiki/Raymond_Smullyan - o autorze i innych zagadkach.
http://www.uweb.ucsb.edu/~rabern/SSHardPuzzle.pdf
http://www.hcs.harvard.edu/~hrp/issues/1996/Boolos.pdf - stad powyższe cytaty.
http://nebula.deanza.fhda.edu/math/karl/apdffiles/WheresFido.pdf - inna zagadka Smullyana.
http://www.illc.uva.nl/HPI/Draft_Information_in_Computer_Science.pdf - owa problematyczna maszyna Turing, również wzmianka o Smullyanie.
http://www.humboldt.edu/~essays/marrev.html - tu można znaleźć dlaczego George Boolos i dlaczego logika modalna.

Powodzenia.  

[Neratin]

LOL, spoko. A już się przestraszyłem, że wyciągnąłeś te wnioski na podstawie rozwiązania Inquisitora Matematicusa, które miałeś za poprawne...

Ale nie odpowiedziałeś na moje pytanie... co ma zagadka wspólnego z symulowanym wyżarzaniem, maszyną Turinga (i nie, prawidłową odpowiedzią nie jest: 'wzmianka o autorze zagadki znajduje się w eseju, w którym pojawia się także termin maszyna Turinga'), ZFC, błędami w formułowaniu indukcji matematycznej itd?

[R3615]

Żeby nie było, że zabiłem zagadkę, podaję link do miliona zagadek równie ciekawych, lecz już nie tak morderczych:

   http://www.faqs.org/faqs/puzzles/archive/logic/

A nad odpowiedzią na powyższy post właśnie pracuję.  

PS: Dwie rzeczy są w tym wszystkim bardzo dziwne:
1) rozwiązanie zagadki zdającej się kwestionować poprawność wnioskowań w logikach modalnych podaje facet wykładający tę logikę na wydziale Computer Science.
2) Nie ma (chwilowo nie widzę) śladu po próbach przeformułowania rozwiązania tak, by nie używać równoważności w pytaniach.

Wniosek (mój): Zawartość informacyjna tego problemu nie powinna się zmienić jak przejdziemy do ogólniejszego systemu wnioskowania. Jeśli poprawną odpowiedź zawsze można uzyskać w logice klasycznej z prawem wyłączonego środka, to co sprawia, że nie można doszukać się przeformułowania tego rozwiązania dla innych ogólniejszych logik (np. w kierunku następującego uogólnienia: {0,1} < Algebry Boolea < Algebry Heytinga, gdzie ostatnie to właśnie logiki modane; a co do ZFC, to sprawdź pojęcie "klasyfikator podobiektów w toposie", a wyjdzie Heyting z worka   ).  Zwracam uwagę, że mamy do czynienia nie ze zdaniem-schematem, którego zmienne i symbole można dowolnie podstawiać, lecz z konkretnym zdaniem-modelem, gdzie symbole ('bogini', 'kłamie', 'pytanie do...') są w pewien sposób ze sobą powiązane. Stąd moje podejrzenie, że chodzi albo o rozmiar zdań stanowiących pytania i ich liczbę, albo o trudność z przeprowadzeniem dowodu, iż rzeczywiście ten hipotetyczny zbiór pytań daje rozwiązanie naszej zagadki.

Do tej uwagi o kategoriach polacam stronę:
http://wazniak.mimuw.edu.pl/index.php?title=Strona_g%C5%82%C3%B3wna
  zwłaszcza w dwóch punktach:
1. Teoria kategorii dla informatyków
2. Logika dla informatyków