El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva.
La pregunta anterior sobre los números primos se puede véase también como el lenguaje de todas las frases en el alfabeto {0, 1,..., 9} tales que el entero correspondiente es primo.
Por tanto una instancia tiene una respuesta específica: «sí» o «no».
Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible.
Para conjuntos de números naturales se emplea una terminología alternativa: