Efficient algorithms for checking non-emptiness of the language of a Turing machine I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?
The problem is undecidable. There are no algorithms for it, so there are no efficient algorithms.