La définition principale de la machine de Turing (TM), au moins dans mon propre manuel de référence (Hopcroft + Ullman 1979) est déterministe. Par conséquent, ma propre compréhension du problème de l' arrêt concerne principalement la MT déterministe, bien que je sache qu'il peut être envisagé pour...
J'ai lu dans Wikipedia et dans quelques autres textes Le problème d'arrêt est décidable [...] pour les automates linéaires bornés (LBA) et les machines déterministes à mémoire finie. Mais plus tôt, il est écrit que le problème d'arrêt est un problème indécidable et donc TM ne peut pas le résoudre!...
J'avais l'impression que nos ordinateurs, étant finis, ne sont finalement pas plus puissants que les machines à états finis (extraordinairement grandes). Cependant, les machines de Turing linéairement délimitées sont également finies, mais il semble que les langues régulières soient strictement un...