O conjunto Lmt pode ser identificado com um subconjunto de N através da enumeração de Godel. Assim, pela enumeração de {0 , 1}* tem-se uma identificação wi, palavra binária, da i-ésima MT Mi. Mostre que Ld = {wi | wi ∉ L(Mi)} não é turing-reconhecível. Observe que Ld contém as cadeias que são codificações de MTs que não aceitam a própria codificação.
Para escrever sua resposta aqui, entre ou crie uma conta.
Compartilhar