$\newcommand{\TM}{(Q,\Gamma, \Sigma, \delta, q_0, q_{accept}, q_{reject})}$

Turing Maskiner¶

1568038791587

Turing Maskine¶

Definition

En 7-tuppel $\TM$

$Q$ endelig mængde af tilstande
$\Gamma$ bånd-alfabet
$\Sigma$ input alfabet ( $\Sigma \subseteq \Gamma$ )
$\delta$ overføringsfuntion
$q_0$ starttilstand ( $q_0 \in Q$ )
$q_{accept}$ accepttilstand ( $q_{accept} \in Q$ )
$q_{reject}$ forkasttilstand ( $q_{reject} \in Q$ )

$q_{accept} \neq q_{reject}$ $$ \delta: (Q \setminus {q_{accept},q_{reject}}) \times \Gamma \to Q \times \Gamma \times {L,R} $$

$L$ : Venstre $R$ : Højre

Example

Se eksempel Lektion 1, Video 2

1568039654270

Konfiguration¶

Definition

Givet en $TM$ $M = \TM$

er en konfiguration en streng $$ uqav, $$ hvor $u$ er del af bånd til venstre for hoved $(u\in\Gamma^*)$ , og $q\in Q$ , og $a$ indhold af det felt $M$ ser nu $(a \in \Gamma)$ , og $v$ ikke-tomme del af bånd til højre for hoved $(v \in \Gamma^*)$

Beregning¶

Definition

1568040267681

Standsende Beregning¶

1568040358563

En turing maskine kan gå i en uendelig løkke!

Accept af Streng¶

Definition

En $TM$ $M$ accepterer input $w$ , hvis:

$M$ har en accepterende beregning på input $w$

En $TM$ $M$ afviser input $w$ hvis:

$M$ har en afvisende beregning på input $w$

Bemærk: At $M$ ikke accepterer $w$ er ikke det samme som at $M$ afviser $w$ , da en $TM$ kan gå i en uendelig løkke!

Turing Genkendelig Sprog¶

1568040718941

Med andre ord:

Afgørbart¶

1568040897166

1568041058759

Note

Indsæt fra afsnit 4 og frem

Last update: September 15, 2019