Bonjour,
J'ai un problème assez énigmatique à résoudre et j'aimerais avoir votre avis par rapport à ma solution.
Voici le problème:
Est ce que chaque Turing-recognizable set A infini contient un Turing-decidable set B infini?
J'en ai conclu qu'il faut dire si on peut trouver un subset de A tel que tous la machine dont le language consiste en tous les strings de A s'arrête à tous les coups (puisque une Turing decidable veut dire Turing recognizable ET la machine halte).
A mon avis ceci n'est pas vrai puisque il existe certainement un Turing recognizable set qui est infini et qui se compose uniquement de machines qui n'arrive jamais dans l'accept state (elles continuent à tourner).
Donc le problème se résume à prouver que le set de Turing recognizable machines qui ne haltent pas est infini.
Votre opinion?
-----