Question

Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear because we don't know about given TM anything so it can behave unpredictably, can simply loop on any input), but on another hand in question 2. we don't know much about machine, however I can hardcore all words into my TM as far as given language is finite. Also, for question 1. I'm able to create TM which checks if the output of M is even-length (I would classify this problem as semi-decidable).

What type of the following decision problems are: decidable, partly decidable, or even undecidable:

  1. Does the language of the given machine M contain only even-length words?

  2. Does the given M machine accept a finite language size of which is less than 2019?

  3. We say that language A is prefixless if no word belonging to A is a prefix of any other word from A. For example, language A = {0, 10, 110, 1110, ...} is prefixless, while language B = {0, 1, 00, 11, 000, 111, ...} does not have this property (for example, because 0 is the prefix 00). Consider the following language (decision problem): L = {⟨M⟩ | L (M) is prefixless}.

  4. Is the given recursive function a surjection?

  5. Is the given recursive function an injection?

  6. Does the machine M stop at bb?

  7. Does the machine M accept the empty language?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top