– Një problem vendimi P thuhet se është gjysmë i zgjidhshëm (d.m.th., ka një gjysmë algoritëm) nëse gjuha L e të gjitha rasteve po në P është r.e. – (Problemi i ekuivalencës për DFA) Duke pasur parasysh dy DFA, a pranojnë të njëjtën gjuhë? Vërtetim: Kujtoni argumentin e Cantor-it nga Leksioni i Parë.
Kur një problem thuhet se është gjysmë i zgjidhshëm?
Problemet gjysmë të vendosshme janë ato për të cilat një makinë Turing ndalon në hyrjen e pranuar prej saj, por ajo mund të ndalojë ose të qarkullojë përgjithmonë në hyrjen që refuzohet nga Makina Turing. Probleme të tilla quhen si probleme të njohura të Turingut.
Cili është problemi pjesërisht i zgjidhshëm?
Përkufizim: Një gjuha e lidhur e të cilit është një gjuhë e numërueshme në mënyrë rekursive. Në mënyrë ekuivalente, ekziston një algoritëm që ndalon dhe nxjerr 1 për çdo shembull që ka një përgjigje "po", por për rastet që ka një përgjigje "jo" lejohet ose të mos ndalojë ose të ndalojë dhe të nxjerrë 0.
A është pjesërisht e zgjidhshme ndalimi i problemit?
Alan Turing vërtetoi në vitin 1936 se një algoritëm i përgjithshëm që funksionon në një makinë Turing që zgjidh problemin e ndalimit për të gjitha çiftet e mundshme të hyrjes së programit nuk mund të ekzistojë domosdoshmërisht. Prandaj, problemi i ndalimit është i pazgjidhshëm për makinat Turing.
Pse problemi i ndalimit është gjysmë i zgjidhshëm?
Një gjuhë thuhet se është gjysmë e zgjidhshme nëse ekziston një makinë Turing e cila ndalon nëse një fjalë i përket gjuhës (PO raste) dhe mund të refuzojë ose të shkojë në pafundësi lak nëse fjala nuk i përket gjuhës (JO rast).
