0

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?

Raton
  • 729
  • 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. – John Hughes Mar 09 '18 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? – Raton Mar 09 '18 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. – John Hughes Mar 09 '18 at 23:09
  • @John fair..... – Raton Mar 09 '18 at 23:11

1 Answers1

4

The condition in a) is satisfied by a TM that halts immediately and doesn't accept anything.

The condition in b) is satisfied by a TM that halts immediately and accepts everything.

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.