I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ It’s a language which either contains all strings or contains no strings. $\endgroup$– Yuval FilmusJul 3, 2019 at 4:53
-
2$\begingroup$ Did you try Googling this? You seem to ask a lot of very simple questions in a short space of time -- we do expect you to do some basic research on your own before posting here. Remember that every answer people post here takes up some of their time. $\endgroup$– David RicherbyJul 3, 2019 at 10:24
-
$\begingroup$ @DavidRicherby Yep, I was initially confused by the notion of trivial property and could not find a direct answer. I am also possibly not very good at parsing information haha. I asked here also so that it would be easily accessible for anyone confused in the future. In about a month, I think in hindsight, this question may seem "trivial" $\endgroup$– WeCanBeFriendsJul 3, 2019 at 10:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A trivial language is one that has no strings, or one that has every string in some alphabet.
In terms of models of computation, a trivial language is one that can be decided by a Turing Machine or lambda function that completely ignores its input.
