0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Commented Mar 9, 2018 at 23:00
  • $\begingroup$ @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? $\endgroup$
    – Raton
    Commented Mar 9, 2018 at 23:02
  • $\begingroup$ 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. $\endgroup$ Commented Mar 9, 2018 at 23:09
  • $\begingroup$ @John fair..... $\endgroup$
    – Raton
    Commented Mar 9, 2018 at 23:11

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .