0

Is it true that every Turing machine $M$ will have at least 1 language $L$ such that $M$ decides $L$?

I have been toiling really hard and I have still not found a Turing machine that will decide zero language. So, I just assumed it to be true.

Derek Allums
  • 3,121
Smit Patel
  • 3

1 Answers1

0

Every Turing Machine has exactly one language that it accepts, yes. No more and no less, namely the language consisting of all the words that it accepts.

Do you mean the empty language, when you say zero language? How to accept it depends a bit on the exact definition of TM that you are using. But any machine without an accepting state, for example, cannot accept any word. So its language is empty.

Peter Leupold
  • 1,220
  • Yes, empty language. So, what I'm trying to prove is that "for every Turing machine M, there exists a language l such that M decides L", so I didn't know how to approach the proof? any help – Smit Patel Nov 17 '21 at 09:47
  • But this holds by definition. Every TM accepts the language consisting of all the words it accepts. There is nothing to prove. Or do you mean by 'decide' something like 'halt on every input'? Then this is not true for TMs which accept undecidable but enumerable languages. – Peter Leupold Nov 17 '21 at 09:53
  • gotcha! Thank you, you were really helpful!! – Smit Patel Nov 17 '21 at 10:27