Est $ nhalt $ indécitable même si $ m $ s'arrête en entrée $ W $ en pas fini

Question

Si nous avons la langue

$ nhalt={; $ $ m $ s'arrêteEntrée $ w $ en moins de $ n $ étapes $\} $

Cette langue est-elle également indéchoire de la même manière que $ HALT $ est indécitable?Et si oui, $ nhalt \ notin p $ , non?

Answer 1

Ce langage est évidemment décritable, il suffit d'émuler $ m $ sur $ w $ et voyez si ellearrêté dans N $ N $ ÉTAPES OU PAS ...

maintenant, à savoir si $ nhalt \ in p $ ou $ nhalt \ notin p $ .La longueur de $ N $ est logarithmique à sa "valeur" (en supposant que $ \ sigma $ icin'est pas unaire).Ainsi, le nombre d'étapes que nous devrons émuler serait exponentielle de sa taille!Je ne vois pas d'algorithme de temps polynomial pour cela, donc je suppose que ce n'est probablement pas dans p .Mais je n'ai pas prouvé que (je viens de donner de l'intuition sur la raison pour laquelle cela pourrait être le cas) et il y a aussi une chance que montrant cela équivaut à un problème ouvert (peut-être que vous pourriez prouver sa $ \ mathcal {np-complet} $ ?)