De bonnes ressources pour en apprendre sur les modèles de calcul?

Question

Par curiosité, je suis en train d'essayer d'identifier quel est le modèle de calcul d'un système que je travaille avec est fonctionnellement équivalent, et de prouver l'équivalence.Le plus que je passe sur ce problème le plus je soupçonne que le système n'est pas Turing-équivalent.Ma compréhension de Machines de Turing et récursivement énumérables langues est bon, mais je ne sais pas beaucoup au sujet de automates dont les capacités sont moindres (par ex.refoulement des automates), donc je ne suis pas sûr de savoir comment procéder.

Tout d'abord, peut-on recommander une bonne ressource pour l'apprentissage sur les différents modèles de calcul?Je suis intéressé dans les grammaires, des langages et des automates, et comment prouver l'équivalence et de la différence entre chacun d'eux.Idéalement, la ressource pourrait briser tous les éléments de chaque modèle dans le plus grand détail et de les comparer.

La seconde, est une approche générale ou le cadre qui doit être utilisé lors de la tentative de s'adapter à un système sur l'un de ces modèles de calcul?

Answer 1

Je voudrais recommander un bon livre sur les sciences de l'informatique (Dans mon Uni sûr, je suis étudiant à partir de Sipser Introduction à la Théorie de Calcul, qui est très bon à mon avis.Vous pouvez également trouver un manuel libre qui enseigne la même, mais je n'ai pas d'expérience avec une donc je ne peux pas le recommander).

L'autre approche serait probablement juste de lire sur Wikipedia.Vous pouvez réellement obtenir beaucoup de kilométrage de l'article de Wikipedia, si vous savez ce que vous cherchez et dans quel ordre.Aussi, si quelque chose n'est pas clair, vous pouvez l'habitude de Google et de trouver plus de ressources sur ce sujet en particulier.

Bien sûr, ce sera pas être aussi bon qu'un vrai manuel, mais c'est un bon endroit pour commencer dès maintenant, et c'est gratuit.

En tant que point de départ, je vous recommande la lecture sur les sujets suivants (dans l'ordre):

1. Automate Fini Déterministe
2. Automate Fini Non Déterministe, et leur équivalence à DFAs.
3. Langages Réguliers, et leur équivalence à DFAs.
4. Refoulement Des Automates
5. Libre de tout contexte Grammaires, et leur équivalence de Refoulement des Automates.
6. Hiérarchie De Chomsky
7. Machines De Turing

Qui devrait offrir une très brève introduction à la plupart des modèles de calcul les gens parlent. 2:Je voudrais recommander un bon livre sur les sciences de l'informatique (Dans mon Uni sûr, je suis étudiant à partir de Sipser Introduction à la Théorie de Calcul, qui est très bon à mon avis).L'autre approche serait probablement juste de lire sur Wikipedia.Vous pouvez réellement obtenir beaucoup de kilométrage de l'article de Wikipedia, si vous savez ce que vous cherchez et dans quel ordre.Aussi, si quelque chose n'est pas clair, vous pouvez l'habitude de Google et de trouver plus de ressources sur ce sujet en particulier.Comme un point de départ, je vous recommande la lecture sur les sujets suivants (dans l'ordre):1. 1: http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Answer 2

Les conférences vidéo à partir du lien suivant donne une bonne introduction à la théorie du calcul. Ceci est l'une des meilleures ressources sur ce sujet.

Conférences Vidéo sur la théorie du calcul par le professeur Shai Simonson

Answer 3

Un texte ancien qui peut être difficile à trouver est Hopcroft et « Introduction à la théorie des automates, des langues et calcul » de Ullman. Il y a un certain nombre d'éditions --- J'ai entendu dire que '79 est le meilleur, dans la mesure où il tire les coups de poing dans l'introduction de plus petit nombre des choses complexes. Il légitime, quoique petit livre, et il introduit tout le champ, pas seulement ce que vous cherchez. Je suggère cela sur le vain espoir probable que peut-être l'un de ces « plus délicat » preuves d'autres sources laissent peut-être sur votre clé.

En tant que point de départ plus doux, il y a quelques langues « de référence » à portée de main.

• Si votre modèle peut reconnaître la langue de toutes les chaînes où il y a le même nombre de A ou B dans une chaîne, il est au moins plus puissant que EFM.
• S'il ne peut pas, alors il peut équivalent à EFM.
• De même, si votre modèle peut reconnaître la langue de toutes les chaînes où le même nombre de As, Bs et Cs dans une chaîne, alors il est plus puissant qu'un CFG, ou PDA.

Ces « langues de référence » ne sont réellement que des fonctions déguisées --- le premier est essentiellement à se demander si 2 numéros unaires sont égaux, la seconde demande si 3 numéros unaires sont égaux. Ils sont gentils et simples, et sont bien connus pour être au-dessus ou en dessous des capacités des modèles particuliers. Je ne sais pas simples pour les machines plus complexes, donc vous pouvez être vous-même.

Notez que pour le modèle « LBA », automates linéairement bornés, je crois qu'il n'y a pas de langage naturel connu qui est calculable avec un TM, mais pas un LBA. Cette déclaration est tirée de souvenirs brumeux, alors ne prenez pas comme une preuve formelle. :)

Note (enfin) que les langues « de référence » ne sont pas fondés sur l'équité. C'est-à-dire si votre modèle ne peut pas comparer 2 numéros unaire, qui fait pas signifie qu'il est nécessairement équivalent à un FSM, il pourrait être encore plus faible. Les langues se déclineront seulement ce qu'elle est supérieure à la puissance, ou moins au pouvoir.

Sur un tout (complètement) autre piste, le livre de Sipser ne fait preuve de équivalence entre regexes et États fédérés de Micronésie, ainsi qu'entre les PDA et CFG. Je ne sais pas comment cela sera utile, que vous êtes assez vague sur ce genre de modèle de calcul que vous envisagez, mais si vous êtes mort fixé sur l'équivalence, ceux-ci peuvent être de bons points de départ.