Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 14. 12. 2015 20:46
Uniform Halting Problem
Zdravím,
našel by se někdo kdo by mi potvrdil/vyvrátil mou myšlenku?
Uniform Halting Problem dále jen UHP je forma problému, kdy je otázkou jestli se obecný Turingův stroj dále jen M, zastaví pro každý vstup.
Problém jako takový je nerozhodnutelný a lze jej dokázat redukcí z Halting Problem dále jen HP.
Tady už trochu tápu.
Redukce:
Mějme M a libovolné validní slovo w (Předpokládejme že máme algoritmus který řeší HP).
Mějme M' takové že: M' je indentické s M s tím rozdílem, že nejprve vstupní pásku vymaže a na ni napíše w a tím pádem ignoruje jiné vstupní slovo a pak ne tento vstup zavolá M.
M' tedy zastaví výpočet jen v tu chvíli pokud M úspěšně skončí na vstupním w, které jako takové je určitě validním vstupem a pokud jsem schopen úspěšně v konečném čase jej zpracovat, tak jsem schopen pomocí tohoto algoritmu zpracovat libovolný validní vstup.
Čili dochází ke sporu, protože HP jako takový je nerozhodnutelný tak pak i UHP musí být nerozhodnutelný...
Uvažuju správně??
Offline
#2 14. 12. 2015 21:05
Re: Uniform Halting Problem
Zdravím.
Ne, neuvažuješ správně.
HP je sice obecně (algoritmicky) nerozhodnutelné, ale pro konkrétní stroi a konkrétní stroj a konkrétní vstup může být rozhodnutelný. Tudíž u tebe vůbec nedochází ke sporu.
Navíc postupuješ přesně obráceně. Ty nejprve vezmeš nějaký stroj a vstup (či všechny vstupy), a k ním hledáš algoritmus. Pokud chceš ale vytvořit spor, tak musíš předpokládat že máš algoritmus řešící UHP a k němu pro libovolný ("nepřítelem dodaný") storj/vstup ukázat že to tvůj algoritmus umí řešit (spíše že to nevyřeší a tam je ten spor).
Jinak pro konkrétní stroj je samonřejmě UHP algoritmicky rozhodnutelné.
Dva jsou tisíckrát jeden.
Offline
#4 14. 12. 2015 21:55
Re: Uniform Halting Problem
Tak například takto:
Uvažujme, že máme algoritmus který řeší UHP.
Nyní vezmemem libovolný stroj M a vstup w. (libovolný, takže obecný)
Vytvořímě stroj M' tak, jak jsi uváděl. Nejprve smažeme vstup a napíšeme vstup w, pak na to pustíme M. -!-POZOR -!- Tohle je ale hrubý zjednodušení, který není tak úplně korektní. Protože žádný stroj, který dokáže smazat obecný vstup a zastavit se neexistuje. Lze to ale obejít třeba tím, že si původní vstup bude stroj M umazávat "pod nohama". Výsledek sice nebude totožný, ale nás zajímá jen to jestli se zastaví a na to to nemá vliv. -!-
Nyní na stroj M' pustíme náš algoritmus který rozhoduje UHP. Pokud se zastaví pro každý vstup, tak se zastaví i M pro vstup w. Pokud není pravda, že se zastaví pro každý vstup, tak se nezastaví aní M pro vstup w. Čímž jsme zíkali HP algoritmus pro obecný vstup. #spor.
Dva jsou tisíckrát jeden.
Offline
#5 14. 12. 2015 22:43
Re: Uniform Halting Problem
Aha, pokud to tedy dobře chápu, ve zkratce:
*Máme jen jedno vstupní slovo v podobě w pro ten obecný stroj M ( nevím, proč jsem si myslel, že vstupních slov bude víc, když UHP rozhoduje pro všechny vstupy a tudíž jako vstup sám dostane jen M resp. M' v našem případě ).
*M' pouze zajistí aby na vstupní pásce bylo jen w pak na tuto pásku pustí M
*Na M' pustíme náš UHP, který by se měl tedy zastavit pro každý vstup, tudíž i pro M v M'
*Tím pádem by se M musel zastavit pro w - což je HP
Jediným úkolem stroje M' je tedy, aby zajistil, že na pásce bude pouze w a pak na ni zavolal M? Pokud bych pak stroj M' neměl a na vstup UHP dal jen obecný stroj M, co by to změnilo?
Offline
#6 14. 12. 2015 22:48
Re: Uniform Halting Problem
↑ hmnt:
změnilo by se to, ža pokud by ti UHP řek, že se M nezastaví pro každý vstup (tzn existuje alespoň jeden vstup pro který se nezastaví), tak bys něvěděl, jestli vstup w je právě tím vstupem pro keterý se nezastaví nebo ne. Tudíž bys nedostal spor.
Dva jsou tisíckrát jeden.
Offline