Techniquement, on peut aussi faire une machine de Turing avec un ruban infini d'un seul côté.
Ça a le même pouvoir expressif en termes de calculabilité. Une manière de voir ça c'est qu'un ruban bi-infini, tu peux choisir arbitrairement une case et le plier en deux à cet endroit : te voilà avec un ruban infini d'un seul côté.
Par contre, en termes de complexité temporelle, il me semble que tu récupère un petit overhead à cause de la transformation (ça doit être un facteur constant 2 à vue de nez).
[^] # Re: Journal bookmark mais sujet intéressant
Posté par Perthmâd . En réponse au journal A Turing machine. Évalué à 4.
Ça a le même pouvoir expressif en termes de calculabilité. Une manière de voir ça c'est qu'un ruban bi-infini, tu peux choisir arbitrairement une case et le plier en deux à cet endroit : te voilà avec un ruban infini d'un seul côté.
Par contre, en termes de complexité temporelle, il me semble que tu récupère un petit overhead à cause de la transformation (ça doit être un facteur constant 2 à vue de nez).