Théorie de la calculabilité aka théorie de la récursivité.
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...
Désolé pour le titre accrocheur. Je veux comprendre, que doit-on faire pour réfuter la thèse de Church-Turing? Quelque part j'ai lu c'est mathématiquement impossible de le faire! Pourquoi? Turing, Rosser, etc. ont utilisé différents termes pour distinguer entre "ce qui peut être calculé" et "ce qui...
Existe-t-il une relation entre la machine de Turing et le calcul Lambda - ou est-ce qu'ils se sont produits à peu près au même
J'ai trois sous-questions liées, qui sont soulignées par des points dans la liste ci-dessous (non, elles ne pourraient pas être divisées, si vous vous le demandez). Andrej Bauer a écrit ici que certaines fonctions sont réalisables avec une machine de Turing, mais pas avec le lambda-calcul. Une...
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 crois comprendre que le modèle de Turing est devenu le "standard" dans la description du calcul. Je voudrais savoir pourquoi. Si le modèle TM est devenu plus largement utilisé que d’autres modèles théoriquement équivalents (à ma connaissance), comme le μ-récursion de Kleene ou le calcul lambda...
Toute fonction calculable en temps t sur une machine de Turing à bande unique utilisant un alphabet de taille k = O ( 1 ) peut-elle être calculée en temps O ( t ) sur une seule bande machine de Turing en utilisant un alphabet de taille 3 ( par exemple, 0 , 1 , et en blanc)?F: { 0 , 1 }*→ { 0 , 1...
C'est une question liée à celle-ci . En le reformulant sous une forme beaucoup plus simple après de nombreuses discussions, la question semblait totalement différente. La preuve classique de l’indécidabilité du problème posé consiste à démontrer une contradiction lorsqu’on essaie d’appliquer à...
Je cherche une réponse définitive à la question de savoir si la génération de nombres "réellement aléatoires" est calculable par Turing. Je ne sais pas comment formuler cela avec précision. Cette question de StackExchange sur les "algorithmes efficaces pour la génération de nombres aléatoires" est...
J'ai récemment entendu ceci: "Une machine non déterministe n'est pas la même chose qu'une machine probabiliste. En gros, une machine non déterministe est une machine probabiliste dans laquelle les probabilités de transitions ne sont pas connues". Je me sens comme si je comprends le point mais je...
Paul Wegner et Dina Goldin publient depuis plus de 10 ans des articles et des livres dans lesquels ils affirment principalement que la thèse de Church-Turing est souvent mal représentée dans la communauté CS Theory et ailleurs. Autrement dit, il est présenté comme englobant tout le calcul, alors...
La complexité croissante des programmes informatiques et la position de plus en plus cruciale des ordinateurs dans notre société me laissent nous demander pourquoi nous n'utilisons toujours pas collectivement des langages de programmation dans lesquels vous devez prouver formellement que votre code...
J'ai suivi un cours une fois sur la calculabilité et la logique. Le matériel comprenait une corrélation entre les classes de complexité / calculabilité (R, RE, co-RE, P, NP, Logspace, ...) et la logique (Calcul de prédicats, logique du premier ordre, ...). La corrélation comprenait plusieurs...
Il est impossible d'écrire un langage de programmation qui autorise toutes les machines qui s'arrêtent sur toutes les entrées et aucune autre. Cependant, il semble facile de définir un tel langage de programmation pour n'importe quelle classe de complexité standard. En particulier, nous pouvons...
Je veux encoder une simple machine de Turing dans les règles d'un jeu de cartes. Je voudrais en faire une machine de Turing universelle afin de prouver l'exhaustivité de Turing. Jusqu'à présent, j'ai créé un état de jeu qui code pour la machine de Turing à 2 états et 3 symboles d'Alex Smith ....
Un ordinateur doté d'un flux infini de bits vraiment aléatoires est plus puissant qu'un ordinateur sans un. La question est: est-elle suffisamment puissante pour résoudre le problème de l'arrêt? Autrement dit, un ordinateur probabiliste peut-il déterminer si un programme déterministe s'arrête ou...
Existe-t-il des langages de programmation (fonctionnels?) Où toutes les fonctions ont une forme canonique? C'est-à-dire que deux fonctions qui renvoient les mêmes valeurs pour tout l'ensemble d'entrée sont représentées de la même manière, par exemple si f (x) a renvoyé x + 1, et g (x) a renvoyé x +...
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...
Dans cet article de wikipedia sur l'exhaustivité de Turing, il déclare que: Le calcul lambda non typé est Turing complet, mais de nombreux calculs lambda typés, y compris le système F, ne le sont pas. La valeur des systèmes dactylographiés est basée sur leur capacité à représenter la plupart des...
Si nous nous en remettons au livre (ou à toute autre version de la spécification du langage si vous préférez), quelle puissance de calcul une implémentation C peut-elle avoir? Notez que «implémentation C» a une signification technique: il s'agit d'une instanciation particulière de la spécification...