Accepter signifie-t-il que le TM lira et reconnaîtra un caractère de la cellule dans laquelle il lit actuellement? Et est-ce le cas qu'un TM s'arrête si l'entrée est décidable?
terminology
turing-machines
undecidability
sdfasdgasg
la source
la source
Réponses:
L'acceptation et le rejet de l'état dans lequel une machine de Turing peut éventuellement entrer est basé sur la chaîne lue sur la bande, et pas seulement sur le symbole d'une cellule. Bien sûr, la décision d'entrer dans une bande d'acceptation ou de rejet est finalement prise sur la base d'un symbole.
Une machine Turing peut éventuellement entrer dans un état d'acceptation, entrer dans un état de rejet ou boucler pour toujours. S'il entre dans un état d'acceptation ou de rejet, il s'arrête.
Une machine de Turing est considérée comme totale si elle s'arrête sur toutes les entrées.
La langue acceptée par une machine de Turing est l'ensemble de tous les mots qui, lorsqu'ils sont fournis en entrée à la machine de Turing, amènent la machine de Turing à entrer dans un état d'acceptation.
Une langue est dite décidable si et seulement s'il existe une machine Turing totale qui acceptera la langue.
la source