L'informatique

9
Version constructive de la décidabilité?

Aujourd'hui au déjeuner, j'ai abordé cette question avec mes collègues, et à ma grande surprise, l'argument de Jeff E. selon lequel le problème est décidable ne les a pas convaincus ( voici un article étroitement lié sur mathoverflow). Une déclaration de problème plus facile à expliquer ("est P =...

9
Pouvons-nous trouver k les chemins les plus courts entre toutes les paires plus rapidement que de résoudre le problème par paire à plusieurs reprises?

Je veux produire chemin le plus court ( k serait inférieur à 10) entre toutes les paires dans un graphique. Le graphique est (en fait une carte de métro):kkkkkk pondéré positivement non dirigé clairsemé avec environ 100 nœuds Mon plan actuel consiste à appliquer routage de chemin le plus courtkkk à...

9
Pourquoi l'état reste-t-il inchangé dans la sémantique opérationnelle à petite étape d'une boucle while?

Habituellement, je vois que dans la représentation sémantique opérationnelle structurelle pour la boucle while, l'état du programme ne change pas: ( W h i l eBréoS, σ) → ( i fBt h e nS; ( W h i l eBréoS)e l s eSKjeP, σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma)...

9
Pour toute langue

J'essaie de trouver une preuve pour les éléments suivants: Pour toute langue AAA , il existe un langage BBB tel que A≤TBA≤TBA \le_{\mathrm{T}} B , mais B ≰TA≰TA\nleq_{\mathrm{T}} A . Je pensais laisser BBB être ATMATMA_{\mathrm{TM}} , mais je me rends compte que toutes les langues ne sont pas...

9
La constante de Chaitin est normale?

Selon cette source, la constante de Chaitin ΩΩ\Omega Est normal. Chaque probabilité d'arrêt est un nombre réel normal et transcendantal qui n'est pas calculable, ce qui signifie qu'il n'y a pas d'algorithme pour calculer ses chiffres. En effet, chaque probabilité d'arrêt est aléatoire de...

9
Qu'est-ce qu'un fichier?

Je cherche une définition formelle de fichier qui n'inclut pas seulement le stockage mais aussi des abstractions comme procfs ou / dev / null (ou tout fichier basé sur un fusible) qui ne se rapportent pas au stockage. Jusqu'à présent, je sais que tous les fichiers sont des abstractions Peut être...

9
Calcul efficace du plus petit entier avec n diviseurs

Afin de résoudre ce problème, j'ai d'abord observé que ϕ(pe11 pe22⋯ pekk)=(e1+1)(e2+1)⋯(ek+1)ϕ(p1e1 p2e2⋯ pkek)=(e1+1)(e2+1)⋯(ek+1)\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1) Où est le nombre de diviseurs (pas nécessairement premiers) de . Si est le...