Un problème simple dont la décidabilité est inconnue

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 type, mais aucun ne semble être considéré comme un bel exemple à ce jour.

Qu'est-ce qu'un problème simple à décrire dont la décidabilité est ouverte?

Le problème de la mortalité matricielle pour les matrices 2x2. C'est-à-dire, étant donné une liste finie de 2x2 matrices entières M ₁ , ..., M _k , le M _i peut-il être multiplié dans n'importe quel ordre (avec un nombre arbitraire de répétitions) pour produire la matrice tout-0?

(Le cas 3x3 est connu pour être indécidable. Le cas 1x1, bien sûr, est décidable.)

MISE À JOUR: Le problème que j'ai mentionné ici est maintenant connu pour être indécidable! http://arxiv.org/abs/1605.05274 De plus, le journal s’inspire de la lecture de cette réponse. :)

Les programmeurs de votre grand public en mathématiques sont peut-être surpris d'apprendre que la question "ce type est-il implicitement convertible en ce type?" n’est connu pour être décisif dans aucun des Java 5, C 4 et Scala 2.

Pour plus de détails, voir l'article de Andrew Kennedy et Benjamin Pierce "Sur la décidabilité du sous-typage nominal avec variance" . Le document donne quelques exemples de restrictions supplémentaires aux systèmes de types de ces langues, en vertu desquelles le sous-typage nominal devient connu pour être décidable ou pour indécidable.

Fait intéressant, le document a été écrit bien avant l’ajout de C # à la covariance générique et à la contravariance, mais les auteurs ont correctement anticipé la direction prise par le langage. (Ce n'est pas surprenant; les auteurs ont conçu le support sous-jacent à la variance dans le CLR dont j'ai profité pour ajouter de la variance à C #! Ils ont fait le gros du travail.)

Dixième problème de Hilbert concernant les rationnels: "Cette équation polynomiale a-t-elle une solution rationnelle?"

Le problème de la récurrence linéaire avec ses valeurs initiales prend-il la valeur 0?

Deux références:

http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/

http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf

Un problème simple dont la décidabilité est inconnue est le suivant (je pense qu'il est toujours ouvert):

Échecs Infinis :

Entrée : une liste finie de pièces d’échecs et leurs positions de départ sur un échiquier ; Question : White peut-il être un compagnon de force?$Z \times Z$

Si nous ajoutons la contrainte que White doit associer dans mouvements ( n fait partie de l'entrée), alors cela devient décidable: voir Dan Brumleve, Joel David Hamkins et Philipp Schlicht, Le problème de l'infini des échecs infinis est décidable .$n$$n$

Un autre problème simple est le comportement de la fourmi de Langton sur la configuration initiale finie.

Le comportement des fourmis de Langton avec un support fini :

Les carrés d'un avion sont colorés en noir ou en blanc. Nous identifions arbitrairement un carré comme la "fourmi". La fourmi peut voyager dans n'importe laquelle des quatre directions cardinales à chaque étape. La fourmi se déplace selon les règles ci-dessous:

• À un carré blanc, tournez à 90 ° à droite, retournez la couleur du carré, avancez d'une unité
• À un carré noir, tournez à 90 ° à gauche, retournez la couleur du carré, avancez d'une unité

Entrée : une configuration finie (noir / blanc) du plan et de la position de la fourmi;
Question : La fourmi finit-elle toujours par construire une "route" infinie récurrente?

Pour un soutien infini, le problème est indécidable, voir: A. Gajardo, A. Moreira et E. Goles, Complexité de la fourmi de Langton

Collatz Problem est un problème simple à décrire dont la décidabilité est ouverte. Cela implique une simple récurrence des opérations arithmétiques élémentaires.

$f(n)=\mathsf{\{}$ $n/2$$3n+1$

$n_0$

Il est intéressant de noter qu'une généralisation du problème de Collatz s'est avérée indécidable.

Références:

1- PROBLÈMES NON DÉCIDABLES: UN ÉCHANTILLON, BJORN POONEN

2- Weisstein, Eric W. "Problème de Collatz." From MathWorld - Une ressource Web Wolfram.

3- Le problème des 3X + 1: un aperçu , Jeffrey C. Lagarias

On ne sait pas s'il est décidable de déterminer si une forme donnée peut paver le plan .

La décidabilité du confinement des requêtes conjonctives est ouverte depuis plus de vingt ans. Résoudre ce problème constituerait une avancée décisive dans la théorie des bases de données.

$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$

Dans les requêtes conjonctives, on utilise AND pour relier des prédicats existentiellement quantifiés. En termes SQL, les requêtes conjonctives sont les requêtes SELECT-FROM-WHERE utilisant "=" et "AND" mais pas de sous-requêtes ni d'agrégation. Il s’agit peut-être du type de requête de base de données le plus courant et inclut la plupart des requêtes des moteurs de recherche.

$I$$Q_1$$Q_2$

$\ne$

$(N,+,\times)$$(N,+,\times)$

Pour des indications sur la littérature abondante et un traitement rigoureux, consultez le document ToDS (sous presse) de certaines personnes.

$Q$$R$$Q$$Q \text{ AND } R$$Q$

Problème de correspondance de la poste avec un nombre fixe de carreaux compris entre 3 et 6.

Bien que ce ne soit pas vraiment simple à décrire, il possède une description très "ludique", et je la trouve appropriée pour des discussions au niveau de l'intuition.

Le problème de la hauteur d'étoile généralisée: "combien dois-je imbriquer d'étoiles de Kleene pour représenter ce langage normal, avec une expression régulière avec complémentation autorisée?"

Nous ne savons même pas si l'algorithme qui retourne toujours 1 (sauf 0 pour les langues sans étoiles, qui est un cas décisif) est correct.

Un problème de la théorie des automates.

$D$

$x$$D$$x$$x$$L(D) \cap Primes$

Commentaires: J'ai d'abord entendu ce problème d'une réponse stackexchange de Jeffrey Shallit. Si vous connaissez des références, veuillez me le faire savoir. Je vous remercie!

Articles Similaires:

(1) Reste-t-il des problèmes en suspens concernant les DFA?

(2) https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime

Travaux connexes: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf

"Éléments minimaux pour les nombres premiers" de C. Bright, R. Devillers et J. Shallit

Cartes itérées sur l'intervalle (description à partir d' ici ):

(très lié au problème proposé par Magnus Find)

$F$$x$$x$$x$$F(x)$$F(F(x))$$F$$x$$F$

$F$$x$$y$$x$$y$

$F$

$F$$x$$y$$x$$F$

Une référence: Asarin 2011 .

il semble y avoir un moyen / angle assez naturel d’étudier cette question qui est utilisée dans au moins 3 articles comme suit.

$TM(k,l)$$k$$l$$k,l$$k,l$

les résultats peuvent être affichés sur une grille comme dans certaines des références suivantes. dans la région intermédiaire, on sait en fait que certaines machines (non résolues) sont capables de simuler la conjecture de Collatz pour certaines entrées.

par conséquent, il existe clairement un "point de transition" comme un phénomène opérant ici mais pas dans une région calculable mais dans un sens inhabituel entre calculable et non calculable.

• Petites machines de Turing et concours généralisé de castors occupés Michel

• La complexité des petites machines universelles de Turing: une enquête Woods, Neary

• Limites de la solvabilité et de l'insolvabilité dans les systèmes d'étiquettes. Résultats théoriques et expérimentaux De Mol

$2^8$

Également à titre d'exemple de «quasi-accident» ou de «question ouverte résolue relativement récemment comme étant un test complet», la machine Wolfram 2,3 a été prouvée universelle en 2007 pour un prix de 25 000 $ . le concours a été annoncé en mai 2007 et le gagnant, Smith, annoncé en octobre 2007 .

il existe un moyen assez naturel de cartographier la plupart des problèmes en suspens sur des questions de (non) décidabilité. la plupart des problèmes en suspens ne sont généralement pas connus pour être prouvables ou non démontables.

sur le web, il existe une certaine confusion informelle quant à l’indécidabilité du problème P vs NP , qui n’est pas strictement un problème de décision. Par conséquent, parler de son indécidabilité n’est pas techniquement correct. mais, en revanche, il semble exister un lien étroit / naturel entre indécidabilité et prouvabilité comme suit.

par exemple considérer

$L$$x$$O(n^x)$

cette langue est-elle décidable? C’est une question sur un langage dont la décidabilité est ouverte et qui est fondamentalement étroitement liée (même, pratiquement identique) au problème P vs NP et à sa (prouvabilité) inhérente.

Quant à P vs NP comme "simple à décrire", il ne nécessite que les concepts de MT , la notation d'exécution Big O , le non - déterminisme qui sont assez simples (quelques-uns des concepts les plus fondamentaux du TCS) et enseignés au premier cycle ou que lycéen pourrait comprendre.

En fait, NP vs P / Poly est également ouvert et peut être associé de la même manière à une question ouverte sur la décidabilité, ce qui peut être considéré comme un problème assez simple concernant la croissance de circuits minimaux (monotones?) permettant de reconnaître NP complète. problèmes (par exemple, cliques).