– Tiek uzskatīts, ka lēmuma problēma P ir daļēji izšķirama (t.i., tai ir daļēji algoritms), ja valoda L visiem jā gadījumiem uz P ir r.e. – (DFA līdzvērtības problēma) Vai, ņemot vērā divus DFA, tie pieņem vienu un to pašu valodu? Pierādījums: atcerieties Kantora argumentu no pirmās lekcijas.
Ja tiek teikts, ka problēma ir daļēji atrisināma?
Daļēji izšķiramas problēmas ir tās kuras Tjūringa mašīna apstājas pie tās pieņemtās ievades, bet tā var vai nu apturēt, vai uz visiem laikiem cilpot ievadei, kuru Tjūringa mašīna noraida. Šādas problēmas sauc par Tjūringa atpazīstamām problēmām.
Kas ir daļēji atrisināma problēma?
Definīcija: Viena kura saistītā valoda ir rekursīvi uzskaitāma valoda. Līdzvērtīgi pastāv algoritms, kas aptur un izvada 1 katram gadījumam, kura atbilde ir "jā", bet gadījumiem, kad atbilde ir "nē", ir atļauts vai nu neapturēt, vai apturēt un izvadīt 0.
Vai problēmas apturēšana ir daļēji atrisināma?
Alans Tjūrings 1936. gadā pierādīja, ka vispārējs algoritms, kas darbojas Tjūringa mašīnā, kas atrisina apturēšanas problēmu visiem iespējamajiem programmas ievades pāriem, noteikti nevar pastāvēt. Līdz ar to apturēšanas problēma ir neatrisināma Tjūringa mašīnām.
Kāpēc apturēšanas problēma ir daļēji atrisināma?
Valoda tiek uzskatīta par daļēji izšķiramu, ja pastāv Tjūringa mašīna, kas apstājas, ja vārds pieder valodai (JĀ gadījumi) un var noraidīt vai nonākt bezgalībā. cilpa, ja vārds nepieder valodai (NAV reģistra).
