Verduidelik die verskil tussen 'n beslisbare taal en 'n Turing-herkenbare maar nie-beslisbare taal.
'n Bepaalbare taal en 'n Turing-herkenbare maar nie-beslisbare taal is twee verskillende konsepte in die veld van rekenaarkompleksiteitsteorie, spesifiek met betrekking tot Turing-masjiene. Om die verskil tussen hierdie twee tipe tale te verstaan, is dit belangrik om eers die basiese definisies en kenmerke van Turing-masjiene en taalherkenning te begryp.
'n Turing-masjien is 'n abstrakte rekenaartoestel wat bestaan uit 'n oneindige band wat in selle verdeel is, 'n lees-/skryfkop wat langs die band kan beweeg, en 'n beheereenheid wat die masjien se gedrag bepaal. Dit kan gesien word as 'n wiskundige model van 'n algemene-doel rekenaar. Turing-masjiene werk op invoerstringe en kan verskeie bewerkings uitvoer soos om simbole te lees, simbole te skryf, die kop te beweeg en die interne toestand te verander.
Taalherkenning verwys na die vermoë van 'n Turing-masjien om te bepaal of 'n gegewe invoerstring aan 'n spesifieke taal behoort. 'n Taal is 'n stel stringe oor 'n gegewe alfabet. In die konteks van Turing-masjiene word gesê dat 'n taal bepaalbaar is as daar 'n Turing-masjien bestaan wat elke string in die taal kan stop en aanvaar, en elke string wat nie in die taal is nie, stop en verwerp. Met ander woorde, 'n beslisbare taal is een waarvoor daar 'n algoritmiese prosedure bestaan om te besluit of 'n gegewe string 'n lid van die taal is.
Aan die ander kant is 'n taal Turing-herkenbaar as daar 'n Turing-masjien bestaan wat elke snaar in die taal stop en aanvaar, maar kan óf stop en verwerp óf onbepaald loop op snare wat nie in die taal is nie. Met ander woorde, 'n Turing-herkenbare taal is een waarvoor daar 'n Turing-masjien bestaan wat elke string in die taal kan herken en aanvaar, maar nie noodwendig elke string wat nie in die taal is nie, verwerp. Dit beteken dat 'n Turing-herkenbare taal snare kan hê wat nie deur die Turing-masjien aanvaar of verwerp word nie.
Om op te som, die belangrikste verskil tussen 'n beslisbare taal en 'n Turing-herkenbare maar nie-beslisbare taal lê in die gedrag van die Turing-masjien op snare wat nie in die taal is nie. 'n Beslisbare taal waarborg dat die Turing-masjien elke string sal stop en óf aanvaar óf verwerp, terwyl 'n Turing-herkenbare maar nie-beslisbare taal die moontlikheid toelaat dat die Turing-masjien onbepaald op stringe wat nie in die taal is nie, sal loop.
Om hierdie verskil te illustreer, kom ons kyk na twee voorbeelde. Oorweeg eers die taal van alle binêre stringe wat priemgetalle verteenwoordig. Hierdie taal is beslisbaar omdat daar 'n algoritme bestaan om te bepaal of 'n gegewe binêre string 'n priemgetal verteenwoordig. 'n Turing-masjien kan ontwerp word om elke priemgetalstring te stop en te aanvaar, en om elke nie-priemgetallestring te stop en te verwerp.
Kom ons kyk nou na die taal van alle binêre snare wat die beskrywing verteenwoordig van 'n Turing-masjien wat op 'n leë invoer stop. Hierdie taal is Turing-herkenbaar, maar nie bepaalbaar nie. Daar bestaan 'n Turing-masjien wat elke string wat 'n stilstaande Turing-masjien verteenwoordig, kan herken en aanvaar, maar dit kan nie waarborg om elke nie-stakende Turing-masjienbeskrywing te stop en te verwerp nie. Dit is as gevolg van die bekende stopprobleem, wat sê dat daar geen algemene algoritme is om te bepaal of 'n arbitrêre Turing-masjien op 'n gegewe inset stop nie.
'n Beslisbare taal waarborg dat elke string algoritmies besluit kan word om 'n lid te wees of nie, terwyl 'n Turing-herkenbare maar nie-beslisbare taal die moontlikheid moontlik maak om onbepaald te lus op snare wat nie in die taal is nie. Hierdie konsepte is fundamenteel in berekeningskompleksiteitsteorie en help ons om die grense van berekening te verstaan.
Ander onlangse vrae en antwoorde t.o.v EITC/IS/CCTF Computational Complexity Theory Fundamentals:
- NP is die klas tale wat polinoomtydverifieerders het. Maar die verifieerder van 'n klas P is polinoom. Dit lyk asof hierdie NP-definisie los of teenstrydig is.
- 'n Verifieerder vir klas P is polinoom?
- Kan 'n Nondeterministic Finite Automaton (NFA) gebruik word om die toestandsoorgange en aksies in 'n firewall-konfigurasie voor te stel?
- Is die gebruik van drie bande in 'n multiband TN gelykstaande aan enkelbandtyd t2(vierkant) of t3(kubus)? Met ander woorde is die tydskompleksiteit direk verwant aan die aantal bande?
- As die waarde in die vastepuntdefinisie die limiet van die herhaalde toepassing van die funksie is, kan ons dit steeds 'n vaste punt noem? In die voorbeeld wat gewys word as ons in plaas van 4->4 4->3.9, 3.9->3.99, 3.99->3.999 het, … is 4 steeds die vaste punt?
- As ons twee TM'e het wat 'n beslisbare taal beskryf, is die ekwivalensievraag nog onbeslisbaar?
- In die geval van die opsporing van die begin van die band, kan ons begin deur 'n nuwe band T1=$T te gebruik in plaas daarvan om na regs te skuif?
- Hoe groot is die stapel van 'n PDA en wat bepaal die grootte en diepte daarvan?
- Is daar huidige metodes om Tipe-0 te herken? Verwag ons dat kwantumrekenaars dit haalbaar sal maak?
- Hoekom is LR(k) en LL(k) nie ekwivalent nie?
Sien meer vrae en antwoorde in EITC/IS/CCTF Computational Complexity Theory Fundamentals