1. Stopt bij alle invoer: Het TM moet uiteindelijk een acceptatiestatus of een afwijzingsstatus bereiken, ongeacht de invoerreeks. Het kan niet eeuwig blijven herhalen.

2. Accepteert tekenreeksen in de taal L: Als een string `w` in L staat, stopt het TM in een acceptatiestatus.

3. Verwerpt tekenreeksen die niet in de taal L:zijn Als een string `w` niet in L staat, stopt het TM in een afwijzingsstatus.

Met andere woorden, een beslisbare taal heeft een Turingmachine die fungeert als een perfecte lidmaatschapstester:hij geeft altijd een "ja" of "nee" antwoord en doet dit altijd binnen een beperkte hoeveelheid tijd.

Hier volgt een overzicht van veelgebruikte technieken en overwegingen:

1. Een Turingmachine (TM) bouwen Beschrijving:

* Beschrijving op hoog niveau: Begin met een duidelijke, voor mensen leesbare beschrijving van het algoritme van het TM. Dit zou de logica moeten verklaren en de stappen die nodig zijn om de invoer te verwerken. Zie het als pseudocode.

* Beschrijving op implementatieniveau (optioneel): U *kunt* een beschrijving op een lager niveau geven, waarbij u de statussen, de overgangsfunctie, het bandalfabet, enz. specificeert. Dit is vaak vervelend en niet vereist, tenzij er expliciet om wordt gevraagd, of als het algoritme erg subtiel is en een nauwkeurige definitie vereist. Concentreer u eerst op de beschrijving op hoog niveau.

* Duidelijkheid is de sleutel: Het belangrijkste is dat uw beschrijving begrijpelijk en overtuigend is. Een slecht geschreven beschrijving op hoog niveau kan moeilijker te begrijpen zijn dan een goed geschreven formele beschrijving.

2. Algemene strategieën voor het ontwerpen van beslissers:

* Simuleer andere machines: Als je kunt aantonen dat L kan worden beslist door een andere beslisbare taal (of meerdere van dergelijke talen) te simuleren, heb je aangetoond dat L beslisbaar is. Bij veel bewerkingen is de beslisbaarheid gesloten (vereniging, snijpunt, complement, aaneenschakeling, Kleene-ster).

* Omzetten naar een eenvoudiger probleem: Probeer het probleem te herformuleren in een gelijkwaardig, maar gemakkelijker op te lossen probleem.

* Overweeg basisgevallen en recursie: Als het probleem een ​​recursieve structuur heeft, kan een recursief algoritme worden vertaald in een Turing Machine-beslisser. Zorg ervoor dat de recursie begrensd is om beëindiging te garanderen.

* Uitgebreid zoeken: Als de invoerruimte eindig is of kan worden begrensd, kunt u vaak uitgebreid zoeken om alle mogelijkheden te controleren. Het cruciale punt is dat de zoektocht gegarandeerd moet worden beëindigd.

* Maak gebruik van bekende beslisbare talen: Bouw voort op de wetenschap dat bepaalde talen al beslisbaar zijn. Bijvoorbeeld reguliere talen, contextvrije talen en vele andere.

3. Technieken voor het aantonen van beëindiging:

* Tellen: Laat zien dat het algoritme een teller omvat die strikt toeneemt of afneemt in de richting van een grens.

* Afnemende grootte: Laat zien dat elke stap van het algoritme de omvang van het probleem verkleint totdat het een triviaal basisscenario bereikt.

* Geen oneindige lussen: Beweer overtuigend dat het algoritme niet in een oneindige lus kan terechtkomen. Hierbij kan het bijvoorbeeld gaan om het laten zien dat de machine de bandkop altijd beweegt, of dat de bezochte toestanden binnen een bepaalde periode altijd verschillend zijn.

* Simulatieduur: Als het algoritme een ander TM simuleert, stel dan een bovengrens vast voor het aantal stappen dat de simulatie zal nemen. Dit is vaak afhankelijk van de invoergrootte.

4. Voorbeelden en veelvoorkomende scenario's:

* Normale talen: Om aan te geven dat een reguliere taal beslisbaar is, geeft u een DFA op voor de taal. Een TM kan de DFA simuleren en stoppen in een acceptatie- of afwijzingsstatus op basis van de eindstatus van de DFA.

* Contextvrije talen: Gebruik het CYK-algoritme of een soortgelijk parseeralgoritme. Deze algoritmen hebben een eindige looptijd.

* Onbeslisbaarheid: Begrijp het stopprobleem. Je *kan* niet beslissen of een willekeurige Turingmachine stopt bij een willekeurige invoer. Als u het stopprobleem tot uw probleem kunt herleiden, heeft u aangetoond dat uw probleem onbeslisbaar (niet beslisbaar) is.

* Leegheidstesten: Het weergeven van een taal die *leeg* is (bevat geen tekenreeksen) is soms gemakkelijker dan laten zien dat deze beslisbaar is. De taal van een Turingmachine is bijvoorbeeld *niet* beslisbaar. Gegeven een DFA of CFG is het echter beslisbaar of de taal die deze vertegenwoordigt leeg is.

5. Wat je NIET moet doen:

* Beweer niet zomaar dat het beslisbaar is zonder rechtvaardiging. U moet een redelijk argument opgeven, wat meestal betekent dat u het algoritme beschrijft.

* Geef geen TM op dat *alleen* tekenreeksen in de taal accepteert. Het moet ook strings *niet* *reject* in de taal en het moet stoppen.

* Geef geen algoritme op dat *misschien* stopt, maar de potentie heeft om voor altijd in een lus te blijven. Een beslisser *moet* stoppen.

* Verwar beslisbaarheid niet met herkenbaarheid. Een herkenbare taal vereist alleen dat een TM stopt en accepteert als de invoer in de taal is. Het kan voor altijd in een lus blijven als de invoer niet in de taal is. Beslisbare talen zijn altijd herkenbaar, maar het omgekeerde is niet waar.

* Probeer geen 'bewijs door voorbeeld' te leveren. Aantonen dat een specifieke invoer wordt geaccepteerd of afgewezen, bewijst niets over de beslisbaarheid van de taal.

Voorbeeld 1:A ={0 ⁿ 1 ⁿ | n>=0} is beslisbaar.

* Beschrijving op hoog niveau:

1. Scan de invoerreeks om er zeker van te zijn dat deze alleen uit nullen bestaat, gevolgd door enen. Zo niet, weiger dan.

2. Terwijl er zowel nullen als enen over zijn:

* Streep de meest linkse 0 af.

* Streep de meest linkse 1 af.

3. Accepteer als er geen nullen en geen enen meer zijn.

4. Als er alleen maar nullen of alleen maar enen overblijven, verwerp dan.

* Motivering: Dit algoritme stopt voor alle invoer. Stappen 1 en 3/4 beëindigen de controles. Stap 2 kruist in elke iteratie één 0 en één 1 af. Het aantal nullen en enen is eindig, dus de lus eindigt. Als het aantal nullen en enen gelijk was, accepteren we dit. Anders wijzen wij het af.

Voorbeeld 2:Gegeven een DFA D, is de taal L(D) leeg? Een_DFA ={ | D is een DFA en L(D) =∅} is beslisbaar.

* Beschrijving op hoog niveau:

1. Markeer de startstatus van D.

2. Herhaal dit totdat er geen nieuwe staten meer gemarkeerd worden:

* Markeer elke staat die kan worden bereikt vanuit een momenteel gemarkeerde staat door een pijl in D te volgen.

3. Als er een acceptatiestatus van D is gemarkeerd, weiger deze dan.

4. Accepteer anders.

* Motivering: Dit algoritme stopt. Stap 2 onderzoekt alle mogelijke bereikbare toestanden. Het aantal toestanden in D is eindig, dus de lus eindigt. Als we een accepterende staat kunnen bereiken, is de taal niet leeg en verwerpen we. Anders is het zo en accepteren we het. Merk op dat `D` bij aanname gegarandeerd een DFA is en dus eindige toestanden heeft.

Door deze strategieën te volgen en de eigenschappen van Turingmachines en beslisbare talen te begrijpen, kunt u effectief aantonen dat een taal beslisbaar is. Vergeet niet om je te concentreren op een duidelijke en overtuigende algoritmebeschrijving en een goed argument voor de beëindiging en juistheid ervan.