– Որոշման P-ի խնդիրը համարվում է կիսաորոշելի (այսինքն՝ ունի կիսաալգորիթմ), եթե P-ի բոլոր այո օրինակների L լեզուն r.e է: – (Համարժեքության խնդիր DFA-ի համար) Հաշվի առնելով երկու DFA-ները, նրանք ընդունո՞ւմ են նույն լեզուն: Ապացույց. Հիշեք Կանտորի փաստարկը Առաջին դասախոսությունից:
Երբ ասում են, որ խնդիրը կիսալուծելի է:
Կիսավճռելի խնդիրներն են - ի համար, որոնք Թյուրինգի մեքենան կանգ է առնում իր կողմից ընդունված մուտքի վրա, բայց այն կարող է կամ ընդմիշտ դադարեցնել կամ կապել այն մուտքի վրա, որը մերժվում է Թյուրինգ մեքենայի կողմից. Նման խնդիրները կոչվում են Թյուրինգի ճանաչելի խնդիրներ:
Ո՞րն է մասամբ լուծելի խնդիրը:
Սահմանում. Մեկ որի կապակցված լեզուն-ը ռեկուրսիվորեն թվարկելի լեզու է:Համարժեքորեն, գոյություն ունի ալգորիթմ, որը դադարեցնում և թողարկում է 1 «այո» պատասխան ունեցող յուրաքանչյուր օրինակի համար, բայց «ոչ» պատասխան ունեցող օրինակների համար թույլատրվում է կա՛մ չդադարեցնել, կա՛մ դադարեցնել և թողարկել 0::
Խնդիրը կասեցնելը մասամբ լուծելի՞ է:
Ալան Թյուրինգը 1936 թվականին ապացուցեց, որ Թյուրինգի մեքենայի վրա աշխատող ընդհանուր ալգորիթմը, որը լուծում է բոլոր հնարավոր ծրագիր-ներածման զույգերի դադարեցման խնդիրը, անպայմանորեն չի կարող գոյություն ունենալ: Հետևաբար, դադարեցման խնդիրն անորոշ է Թյուրինգի մեքենաների համար:
Ինչու է դադարեցման խնդիրը կիսալուծելի:
Լեզուն համարվում է կիսաորոշելի, եթե գոյություն ունի Թյուրինգի մեքենա, որը կանգ է առնում, եթե բառը պատկանում է լեզվին (ԱՅՈ դեպքեր) և կարող է մերժել կամ գնալ անսահմանության մեջ: հանգույց, եթե բառը չի պատկանում լեզվին (առանց դեպքի):
