Изменения

'''Пример:''' Согласно [[Машина_Тьюринга#.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BB.D0.B5.D0.BD.D1.82.D0.BE.D1.87.D0.BD.D0.B0.D1.8F_.D0.BC.D0.B0.D1.88.D0.B8.D0.BD.D0.B0_.D0.A2.D1.8C.D1.8E.D1.80.D0.B8.D0.BD.D0.B3.D0.B0 | тезису Чёрча {{---}} Тьюринга]], существует биекция между машинами Тьюринга и программами. Зафиксировав алфавит, можно занумеровать программы (программа будет иметь номер <tex>n</tex>, если ее код {{---}} <tex>n</tex>{{---}}е слово среди всех слов над алфавитом, отсортированных сначала по возрастанию длины, а при равной длине {{---}} в лексикографическом порядке), а следовательно и машины Тьюринга. Рассмотрим язык <tex> \{1^{n} \mid n</tex>{{---}}я [[Машина Тьюринга | машина Тьюринга]] останавливается в допускающем состоянии <tex> \} </tex>. Просто приняв <tex> p(n) = 1 </tex>, получим, что он принадлежит <tex> \mathrm{SPARSE}</tex>. Более того, любой унарный язык принадлежит <tex>\mathrm{SPARSE} </tex> .