Një gjuhë quhet e Decidueshme ose Rekursive nëse ka një makinë Turing e cila pranon dhe ndalon në çdo varg hyrës w. Çdo gjuhë e vendosur është e pranueshme nga Turing. Një problem vendimi P është i zgjidhshëm nëse gjuha L e të gjitha rasteve po të P është e zgjidhshme.
Çfarë kuptoni me vendosmëri?
: i aftë për t'u vendosur në mënyrë specifike: i aftë të vendoset si vijon ose jo nga aksiomat e një sistemi logjik A ishte logjika e plotë … ? Dhe a ishte e zgjidhshme, në kuptimin që ekzistonte një metodë që demonstronte të vërtetën apo falsitetin e çdo deklarate? -
Cili është ndryshimi midis vendosshmërisë dhe pavendosshmërisë?
Një problem vendimi është i zgjidhshëm nëse ekziston një algoritëm vendimi për të. Përndryshe është e pavendosur. Për të treguar se një problem vendimi është i zgjidhshëm, mjafton të jepet një algoritëm për të.
Si e llogaritni vendosmërinë?
Një gjuhë është e zgjidhshme nëse dhe vetëm nëse ajo dhe plotësuesi i saj janë të dallueshëm. Dëshmi. Nëse një gjuhë është e zgjidhshme, atëherë plotësimi i saj është i zgjidhshëm (me mbyllje nën plotësim).
Cili është problemi i vendosshmërisë?
(përkufizim) Përkufizim: Një problem vendimi që mund të zgjidhet nga një algoritëm që ndalon në të gjitha hyrjet në një numër të kufizuar hapash Gjuha e lidhur quhet gjuhë e zgjidhshme. I njohur gjithashtu si problem plotësisht i zgjidhshëm, i zgjidhshëm algoritmikisht, i zgjidhshëm në mënyrë rekursive.
