Turing Donc on peut dire une langue est Turing complete si elle répond à certains critères, et il peut faire quelque chose une autre langue complète peut Turing faire.complet
Est-ce que cela veut dire que je peux théoriquement mettre en œuvre Google en utilisant JavaScript ou Brainf_ck?
Oui, tout ce qu'ils peuvent calculer, vous pouvez le faire dans ces langues. Mais cela ne dit rien sur la quantité de mémoire ou d'autre stockage nécessaire, à quelle vitesse il fonctionnera ou sur la facilité d'écriture ou de débogage.
Nous allons obtenir Chuck Norris pour écrire le code, puis nous pouvons passer le débogueur ... –
Vous pouvez installer Google à partir d'une machine à pile en boîtes d'allumettes et de rochers. Yabba-Dabba-Doo?
Bien sûr, vous pouvez, aussi longtemps que vous avez une bande infinie et de la patience. –
Non, pour des exemples donnés, cela serait impossible. Turing completness est sur la mise en œuvre des algorithmes et de telles choses, il ne vous dira pas si vous ne pouvez implememnt aucun logiciel dedans. Google dépend principalement de ses bases de données que vous ne pouvez pas utiliser directement via JavaScript, ergo no DB == no Google.
Bonne réponse. Le point clé est que Turing Completeness consiste à calculer les réponses aux problèmes. Il ne dit rien sur les E/S, le stockage, les interfaces avec d'autres logiciels, etc. –
Je ne peux pas simplement mettre la DB en mémoire en supposant que j'ai une mémoire infinie? – maniac
@maniac: yup. Bien sûr, on peut se demander si vous avez "implémenté Google", si votre logiciel est différent (et, par exemple, n'utilise pas de base de données) – jalf
Au-delà des questions de performances d'E/S, il y a aussi des questions de temps d'exécution. Le nombre d'étapes nécessaires pour qu'une machine Turing-complete puisse effectuer une tâche peut être plus long de plusieurs centaines de fois que le nombre d'étapes requises pour qu'une autre machine Turing-complete fasse la même chose. Il est donc tout à fait possible qu'une machine puisse achever en une fraction de seconde une tâche qui occuperait une autre machine jusqu'à la fin de l'univers; si cette dernière machine était en quelque sorte autorisée à continuer même après la fin de l'univers, elle pourrait être capable de produire une réponse, mais d'un point de vue pratique, cette dernière serait incapable de résoudre le problème utilement malgré sa complétude.
Je suppose que cela est sur le point d'être bientôt fermé (ceci: http://stackoverflow.com/questions/3689311/stackoverflow-help-needed-closed) a quelque chose à voir avec cette –
Vous ne pouvez mettre en œuvre Google moteur de recherche en travaillant pour Google et en écrivant le code qu'ils utilisent réellement. Tout le reste n'est pas le moteur de recherche Google. Donc, une meilleure question serait de savoir si vous pourriez théoriquement mettre en œuvre * un moteur de recherche * (similaire à celui de Google) dans ces langues. – jalf