[11 settembre 2024] Calcolabilità

[matypist]

[cornflexxx]

Sia $M$ la $TM$ che decide $L$:

1. Prende in input la stringa $u$
2. crea un contatore per il numero di $a$ e $b$ in tempo $O(\log n)$
3. Ripete i passi dal 4 al 5 fino a che non trova $\sqcup$
4. Scorre l'input, ogni volta che trova una $a$ o una $b$, contrassegna $a$ con $x$ e $b$ con $y$ $O(n)$
5. torna indietro e aggiorna il contatore di $a$ o $b$ in $O(n) + O(\log n) = O(n)$, torna al (4).
6. confronta i due contatori e verifica che il numero di $a$ sia almeno il doppio di quello di $b$.

$M$ computa ad ogni iterazione in $O(n)$ per un totale di $n$ iterazioni, quindi $O(n^2)$

---

Nel caso di una $TM$ con multi-nastro possiamo utilizzare il seguente algoritmo :

1. sul primo nastro mantiene l'input
2. sul secondo nastro (vuoto) marca la prima cella e si sposta a destra.
3. sul terzo nastro faccio la stessa cosa di (2).
4. La testina sul primo nastro scorre tutto l'input e ogni volta che trova $a$ la copia sul secondo nastro. Il terzo nastro fa la stessa cosa con $b$.
5. Finito di scorrere l'input, scorriamo il terzo nastro verso sinistra e ogni due $b$ incontrate, scorro di una cella sul secondo controllando se ci sia $a$, se finisco trovo il simbolo marcato sul secondo nastro prima che il terzo nastro lo incontri rifiuto
6. altrimenti accetta

$M$ scorre una volta l'input in $n$ passi, copiando i simboli sul nastro 2 e 3 in $O(1)$, quindi scorre all'indietro i nastri 2 e 3 in $O(n)$. Costo computazionale : $O(n) + O(1) +O (n) = O(n)$