Deux documents que j'inclus sont: D. Kozen, "Indexation des classes subrécursives" , STOC, 1978. R. Ladner, «Sur la structure de la réductibilité du temps polynomial» , JACM, 1975.
Si je comprends bien, une preuve que P = NP ou P ≠ NP devrait être non relativisable (comme dans les oracles de la théorie de la récursivité). Cependant, presque toutes les preuves semblent être relativisables. Quels sont les bons exemples de preuves non relativisables, du type d'une preuve P = NP...
La manière habituelle de prouver l'indécidabilité est la réduction d'un problème RE-complet tel que le problème d'arrêt, la validité dans la logique du premier ordre, la satisfiabilité des équations diophantiennes, etc. Il est connu qu'il y a des problèmes récursivement énumérables, mais...
Est-il possible de construire une implémentation mécanique à but unique (non complète de Turing) de, disons, Microsoft Word? Est-il possible d'implémenter des choses comme les itérateurs, les fonctions de premier ordre, toute la gamme des techniques de programmation? Les engrenages et autres pièces...
Si est l'ensemble des temps d'arrêt des machines de Turing à n états sur un alphabet binaire avec une bande initiale vide, alors B B ( n ) = max H T ( n ) .HT(n)HT(n)HT(n)nnnBB(n)=maxHT(n)BB(n)=maxHT(n)BB(n) = \max HT(n) Que dire du deuxième plus grand nombre de ? Appelez cela B B 2 ( n )...
Il est bien connu que le problème d'arrêt n'est pas calculable. Cependant, il est possible de "compresser" exponentiellement des informations sur le problème d'arrêt, de sorte que sa décompression soit calculable. Plus précisément, il est possible de calculer à partir d'une description de machines...
C'est probablement assez simple, mais considérez le problème standard de correspondance par correspondance: Étant donné et , trouvez une séquence d'indices tels que . C'est, bien sûr, indécidable.β 1 , … , β N i 1 , … , i K α i 1 ⋯ α i K = β i 1 ⋯ β i Kα1,…,αNα1,…,αN\alpha_1, \ldots,...
J'ai essayé d'enrouler ma tête autour du quoi, pourquoi et comment du -calculus mais je ne suis pas parvenu à comprendre "pourquoi ça marche"?λλ\lambda «Intuitivement», j'obtiens le modèle de calculabilité de Turing Machines (TM). Mais cette -abstraction me laisse juste perplexe.λλ\lambda Supposons...
Quel est le modèle de calcul le plus simple pour lequel le problème de vide est indécidable? Le problème de vide pour un modèle de calcul (par exemple automate à états finis, automate à poussée alternée, automate quantique à erreurs bornées avec compteur, LBA déterministe, etc.) est de déterminer...
Nous pouvons considérer la complexité de Kolmogorov d'une chaîne xxx comme la longueur du programme le plus court PPP et saisir yyy tel que x=P(y)x=P(y)x = P(y) . Habituellement, ces programmes sont tirés d'un ensemble complet de Turing (comme PPP pourrait être la description d'une machine de...
Le papier Lauri Hella et José María Turull-Torres, Requêtes informatiques avec des logiques d'ordre supérieur , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 propose une logique VO, une logique d'ordre variable. Cela permet de quantifier les commandes sur les variables. VO est assez...
Soit la de -terms définie comme suit:λs i zesizesizeλλ\lambda s i ze ( x ) = 1size(x)=1size(x) = 1 , s i ze ( λ x . t ) = s i ze ( t ) + 1size(λx.t)=size(t)+1size(λx.t) = size(t) + 1 , s i ze ( t s ) = s i ze ( t ) + s i ze ( s ) + 1size(ts)=size(t)+size(s)+1size(t s) = size(t) + size(s) + 1 . Soit...
Il est généralement plus simple de raisonner sur le calcul où la limitation est la finitude du calcul plutôt qu'un seuil comme "calculable en temps polynomial". Dans la théorie des langages formels par exemple, plutôt d'utiliser le ∃n.xn+1=xn∃n.xn+1=xn\exists n. x^{n+1} = x^n pour caractériser le...
Existe-t-il des problèmes décidables tels que pour aucun algorithme qui résout le problème, nous pouvons donner une limite de temps en fonction de la longueur n de l'instance d'entrée? Je suis arrivé à cette question parce que je pensais à ce qui suit: Supposons que nous ayons un problème...
Existe-t-il un moyen documenté de calculer les nœuds? (circonférences incrustées dans un espace euclidien tridimensionnel). Je veux dire, un type de données pour les représenter, et un algorithme pour déterminer si deux instances du type de données représentent le même nœud. Si la réponse est...
Comme nous le savons, la définition de la complexité de calcul de l'algorithme est presque sans controverse, mais la définition de la complexité de calcul des réels ou des modèles de calcul sur les réels n'est pas dans un tel cas. Nous connaissons le modèle et le modèle de Blum et Smales dans le...
Le problème suivant est décidable: Étant donné une grammaire sans contexte , L ( G ) = ∅ ?GGGL ( G ) = ∅L(G)=∅L(G) = \varnothing Le problème suivant est indécidable: Étant donné une grammaire sans contexte , L ( G ) = A ∗ ?gGGL ( G ) = A∗L(G)=A∗L(G) = A^{\ast} Existe-t-il une caractérisation des...
Est-il possible de construire un algorithme qui prend en entrée un automate de refoulement avec la promesse que le langage accepté par cet automate L ( M ) est un langage déterministe sans contexte et génère un automate de refoulement déterministe N qui accepte précisément le langage accepté par M...
Je sais que la question "est-ce qu'une formule de premier ordre a un modèle" est indécidable en général.ϕϕ\phi Quelqu'un pourrait-il me donner un lien ou un livre qui donnerait la réponse pour les modèles finis. Si j'ai une formule de premier ordre , est-il possible de déterminer si ϕ a un modèle...
Le "nom du jeu le plus grand nombre" demande à deux joueurs d'écrire un numéro secrètement, et le gagnant est la personne qui a écrit le plus grand nombre. Le jeu permet généralement aux joueurs d'écrire des fonctions évaluées à un moment donné, donc serait également une chose acceptable à...