# Turing machine for any language

I am trying to prove that for any language over an alphabet there is a

a) Turing machine which halts on all inputs and if it accepts a string, then it is in our language $L$

b) There is a Turing machine which halts on all inputs and if it rejects a string, then the string is not in our language $L$

c) There is a Turing machine which if it accepts a string, then it is in our language $L$ and if it rejects a string then the string is not in $L$

Here are my thoughts:

For a) I am thinking that our Turing machine can have a pathway for every string in the language and accept and clear when it reaches the end of any string in the language. Otherwise it rejects. I can't think of a canonical way to formulate this machine for any language though. Any tips?

Also I know that b) is the complement of a) and c) is a decider that can loop. Are there any canonical ways to come up with a decider for a language?

• Your solution for "a" can't be right; "a" asks that the machine halts on all inputs, but you've got it looping for inputs not in the language. Commented Mar 9, 2018 at 23:00
• @John Ok so what would a canonical TM look like which rejects on all strings not in the language and accepts on all strings in the language? Commented Mar 9, 2018 at 23:02
• I have no idea --- this really isn't my area of expertise. But I know enough to know that what you wrote was inconsistent with what was required. Commented Mar 9, 2018 at 23:09
• @John fair..... Commented Mar 9, 2018 at 23:11

As for c), if 'reject' means 'halts but does not accept', then a TM that doesn't halt on any input will suffice. If 'reject' means 'halts but does not accept, or does not halt at all', then such a TM must accept a word if and only if it is in $L$. This is impossible:
If, given a language $L$, such a Turing machine $M_L$ can always be found, then by definition $L$ is the language accepted by $M_L$. There are only countably many Turing machines, but uncountably many languages over any given alphabet, so there exist some languages that are not accepted by any Turing machine.