Décidabilité des problèmes de décision

Question

Quelqu'un peut-il donner à l'intuition comment répondre à ces questions? D'un côté, je peux dire que la plupart d'entre eux sont indécidables parce que nous pouvons leur réduire le problème de l'arrêt (ou un problème d'arrêt peut apparaître parce que nous ne savons rien à TM afin qu'il puisse se comporter de manière imprévisible, peut simplement boucle sur n'importe quelle contribution) , mais d'une autre main dans la question 2. Nous ne savons pas grand-chose sur la machine, mais je peux hardcore tous les mots dans mon TM en ce qui concerne le langage donné est fini. De plus, pour la question 1. Je suis en mesure de créer TM qui vérifie si la sortie de M est une longueur uniforme (je classerais ce problème comme semi-décidable).

Quels types de problèmes de décision suivants sont les suivants: décidables, en partie décidables, ou même indécidables:

1. Le langage de la machine donnée m ne contient-il que des mots uniques?

2. La machine M donnée accepte-t-elle une taille de langage finie dont est inférieur à 2019?

3. Nous disons que la langue a est sans préfixe si aucun mot appartenant à A est un préfixe de tout autre mot de A. Par exemple, la langue a = {0, 10, 110, 1110, ...} est sans préfixe, tandis que le langage b = { 0, 1, 00, 11, 000, 111, ...} n'a pas cette propriété (par exemple, car 0 est le préfixe 00). Considérez la langue suivante (problème de décision): l = {⟨m⟩ | L (m) est préfixe sans

4. La fonction récursive donnée est-elle une surjection?

5. La fonction récursive donnée est-elle une injection?

6. La machine M s'arrête-t-elle à BB?

7. La machine m accepte-t-elle la langue vide?