Dit is waarom het beslisbaar is en hoe een Turing-machine dit kan beslissen:

Beslisbaarheid: Een taal is beslisbaar als er een Turing-machine bestaat die stopt bij elke invoer en de invoer accepteert als deze in de taal aanwezig is en deze afwijst als dat niet het geval is.

Turingmachine-beslisser: We kunnen een Turingmachine ‘D’ construeren die ‘A’ als volgt beslist:

1. Invoer: `D` heeft als invoer ``, waarbij `M` de codering is van een DFA en `w` een string is.

2. Simulatie: `D` simuleert de DFA `M` op invoerstring `w`. Dit is mogelijk omdat `D` de huidige status van `M` en het huidige symbool dat uit `w` wordt gelezen, kan volgen. De simulatie verloopt als volgt:

* Start `M` in de oorspronkelijke staat.

* Voor elk symbool in `w`, overgang `M` naar de volgende toestand volgens zijn overgangsfunctie.

3. Accepteren/Weigeren:

* Als `M` eindigt in een accept-status na het lezen van de volledige string `w`, dan accepteert `D` ``.

* Als `M` eindigt in een niet-accepterende status na het lezen van de volledige string `w`, dan wijst `D` `` af.

Waarom dit werkt:

* DFA's stoppen altijd: DFA's verwerken elk invoersymbool per definitie precies één keer en stoppen dan. Ze hebben geen oneindige lussen of ongedefinieerd gedrag.

* Simulatie is mogelijk: Een Turing-machine kan het deterministische gedrag van een DFA gemakkelijk simuleren, omdat deze over voldoende geheugen en controle beschikt om de status en invoerpositie van de DFA te volgen.

* Stoppen: De Turingmachine `D` stopt altijd omdat de DFA-simulatie altijd stopt.

* Juistheid: `D` accepteert exact de strings `` waar `M` `w` accepteert, en het verwerpt exact de strings `` waar `M` `w` *niet* accepteert.

Formeel bewijs (schets):

Om de beslisbaarheid rigoureus te bewijzen, moet je:

1. Definieer de codering formeel: Specificeer hoe een DFA `M` en een string `w` worden weergegeven als strings in het invoeralfabet van de Turing-machine `D`.

2. Definieer de Turing-machine `D` formeel: Geef een toestandsdiagram of een formele beschrijving van de overgangen van `D`.

3. Bewijs juistheid: Laat zien dat als `` in de taal `A` is, `D` het accepteert, en als `` *niet* is in de taal `A`, `D` het afwijst.

4. Bewijs het stoppen: Laat zien dat `D` altijd stopt bij elke invoer.

Samengevat: Omdat we een Turing-machine kunnen bouwen die altijd stopt en correct accepteert of afwijst op basis van het feit of een gegeven DFA een bepaalde string accepteert, is de taal `A` beslisbaar. Dit is een fundamenteel en belangrijk voorbeeld in de berekeningstheorie.