Questions marquées «decidability»

92
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...

12
Théorie décidable de la croissance asymptotique

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)...

11
Nombres naturels non comparables

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 à...