Je me prépare pour une conférence destinée aux étudiants en mathématiques de premier cycle et, dans ce cadre, j’envisage de discuter du concept de décidabilité. Je veux donner un exemple d'un problème que nous ne savons pas actuellement décisif ou indécidable. Il existe de nombreux problèmes de ce...
Si on restreint Turing Machines à une bande finie (c'est-à-dire d'utiliser un espace délimité ), le problème d'arrêt est décidable, essentiellement parce qu'après plusieurs étapes (pouvant être calculées à partir du nombre d'états Q , S et taille de l'alphabet), une configuration doit être...
Je sais qu'il est indécidable de déterminer si un ensemble de tuiles peut carreler l'avion, un résultat de Berger utilisant des tuiles Wang . Ma question est de savoir s'il est également connu d'être indécidable pour déterminer si une seule tuile donnée peut carreler l'avion, un carrelage...
Il est bien connu que le problème d'équivalence est indécidable pour les langages généraux sans contexte. Cependant, toutes les preuves de ce fait que je connais semblent impliquer des grammaires ambiguës sans contexte. Pour cette raison, je voudrais demander si l'on sait si le problème reste...
Je m'intéresse au problème suivant: étant donné les matrices entières décident si chaque produit infini de ces matrices est finalement égal à la matrice zéro.A1,A2,…,AkA1,A2,…,AkA_1,A_2, \ldots, A_k Cela signifie exactement ce que vous pensez qu'il fait: nous dirons que l'ensemble des matrices a la...
C'est un résultat bien connu que la question Une grammaire sans contexte génère-t-elle un langage régulier? est indécidable. Cependant, il devient décidable sur un alphabet unaire, simplement parce que dans ce cas, les classes de langues sans contexte et régulières coïncident. Ma question est de...
Je sais qu'il est impossible de décider de l' équivalence pour le calcul lambda non typé. Citant Barendregt, HP Le calcul lambda: sa syntaxe et sa sémantique. Hollande du Nord, Amsterdam (1984). :ββ\beta Si A et B sont des ensembles de termes lambda disjoints et non vides qui sont fermés sous...
J'essaie de résoudre un problème particulier et j'ai pensé que je pourrais le résoudre en utilisant la théorie des automates. Je me demande, quels modèles d'automates ont un confinement décidable en temps polynomial? c'est-à-dire que si vous avez des machines vous pouvez tester si...
Le problème d'arrêt des machines Turing est peut-être l'ensemble canonique indécidable. Néanmoins, nous prouvons qu'il existe un algorithme qui en décide presque toutes les instances. Le problème de l'arrêt fait donc partie de la collection croissante de ceux qui présentent le phénomène de «trou...
Réponse: inconnue. Les questions posées sont naturelles, ouvertes et apparemment difficiles; la question est maintenant un wiki communautaire. Aperçu La question vise à diviser les langages appartenant à la classe de complexité PPP - ainsi que les machines de Turing de décision (TM) qui acceptent...
Il est connu que de nombreux problèmes de logique (par exemple les problèmes de satisfiabilité de plusieurs logiques modales) ne sont pas décidables. Il existe également de nombreux problèmes indécidables dans la théorie des algorithmes, par exemple dans l'optimisation combinatoire. Mais dans la...
Quelles sont les limites connues de la décidabilité de la comparaison du taux de croissance des fonctions de ? Je pense ici à la décidabilité de questions comme "Est-ce que ?" ou "Est-ce que ?".N→NN→N\mathbb{N} \to \mathbb{N}xx∼2⌊xlg(x+2)⌋xx∼2⌊xlg(x+2)⌋x^x \sim 2^{\lfloor x \lg (x+2)...
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...
Un système d'addition vectorielle (VAS) est un ensemble fini d' actions A⊂ZdA⊂ZdA \subset \mathbb{Z}^d . NdNd\mathbb{N}^d est l'ensemble des marquages . Une course est un mot non vide de marques m0m1…mnm0m1…mnm_0 m_1\dots m_n st ∀i∈{0,…,n−1},mi+1−mi∈A∀i∈{0,…,n−1},mi+1−mi∈A\forall i \in \{0, \dots,...
Réponse: inconnue Un grand merci à tous ceux qui ont contribué à affiner cette question et les définitions qui y sont associées. Les définitions de ce wiki ont fourni le point de départ du plus récent wiki TCS " P contient-il des langues dont l'existence est indépendante de PA ou ZFC? (Wiki...
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 à...
Considérons une grammaire arbitraire sans contexte sur l'alphabet { 0 , 1 , ¯ 0 , ¯ 1 } . Aux productions de cette grammaire, ajoutez deux productions fixes non contextuelles P : ¯ 0 0 → ϵ et ¯ 1 1 → ϵ . Appelons la grammaire résultante G P pour " G augmenté des productions P ".gGG{ 0 , 1 , 0¯¯¯,...
Il y a des problèmes qui sont décidables, il y en a qui sont indécidables, il y a la semi-décidabilité, etc. Dans ce cas, je me demande si un problème peut être méta-indécidable. Cela signifie (du moins dans ma tête) que nous ne pouvons pas dire si c'est décidable ou non. Peut-être qu'il est connu...
Chaque langage indécidable reconnaissable par Turing a-t-il un sous-ensemble NP-complet? La question pourrait être considérée comme une version plus forte du fait que chaque langue infinie reconnaissable par Turing a un sous-ensemble décidable
Si vous avez deux fonctions implémentant un algorithme de tri différent, est-il alors possible de déduire par code source qu'elles ont toutes les deux les mêmes propriétés externes? Cela signifie qu'ils auront tous les deux une séquence non triée possible comme entrée et une séquence triée comme...