Is each string decideble?

Question

Is it possible to prove that there exist for every string a Turing Machine that decides that string? I think it is provable that for every string you can build a TM that recognises that string, but I cannot find such a TM to decide a string.

You don't even need a Turing machine, you can use a finite deterministic automaton. — Captain Lama, Apr 07 '16 at 07:51

score 1 · Answer 1 · answered Apr 07 '16 at 08:11

I'll do it in a pseudo-programming-language, recognising the string "1101" as an example.

if x1 = 1 then
  if x2 = 1 then
    if x3 = 0 then
      if x4 = 1 then
        return true
return false

So by Church's thesis, since I have described how to recognise the string "1101", there is a Turing machine to do it.

Is each string decideble?

1 Answers1