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 à...
Quelqu'un connaît-il un ensemble de problèmes qui varient uniformément et qui couvrent l'une des hiérarchies "intéressantes" de complexité et de calculabilité? Par intéressant, je veux dire, par exemple, la hiérarchie polynomiale, la hiérarchie arithmétique ou la hiérarchie analytique. Ou peut-être...
Question : La prévision (telle que définie ci-dessous) de séquences calculables est-elle aussi difficile que le problème d'arrêt? Elaboration : "Prédire" signifie prédire avec succès, ce qui signifie ne faire que de nombreuses erreurs sur la tâche d'essayer de prédire le n-ième bit de la séquence...
Harvey Friedman a montré qu'il existe un résultat net précis qui ne peut pas être prouvé en ZFC (la théorie des ensembles de Zermelo-Frankel habituelle avec l'Axiom of Choice). De nombreuses logiques modernes sont construites sur des opérateurs à virgule fixe, alors je me demandais: y a-t-il des...
J'ai souvent entendu dire que vous ne pouvez pas écrire un programme pour détecter les bogues dans un navigateur Web, un traitement de texte ou un système d'exploitation, à cause du théorème de Rice: toute propriété sémantique pour un langage complet de Turing est indécidable. Cependant, je ne sais...
Cette question est de savoir s'il existe des tarpits de Turing réversibles connus, où "réversible" signifie au sens d' Axelsen et de Glück , et "tarpit" est un concept beaucoup plus informel (et pourrait ne pas être un très bon choix de mot), mais je ferai de mon mieux pour expliquer ce que je veux...
Les problèmes ont été, dans leur ensemble, classés, grâce à la complexité informatique. Mais, dans les équations différentielles, est-il possible de classer les équations différentielles en fonction de leur structure de calcul? Par exemple, si une équation non homogène du premier ordre est...
Soit HA L TnHALTnHALT_n la chaîne de longueur 2n2n2^n correspondant à la table de vérité du problème d'arrêt pour les entrées de longueur nnn . Si la séquence des complexités de Kolmogorov K( HA L Tn)K(HALTn)K(HALT_n) était O ( 1 )O(1)O(1) , alors l'une des chaînes de conseil serait utilisée...
Considérez le jeu à 2 joueurs suivant: La nature choisit au hasard un programme Chaque joueur joue un nombre en [0, infini] inclus en réponse au mouvement de la nature Prenez le minimum de numéros de joueurs et exécutez le programme pour (jusqu'à) autant d'étapes (sauf si les deux joueurs ont...
Existe-t-il une notion de calculabilité sur des ensembles autres que les nombres naturels? Par souci d'argument, disons sur les ensembles qui se bijectent avec .NSSSNN\mathbb{N} Il est tentant de dire "oui, ce sont ces fonctions de la forme où est toute bijection et est toute fonction calculable "....
Fermé. Cette question est hors sujet . Il n'accepte pas actuellement les réponses. Vous souhaitez améliorer cette question? Mettez à jour la question afin qu'elle soit sur le sujet pour l'échange théorique de pile informatique. Fermé il y a 3 ans . Existe-t-il une courte construction explicite...
D'après mon expérience, les langages contextuels et les automates linéaires bornés sont souvent ignorés ou ignorés dans les cours de théorie de la calculabilité, et sont même exclus de certains manuels remarquables, bien que les automates finis et déroulants reçoivent beaucoup d'attention. Il doit...
Les ordinateurs quantiques et les ordinateurs à ADN sont des exemples bien connus de calcul inspiré par des phénomènes naturels. Que sait-on du potentiel et / ou des limites de l'informatique avec les lois ou la gravité de Maxwell? Autrement dit, incorporer les solutions «rapides» de la nature aux...
J'ai une question, dont la réponse est probablement bien connue, mais je n'arrive pas à trouver quoi que ce soit de significatif après un peu de recherche, donc j'apprécierais de l'aide. Ma question est de savoir si l'on sait que décider si un nombre est transcendantal est indécidable....
Supposons que nous ne connaissions pas le résultat de Joe B. Wells de 1994 selon lequel la typabilité et la vérification de type sont indécidables dans le système F (AKA ). Dans les calculs Lambda avec types de Barendregt (1992), j'ai trouvé une preuve due à Malecki 1989 que la vérification de type...
Intrigué par la question intéressante de Chris Pressey sur les fonctions élémentaires-récursives , j'explorais davantage et je n'arrivais pas à trouver une réponse à cette question sur le web. Les fonctions récursives élémentaires correspondent bien à la hiérarchie exponentielle, .DTIME ( 2n) ∪...
J'ai rencontré la question suivante, qui est un exercice facile (spoiler ci-dessous). On nous donne instances du problème d'arrêt (ie TMs ), et nous devons décider exactement lequel s'arrêtera sur . Autrement dit, nous devons afficher . On nous donne un oracle pour le problème d'arrêt, mais nous...
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...
Existe-t-il un système similaire au calcul lambda à forte normalisation, sans qu'il soit nécessaire d'ajouter un système de type
Le fœtus, si vous n'en avez pas entendu parler, peut être lu ici . Il utilise un système de «matrices d'appel» et de «graphiques d'appel» pour trouver tous les «comportements de récursivité» des appels récursifs dans une fonction. Pour montrer qu'une fonction se termine, cela montre que tous les...