La thèse de Church-Turing déclare que tout ce qui peut être physiquement calculé, peut être calculé sur une machine de Turing. L'article «Analog computation via neural networks» (Siegelmannn et Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) affirme qu'un réseau neuronal d'une...
C'est une question naïve et, par conséquent, peut-être malformée, donc excuses à l'avance! À mon avis, une machine de Turing peut être considérée comme la base de calcul des langages de programmation procéduraux / impératifs. De même, le lambda calcul est le fondement des langages de programmation...
Il y a beaucoup (et je veux dire beaucoup) de langues dénombrables qui sont décidables par Turing. Est-ce qu'une langue innombrable peut être décidable de
Il existe des temps spatiaux relativistes (par exemple des temps spatiaux MH; voir Hogarth 1994) où une ligne du monde de durée infinie peut être contenue dans le passé d'un observateur fini. Cela signifie qu'un observateur normal peut avoir accès à un nombre infini d'étapes de calcul. En supposant...
Si nous avons un programme informatique arbitraire qui peut modifier ses instructions, est-il possible de simuler ce programme avec un programme qui ne peut pas modifier ses instructions? Éditer: Je suis nouveau sur stackexchange, donc je ne sais pas si je suis autorisé à poser une NOUVELLE...
J'ai vu des sites Web qui prétendent «prouver» que HTML5 + CSS est Turing Complete. J'ai vu des sites Web qui prétendent «prouver» que SQL est Turing Complete. J'ai vu un tas de sites Web qui prétendent «expliquer» ce que signifie être Turing Complete. Assez! Où puis-je trouver un livre (écrit par...
J'aimerais citer Nielsen & Chuang, Quantum Computation and Quantum Information, édition du 10e anniversaire, page 5 (c'est moi qui souligne): Une classe de défis à la forte thèse de Church-Turing vient du domaine du calcul analogique. Au cours des années qui se sont écoulées depuis Turing, de...
Selon la thèse de Church-Turing, il est impossible de concevoir un algorithme pour décider du problème d'arrêt. Le mot algorithme dans ce contexte inclut-il ou non l'intelligence artificielle, c'est-à-dire que la thèse de Church-Turing s'applique-t-elle également à l'intelligence artificielle?...
Quand je lis à propos de la thèse de Church-Turing, il semble être une affirmation courante que «la réalité physique est calculable par Turing». Quelle est la base de cette réclamation? Y a-t-il des résultats théoriques dans ce sens? Pour le contexte, je suis un chercheur qui travaille sur des...
Tout d'abord, je m'excuse si cela a été demandé, mais je n'ai vraiment rien trouvé. Je suis tombé sur cet article . Il indique qu'il existe un problème que seuls les ordinateurs quantiques peuvent résoudre. À ma connaissance, cela devrait signifier, intuitivement, que ce problème est "effectivement...