si on peut calculer length, on peut résoudre le problème de l’arrêt
Euh, vraiment ? Ça suffit ?
Oui. Tu peux facilement créer une liste de toutes les instructions effectuées pour une machine de Turing donnée (en terminant la liste quand la machine s’arrête, en ayant une liste infinie, par construction, sinon). Trivialement, une méthode qui te dit si ta liste est infinie ou non (c’est à dire un length dans N∪{∞}) résout le problème de l’arrêt.
[^] # Re: C++ std::future
Posté par neil . En réponse à la dépêche Sortie du livre « Parallel and Concurrent Programming in Haskell ». Évalué à 2. Dernière modification le 29 juillet 2013 à 19:00.
Oui. Tu peux facilement créer une liste de toutes les instructions effectuées pour une machine de Turing donnée (en terminant la liste quand la machine s’arrête, en ayant une liste infinie, par construction, sinon). Trivialement, une méthode qui te dit si ta liste est infinie ou non (c’est à dire un
lengthdans N∪{∞}) résout le problème de l’arrêt.