Questions marquées «circuits»

18
Est-il possible de tester si un nombre calculable est rationnel ou entier?

Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...

14
L'équivalence eta pour les fonctions est-elle compatible avec l'opération seq de Haskell?

Lemme: En supposant une équivalence éta, nous avons cela (\x -> ⊥) = ⊥ :: A -> B. Preuve: ⊥ = (\x -> ⊥ x)par eta-équivalence, et (\x -> ⊥ x) = (\x -> ⊥)par réduction sous lambda. Le rapport Haskell 2010, section 6.2 spécifie la seqfonction par deux équations: seq :: a -> b -> b...

12
Circuits arithmétiques avec ,

Considérons un circuit qui prend comme nombres d'entrées dans [0,1][0,1][0,1] et a des portes qui se composent des fonctions max(x,y)max(x,y)\max(x, y) , min(x,y)min(x,y)\min(x, y) , 1−x1−x1 - x et x+y2x+y2\frac{x+y}{2} . La sortie du circuit est alors également un nombre en [0,1][0,1][0,1] ....

11
Déterminants et multiplication matricielle - Similitude et différences de complexité algorithmique et de taille des circuits arithmétiques

J'essaie de comprendre la relation entre la complexité algorithmique et la complexité du circuit des déterminants et de la multiplication matricielle. On sait que le déterminant d'unmatrice n × n peut êtrecalculéen temps ˜ O ( M ( n ) ) , où M ( n ) est le temps minimum requis pour multiplier...