Ako je možné uplatniť zníženie problémov s zastavením na určenie výpočtu daného algoritmu?

Zníženie problémov je výkonným nástrojom na preukázanie toho, že daný problém (alebo algoritmus) je nerebateľný , čo znamená, že neexistuje žiadny všeobecný algoritmus, ktorý by vždy mohol správne určiť, či daný problémový inštancia je možné vyriešiť nejakým iným algoritmom. To * nie * priamo vám nepovie, či je algoritmus * vypočítateľný *, ale skôr, ak určuje * vlastnosť o * algoritme je vypočítateľná.

Takto funguje redukcia:

1. Pochopenie problému zastavenia:

*Problém zastavenia sa pýta:Vzhľadom na algoritmus (program) *H *a vstup *i *pre tento algoritmus, bude *H *Halt (dokončiť spustený), keď spustí vstup *i *?

* Problém s zastavením je nerečiteľný . Neexistuje žiadny algoritmus, `Halts (h, i)`, ktorý sa môže vždy správne vrátiť `true`, ak *h *sa zastavuje na *i *a` false`, ak *h *slučky navždy.

2. Technika redukcie (dôkaz proti rozpore):

Aby ste dokázali, že problém * p * je nerozhodnuteľný, robíte nasledujúce:

1. To znamená, že predpokladáme, že existuje algoritmus „solvep (inputforp)“, ktorý vždy správne vracia riešenie pre akúkoľvek inštanciu problému *p *.

2. Zostavte redukciu: Musíte ukázať, ako použiť hypotetický algoritmus „solvep ()` na vyriešenie problému zastavenia. Inými slovami, vytvoríte algoritmus „Halts (H, i)`, ktorý používa ako podprogram `solvep ()`. Tento algoritmus `Halts (H, I)` by mal fungovať takto:

`` `

Zastavenie (H, i):

1. Transformujte inštanciu problémov s zastavením (H, i) na inštanciu problému P, nazývajme to „inputforp“. Toto je rozhodujúci krok:Vytvárate `InputForp` tak, že *riešenie problému P na tomto vstupe priamo odhalí, či sa H zastaví na i *. Špecifiká toho, ako robíte túto transformáciu, úplne závisia od problému *p *.

2. ResultP =Solvep (InputForp) // Zavolajte nášmu hypotetickým riešením pre problém P.

3. Na základe výsledku, určte, či sa H zastaví na i, a podľa toho vráťte alebo nepravdivo.

`` `

3. ukazuje, že vaše zníženie znamená riešenie problému zastavenia: Vysvetlite jasne, ako výsledok `solvep (inputforp)` priamo povie, či algoritmus *h *zastavuje pri vstupe *i *.

4. protirečenie: Pretože je známe, že problém zastavenia je nerečiteľný, a preukázali ste, že na jeho vyriešenie by ste sa mohli použiť hypotetický „solvep“, dosiahli ste rozpor.

5. Záver: Preto musí byť náš počiatočný predpoklad ( * p * rozhodujúci) nepravdivý. Preto je problém * p * nerozhodnuteľný.

Kľúčové nápady a výzvy:

* transformácia je kľúč: Najťažšia časť je nájdenie transformácie z (h, i) na inštanciu *p *tak, aby riešenie na *p *priamo odhalilo, či *h *sa zastaví na *i *. Vyžaduje si to chytrosť a pochopenie problému zastavenia a problému *p *.

* Protia protirečenie: Nie ste * priamo *, čo dokazuje, že * p * je nerozhodnuteľný. Ukazujete, že keby * P * * boli * rozhodné, viedlo by to k nemožnosti (riešenie problému zastavenia).

* Zovšeobecnenie: Cieľom je dokázať, že *nemôže existovať algoritmus, ktorý rieši *p *pre *všetky možné vstupy *. Vaše zníženie musí byť platné pre akýkoľvek ľubovoľný algoritmus *H *a vstup *i *.

Príklad:Problémom prázdnoty pre Turing Stromes

Problémom prázdnoty pre Turing Stromes sa pýta:je vzhľadom na stroj *m *, je jazyk akceptovaný *m *prázdny (t. J. Prijíma *M *nejaký *vstup)? Ukážme, že je to nerozhodnuteľné.

1. Predpokladajme, že prázdnota je rozhodná: Predpokladajme, že existuje algoritmus „isempty (m)“, ktorý sa vracia „true“, ak je jazyk prijatý * m * prázdny a „false“ inak.

2. Redukcia: Vytvoríme algoritmus `Halts (h, i)`, ktorý používa `isEmpty ()`:

`` `

Zastavenie (H, i):

1. // Vytvorte nový Turingov stroj m_hi

// - m_hi berie akýkoľvek vstup w.

// - m_hi najskôr simuluje H na I.

// - Ak sa H zastaví na i, potom m_hi prijíma w.

// - Ak H nezastaví I, potom navždy m_hi slučky.

M_HI =CONTRUCTTM (H, I)

2. Výsledok =isempty (m_hi)

3. Ak je výsledok ==true:

návrat false // h nezastavuje i

inak:

Vráťte sa true // h zastaví na i

`` `

3. Prečo to funguje:

*Ak *h *zastavuje *i *, potom `m_hi` akceptuje *každý *vstup` w`. Teda jazyk akceptovaný `m_hi` nie je prázdny (v skutočnosti je to σ*, sada všetkých reťazcov). Preto sa `isempty (m_hi)` vráti `false` a` halts (h, i) `returs` true`.

*Ak *h *sa *nezastavuje *i *, potom `m_hi` bude navždy slučka na *každom *vstupe` w`. Jazyk prijatý `m_hi` je teda prázdny. Preto `isempty (m_hi)` sa vráti „true` a` Halts (h, i) `returs` false`.

4. protirečenie: Vytvorili sme algoritmus „Halts (H, i)`, ktorý používa na vyriešenie problému zastavenia `` Isempty () `. Problém s zastavením je však nerozhodnutý, takže je to rozpor.

5. Záver: Preto je problém s prázdnotou pre Turing Stroje nerozhodnuteľný.

Dôležité poznámky:

* Redukcia ukazuje, že problém * p * je * aspoň taký tvrdý ako problém zastavenia. Pretože problém zastavenia je nerozhodnuteľný, tak je *p *.

* Redukcie sa často používajú na preukázanie nerešpektovania, ale môžu sa tiež použiť na preukázanie úplnosti NP v kontexte výpočtovej zložitosti.

* Algoritmus `ConstructTM (H, i)` Vo vyššie uvedenom príklade je teoretický konštrukt. V praxi by ste v skutočnosti „nevybudovali“ fyzický Turingov stroj. Ide o to, že * v zásade * je možné opísať takýto stroj.

Stručne povedané, zníženie problémov s zastavením je výkonná dôkazná technika, ktorá nám pomáha porozumieť obmedzeniam výpočtu. Tým, že by sme ukázali, že riešenie konkrétneho problému by znamenalo riešenie problému zastavenia (o ktorom vieme, že je nemožné), môžeme dospieť k záveru, že problém je nerozhodnuteľný.

• Predchádzajúca strana: Ako vidím, kedy bol môj počítač (win10) zavrel alebo na nečinnosti? 
• Ďalšia strana: Ako počítač pracuje na spracovaní a vykonávaní príkazov?