HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Sub language is not Turing-recognizable, or could it be?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
subrecognizablecouldlanguageturingnot

Problem

Let A and B be languages with A ⊆ B, and B is Turing-recognizable. Can A be not Turing-recognizable? If so, is there any example?

Solution

This is something that confuses many students. The point here is that being subset of another language does not imply much about their difficulty of computation. You can always consider the trivial language $\emptyset$ and $\Sigma^*$ and any other language is between them w.r.t. set inclusion.

Therefore just knowing that a language contains or is contained in a easy to compute language doesn't say anything about the difficulty of computing it.

Context

StackExchange Computer Science Q#1427, answer score: 18

Revisions (0)

No revisions yet.