Turingmaskine: Forskelle mellem versioner
Content deleted Content added
No edit summary |
No edit summary |
||
Linje 2:
En turingmaskine kan være en '''''specifik turingmaskine''''' som er konstrueret til at løse et bestemt problem, eller det kan være en '''''universel turingmaskine''''' som kan læse en kodet beskrivelse af en vilkårlig turingmaskine inkl. dennes inddata, og så udføre dens beregninger.
==Formel definition==
En Turingmaskine er en 7-tuple(<math>\mathcal{Q},\Sigma,\Gamma,\delta,q_{0},q_{accepter},q_{afvis}</math>), hvor <math>\mathcal{Q},\Sigma,\Gamma</math> er endelige mængder. Og<br />
<math>\mathcal{Q}</math> er mængden af tilstande.<br />
<math>\Sigma</math> er inputalfabetet hvor den tomme streng ikke er del af.<br />
<math>\Gamma</math> er båndalfabetet hvor den tomme streng samt <math>\Sigma</math> er del af.<br />
<math>q_{0}</math> er starttilstanden hvor <math>q_{0} \in \mathcal{Q}</math> og <math>q_{0}</math>.<br />
<math>q_{accepter}</math> er den accepterende tilstand og <math>q_{accepter} \in \mathcal{Q}</math><br />
<math>q_{afvis}</math> er den afvisende tilstand og <math>q_{afvis} \in \mathcal{Q}, q_{afvis} \neq q_{accepter}</math>
| |||