Simple concrete example of a language that is Turing recognizable but not decidable

379 Views Asked by At

Sipser's Theory of Computation, third edition, chapter three introduces the idea that such languages exist but gives no examples. Chapter four gives examples in terms of abstract languages whose strings are themselves representations of machines.

What would be a concrete example of a language that is recognizable but not decidable?

1

There are 1 best solutions below

0
On

The set of string encodings of instances of the Post Correspondence Problem that have matches is a language that is recognizable but not decidable, as discussed in Sipser's Introduction to the Theory of Computation, Third Edition, chapter 5, pages 227-233. The discussion includes a proof of undecidability by reduction from the language of encodings <M,w> where M is a Turing machine that accepts w.

It is clear that the language is recognizable since one could systematically enumerate sequences of dominos, checking each one to to see if it is a match. If a match exists, it will be found. If not, however, the procedure could run forever.