For any arbitrary Turing machine, it will always decide a specific language $L$?

38 Views Asked by At

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.

1

There are 1 best solutions below

3
On BEST ANSWER

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.