Questions marquées «computability»

En lisant l'article An Introduction to the Lambda Calculus , je suis tombé sur un paragraphe que je ne comprenais pas vraiment, à la page 34 (en italique): Dans chacun des deux paradigmes, il existe plusieurs versions de calcul lambda typé. Dans de nombreux systèmes importants, en particulier ceux...

Soit un ensemble non trivial de langages récursivement énumérables ( ) et soit L l'ensemble des encodages des machines Turing qui reconnaissent un langage en C : L = \ {\ langle M \ rangle \ mid L (M) \ in C \}CCC∅⊊C⊊RE∅⊊C⊊RE\emptyset \subsetneq C \subsetneq

Les machines de Turing ont un alphabet de symboles formel, une description basée sur les règles d'état et de transition de la façon dont un calcul est effectué. Le modèle d'acteur est parfois mentionné comme un modèle de calcul plus puissant que les machines de Turing (pas dans ce qu'il peut...

J'aimerais votre aide pour prouver que la langue est décidable ssi .L = { ⟨ M⟩ | L ( M) ∈ N P ∖ P }L={⟨M⟩|L(M)∈NP∖P}L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}P = N PP=NP\mathrm{P}=\mathrm{NP} Si , je comprends que c'est le langage des machines Turing vides....

J'essaie de m'enseigner la théorie de la calculabilité avec un manuel. Selon mon livre, une fonction sur un alphabet n'est calculable que si la langueFFfA = { a , b , c , d, e , f, g, h , i , j , k , l , m , n , o , p ,

Donné n∈Nn∈Nn \in \mathbb{N} et p,q∈N[x1,…,xn]p,q∈N[x1,…,xn]p,q \in \mathbb{N}[x_1,\ldots,x_n] on peut définir la formule suivante dans le langage de l'arithmétique formelle φ(n,p,q)=∀x1⋯∀xn:¬(p(x1,…,xn)=q(x1,…,xn))φ(n,p,q)=∀x1⋯∀xn:¬(p(x1,…,xn)=q(x1,…,xn))\varphi(n,p,q) = \forall x_1 \cdots \forall...

Si vous avez une langue L, sans faire de preuves, existe-t-il un moyen de savoir si elle est reconnaissable ou co-reconnaissable ou décidable? Fondamentalement, tous les conseils ou astuces qui peuvent être utilisés pour le dire. Ou peut-être les modèles communs à rechercher pour savoir de quel...

Notre PC fonctionne-t-il comme machine de Turing? Le modèle d'une machine de Turing se compose d'une bande mémoire infinie, ce qui signifie des états infinis. Mais supposons que si notre PC a 128 Mo de mémoire et 30 Go de disque, il aurait 256 ^ 30128000000 états et donc, il a des états finis. Je...

J'essaie de comprendre (intuitivement) les deux termes «décidabilité» et «vérifiabilité». J'ai fait un nombre raisonnable de recherches et de lecture des différents textes sur lesquels je peux mettre la main. Cependant, leur compréhension intuitive semble m'échapper, spécialement pour le second....

Comme je l'ai étudié, décider de la régularité des langages sans contexte est indécidable. Cependant, nous pouvons tester la régularité en utilisant le théorème de Myhill – Nerode qui fournit une condition nécessaire et suffisante. Le problème devrait donc être décidable. Où est mon...

est-il possible de minimiser les automates de refoulement? Si non, pourquoi? Est-ce parce que pour la minimisation, les classes d'équivalence doivent avoir un indice fini et nous ne pouvons pas le garantir pour

Selon la thèse de Church-Turing, il est impossible de concevoir un algorithme pour décider du problème d'arrêt. Le mot algorithme dans ce contexte inclut-il ou non l'intelligence artificielle, c'est-à-dire que la thèse de Church-Turing s'applique-t-elle également à l'intelligence artificielle?...

Par exemple, nous pouvons dire que nous avons un programme abstrait qui, étant donné une chaîne binaire finie en entrée, supprime tous les zéros (c'est-à-dire que 0010001101011 est évalué à 111111), ce qui est certainement une fonction calculable par Turing. Comment un système de balises cycliques...

Je veux déterminer si ce problème de décision est décidable. J'ai essayé d'établir des réductions à partir de Halt et "Accepte une chaîne vide", mais je n'ai pas encore trouvé de solution. Est-ce que quelqu'un peut

À ma connaissance, l'arrêt du problème demande s'il existe un programme qui décide si un programme en cours de test, compte tenu de certaines données d'entrée (quel que soit le programme ou quelles données d'entrée nous donnons) se terminera ou non. La réponse à ce problème est «non». En d'autres...

Si F: N → Nf:N→Nf:\mathbb{N}\rightarrow\mathbb{N} est calculable et a un inverse, dans quelles conditions est F- 1f−1f^{-1}aussi calculable? Je ne pouvais pas trouver cela dans un manuel, et googler obtient de vagues suggestions sur le bijectif, mais je n'ai pas pu trouver un théorème clairement...

Existe-t-il des problèmes dont la décidabilité est inconnue, mais il est certain que les problèmes sont moins difficiles que le problème

Quand je lis à propos de la thèse de Church-Turing, il semble être une affirmation courante que «la réalité physique est calculable par Turing». Quelle est la base de cette réclamation? Y a-t-il des résultats théoriques dans ce sens? Pour le contexte, je suis un chercheur qui travaille sur des...

Considérez les termes construits à partir d'éléments de QQ\mathbb Q et les opérations + , × , - , /+,×,−,/+,\times,-,/, et ⋅--√n⋅n\sqrt[n]{\,\cdot\,} pour chaque nombre naturel nnn. Étant donné la promesse que deux termes sont bien formés - c'est-à-dire qu'il n'y a pas de division par zéro et même...

La théorie des domaines donne une théorie étonnante de calculabilité en présence de types simples. Mais lorsque le polymorphisme paramétrique est ajouté, il ne semble pas y avoir une bonne théorie qui explique ce qui se passe aussi bien que la théorie des domaines explique le calcul sur des types...