Étant donné un programme et les entrées pour celui-ci, est-ce qu'il s'arrête ou s'exécute pour toujours?
On sait que certains problèmes sont indécidables, mais il est néanmoins possible de progresser dans leur résolution. Par exemple, le problème d'arrêt est indécidable, mais des progrès pratiques peuvent être réalisés dans la création d'outils permettant de détecter les boucles infinies potentielles...
Je sais que le problème de l'arrêt est indécidable en général, mais il y a certaines machines Turing qui s'arrêtent évidemment et d'autres qui ne le sont évidemment pas. De toutes les machines de turing possibles, quelle est la plus petite où personne n'a de preuve qu'elle s'arrête ou...
On sait qu'avec un ensemble dénombrable d'algorithmes (caractérisés par un nombre de Gödel), nous ne pouvons pas calculer (construire un algorithme binaire qui vérifie l'appartenance) tous les sous-ensembles de N. Une preuve pourrait être résumée comme suit: si nous le pouvions, alors l'ensemble de...
Je me demandais s'il y avait une bonne bibliographie des tentatives d'enquêter sur la conjecture de Collatz comme grammaire formelle? (ou toute autre tentative dans la communauté CS pour faire face à cette classe de phénomènes génératifs et leurs propriétés
Je cherche à obtenir une réponse définitive à la question du titre. Existe-t-il un ensemble de règles qui traduisent un programme en une configuration de pièces finies sur un plateau infini, de sorte que si le noir et blanc ne joue que des mouvements légaux, le jeu se termine en temps fini si le...
Je m'intéresse au problème "le plus proche" (et "le plus complexe") de la conjecture de Collatz qui a été résolue avec succès (ce que Erdos a dit fameusement "les mathématiques ne sont pas encore mûres pour de tels problèmes"). Il a été prouvé qu'une classe de problèmes "de type Collatz" est...
Existe-t-il une machine de Turing qui peut décider si presque toutes les autres machines de Turing s'arrêtent? N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\| \cdot \| f(i)=∥{n:Mi can't decide whether Mn halts}∥.f(i)=‖{n:Mi can't decide whether Mn halts}‖.f(i) = \|\{n: M_i \text{ can't decide...
La théorie des types constructifs avec son interprétation de base sous la correspondance de curry howard consiste uniquement en fonctions calculables totales. Dans la littérature, certains ont dit que l'utilisation de la "théorie du type informatique" pour représenter la non-terminaison dans les...
Étant donné que les deux preuves utilisent l'argument diagonal, je me demande s'il existe un lien obscur entre l'existence d'ensembles infinis innombrables et l'indécidabilité du problème d'arrêt. Le problème d'arrêt serait-il décidable si tous les ensembles étaient
J'ai une question naïve: existe-t-il une machine de Turing dont la terminaison est vraie mais non démontrable par aucune théorie naturelle, cohérente et finement axiomatisable? Je demande une simple preuve d'existence plutôt qu'un exemple spécifique. Cela pourrait avoir un lien avec l'analyse...