La définition de l'ensemble des opérations admissibles utilisées pour le calcul et leurs coûts respectifs. Quelques exemples de modèles incluent les machines de Turing, les fonctions récursives, le calcul lambda et les systèmes de production.
Je lisais récemment sur le calcul Lambda, mais étrangement, je ne trouve pas d'explication expliquant pourquoi il s'appelle "Lambda" ni d'où vient l'expression. Quelqu'un peut-il expliquer les origines du
Je suis un étudiant de premier cycle en CS. Je comprends comment Turing a créé sa machine abstraite (modéliser une personne effectuant un calcul), mais cela me semble être une abstraction maladroite et inélégante. Pourquoi considérons-nous une "bande" et une tête de machine écrivant des symboles,...
Je conviens qu'une machine de Turing peut résoudre "tous les problèmes mathématiques possibles". Mais c’est parce qu’il ne s’agit que d’une représentation machine d’un algorithme: faites ceci en premier, puis faites-le, et enfin en sortie. Je veux dire que tout ce qui peut être résolu peut être...
Dans le calcul quantique, quel est le modèle équivalent d'une machine de Turing? Il est tout à fait clair pour moi que les circuits quantiques puissent être construits à partir de portes quantiques, mais comment pouvons-nous définir une machine de Turing quantique (QTM) pouvant réellement...
En considérant à quel point notre programme doit être convivial pour les multi-threads, mon équipe se demanda si quelque chose ne pouvait absolument pas être fait sur un processeur monocœur. J'ai posé comme principe que le traitement graphique nécessite un traitement extrêmement parallèle, mais ils...
La complexité de l'algorithme est conçue pour être indépendante des détails de niveau inférieur, mais elle est basée sur un modèle impératif, par exemple, l'accès au tableau et la modification d'un nœud dans une arborescence prennent un temps O (1). Ce n'est pas le cas dans les langages...
Classiquement, il y a 3 façons populaires de penser au calcul: la machine de Turing, les circuits et le lambda-calcul (je l'utilise comme un tout pour la plupart des vues fonctionnelles). Tous les trois ont été des moyens fructueux de réfléchir à différents types de problèmes, et différents...
Quelles sont les différences et les relations entre les algorithmes randomisés et les algorithmes non déterministes? De Wikipédia Un algorithme randomisé est un algorithme qui utilise un degré d'aléatoire dans le cadre de sa logique. L'algorithme utilise généralement des bits uniformément...
Voulez-vous améliorer ce post? Fournissez des réponses détaillées à cette question, y compris des citations et une explication de la raison pour laquelle votre réponse est correcte. Les réponses sans suffisamment de détails peuvent être modifiées ou supprimées. J'ai rencontré ci-dessous la...
Wikipédia ainsi que d'autres sources que j'ai trouvées listent le voidtype C comme type d'unité par opposition à un type vide. Je trouve cela déroutant car il me semble que cela voidcorrespond mieux à la définition d'un type vide / bas. Autant voidque je sache , aucune valeur n'habite . Une...
Récemment, dans ma classe CS, j'ai découvert la machine de Turing. Après le cours, j'ai passé plus de 2 heures à essayer de comprendre quelle est la relation entre une bande et une machine. J'ignorais complètement l'existence des bandes d'ordinateurs ou la façon dont les bandes et les machines...
Par recommandation, je republie cela à partir de Stack Overflow . Récemment, j'ai réfléchi au problème suivant. Considérez le code pour un standard "Bonjour tout le monde!" programme: main() { printf("Hello World"); } Maintenant, presque tout changement dans ce code le rendra complètement inutile,...
Lorsque l'on considère les modèles de calcul des machines, la hiérarchie de Chomsky est normalement caractérisée par (dans l'ordre), les automates finis, les automates déroulants, les automates liés linéaires et les machines de Turing. Pour le premier et le dernier niveau 1 (langages réguliers et...
Je cherche des explications sur la façon dont on pourrait prouver que deux modèles de calcul sont équivalents. J'ai lu des livres sur le sujet, sauf que les preuves d'équivalence sont omises. J'ai une idée de base sur ce que cela signifie pour deux modèles de calcul d'être équivalents (la vue des...
J'ai récemment entendu une analogie intéressante qui déclare que la preuve de Turing de l'indécidabilité du problème d'arrêt est très similaire au paradoxe du barbier de Russell. Je me suis donc demandé: les mathématiciens ont finalement réussi à rendre la théorie des ensembles cohérente en passant...
Je sais que les ordinateurs quantiques sont capables de traiter une superposition de tous les états possibles en un seul passage à travers la logique. Cela semble être ce que les gens indiquent comme étant ce qui rend les ordinateurs quantiques spéciaux ou utiles. Cependant, après avoir traité les...
J'ai entendu dire que l' interaction avec la devise était plus puissante que les algorithmes de Peter Wegner . L'idée de base est qu'une machine de Turing (classique) ne peut pas gérer l'interaction, c'est-à-dire la communication (entrée / sortie) avec le monde / l'environnement extérieur. Comment...
Je commence à lire un livre sur la complexité informatique et les machines de Turing. Voici une citation: Un algorithme (c'est-à-dire une machine) peut être représenté comme une chaîne de bits une fois que nous avons décidé d'un codage canonique. Cette affirmation est fournie comme un simple fait,...
Quelles opérations doivent être effectuées pour effectuer un calcul analogique arbitraire ? L'addition, la soustraction, la multiplication et la division seraient-elles suffisantes? De plus, quelqu'un sait-il exactement quels problèmes peuvent être traités avec le calcul analogique, mais pas avec...
Lors du développement d'algorithmes en informatique quantique, j'ai remarqué qu'il existe deux modèles principaux dans lesquels cela se fait. Certains algorithmes - comme pour le problème de l'arbre NAND hamiltonien (Farhi, Goldstone, Guttman) - fonctionnent en concevant un hamiltonien et un état...