Différence entre Turing-Decidable et Co-Turing-Decidable

Je suis vraiment du mal avec la compréhension de la différence entre ces deux. À partir de mon livre, il décrit essentiellement la différence en disant

une langue est co-turing reconnaissable si c'est le complément de turing-langage reconnaissable.

Je suppose que la partie de cette définition, je ne comprends pas, c'est: que signifie-t-il quand il est complément d'un turing-langage reconnaissable?

Exactement comment déterminez-vous si c'est un complément d'une autre langue?

source d'informationauteur Jason M.

  1. 38

    (Note - les termes "Turing decidable" et "co-Turing decidable" sont la même chose. Cependant, "Turing-reconnaissable" et "co-Turing-reconnaissable" ne sont pas les mêmes, et c'est ce que j'ai décidé de couvrir dans ma réponse. La raison pour cela est que si une langue est decidable, puis son complément doit être decidable. Ce n'est pas vrai reconnaissable langues.)

    Intuitivement, une langue est Turing-reconnaissable si il y a un programme d'ordinateur qui, étant donné une chaîne de caractères dans la langue, peut confirmer que la chaîne est en effet dans la langue. Ce programme pourrait boucle à l'infini si la chaîne n'est pas dans la langue, mais c'est la garantie de toujours accepter éventuellement si vous lui donnez une chaîne de caractères dans la langue.

    Même s'il est vrai qu'une langue est co-Turing-reconnaissable si c'est le complémentaire d'un langage Turing-reconnaissable, cette définition n'est pas jeter plus de lumière sur ce qui se passe. Intuitivement, si une langue est co-Turing-reconnaissable, cela signifie qu'il ya un programme d'ordinateur qui, étant donné une chaîne pas dans la langue, finira par confirmer que la chaîne n'est pas dans la langue. Il pourrait en boucle à l'infini si la chaîne est en effet dans la langue, mais. La raison pour cela est simple: si une chaîne de caractères w n'est pas contenue dans une co-Turing-langage reconnaissable, alors que la chaîne w doit être contenue dans le complément de ce que le co-Turing-langage reconnaissable, qui, par définition, doit être Turing-reconnaissable. Puisque w est dans la Turing-reconnaissable complément, il doit y avoir un programme qui peut confirmer que w est en effet dans le compléter. Ce programme peut donc confirmer que w n'est pas dans l'original co-Turing-langage reconnaissable.

    En bref, Turing-la facilité d'identification signifie qu'il existe un programme qui permet de confirmer qu'une chaîne w est dans une langue, et co-Turing-la facilité d'identification signifie qu'il existe un programme qui permet de confirmer qu'une chaîne w est pas dans la langue.

    Espérons que cette aide!

  2. -1

    Un langage est Reconnaissable ssi il existe une Machine de Turing qui s'arrête et accepte seulement les chaînes de la langue et pour les chaînes non dans la langue, la TM, soit rejette, ou de ne pas mettre fin à tous. Remarque: il n'est pas nécessaire que la Machine de Turing doivent s'arrêter pour les chaînes non dans la langue.

    Une langue est Decidable ssi il existe une Machine de Turing qui accepte les chaînes de la langue et de rejeter les chaînes non dans la langue.