Machine de Turing sans "Blanc"

Discutez d'informatique ici !
dedi820
Membre Naturel
Messages: 32
Enregistré le: 07 Avr 2009, 15:30

Machine de Turing sans "Blanc"

par dedi820 » 27 Avr 2013, 20:55

Bonjour,

J'ai un travail à réaliser sur les machines de Turing, et soudain un immense doute m'envahi, est-ce qu'une machine de Turing peu avoir un côté (ou les deux) du ruban sans aucun blanc ? C'est à dire (puisque le ruban est toujours infini des deux côtés) qu'un côté (ou les deux) serait une suite infinie de caractères différents de blanc, par exemple

...11111111101011[0]101BBBBBBBB.... sans jamais plus aucun blanc aussi loin qu'on aille à gauche.

Est-ce que ce type de ruban est possible dans un machine de Turing ?

Merci d'avance pour vos réponses !



dedi820
Membre Naturel
Messages: 32
Enregistré le: 07 Avr 2009, 15:30

par dedi820 » 28 Avr 2013, 10:15

Une idée ?

LaCoc6nl
Membre Naturel
Messages: 90
Enregistré le: 29 Mar 2013, 21:06

par LaCoc6nl » 28 Avr 2013, 14:39

dedi820 a écrit:
...11111111101011[0]101BBBBBBBB.... sans jamais plus aucun blanc aussi loin qu'on aille à gauche.

Est-ce que ce type de ruban est possible dans un machine de Turing ?



Le théorème de Rice rend le calcul indécidable par machine de Turing. La physique du système le résout...

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 2 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite