Comment montrer que la fonction est non calculable?

https://cs.stackexchange.com/questions/11181

16-10-2019
|

Question

Je sais qu'il existe une machine de Turing, si une fonction est calculable. Alors, comment montrer que la fonction est pas calculable ou il n'y a pas une machine de Turing pour cela. Y at-il quelque chose comme un lemme de Pompage?

La solution

Avant de répondre à votre question générale, laissez-moi prendre d'abord un pas en arrière, faire un bref historique de l'histoire, et répondre à une question préliminaire:? Les fonctions non calculables existent même

^{[Notationnelle Note: nous pouvons rapporter toute $ fonction f $ avec un langage $ L_f = \ {(x, y) \ mid y = f (x) \} $, puis discuter de la décidabilité de $ L_f $ plutôt que la calculabilité de $ f $]}

langues indécidables faire existent

Il y a quelques langues qu'aucune machine de Turing peut décider. L'argument est simple: il y a "seulement" un nombre dénombrable $ (\ aleph_0) $, mais différentes mémoires de traduction indénombrablement beaucoup $ (\ aleph) $ différentes langues. Ainsi, il y a au plus $ \ aleph_0 $ langues décidables, et le reste (en nombre infini) sont indécidables. Pour en savoir plus:

Afin de mettre la main sur une langue spécifique indécidable, l'idée est d'utiliser une technique appelée diagonalisation (Georg Cantor, 1873), qui était à l'origine utilisé pour montrer qu'il ya un nombre plus réel que des entiers, ou en d'autres termes, que $ \ aleph> \ aleph_0 $.

L'idée de la construction de la première langue indécidable est simple: (! Ce qui est possible car ils sont recusively dénombrable) nous répertorions toutes les machines de Turing, et créer un langage qui est en désaccord avec chaque TM sur au moins une entrée

$$ \ Begin {array} {c |} CCCCC & \ Varepsilon & 0 & 1 & 00 & \ cdots \\ \ hline M_1 & \ color {red} {1} & 0 & 1 & 0 & 1 \\ M_2 & 0 & \ color {red} {1} & 0 & 0 & 0 \\ M_3 & 0 & 0 & \ color {red} {0} & 1 & 0 \\ \ Vdots & & & & \ ddots & \ End {array} $$

Dans ce qui précède, chaque ligne est une TM et chaque colonne est une entrée. La valeur de la cellule est 0 si les rejets TM ou jamais arrête et 1 si la MC accepte cette entrée. Nous définissons la langue $ D $ à être tel que $ D $ contient $ i $ entrée -ème si et seulement si le $ i $ -ème TM n'accepte pas cette entrée.

Suite à la table ci-dessus, $ \ varepsilon \ Notin D $ depuis accepte $ M_1 $ $ \ varepsilon $. De même, $ 0 \ Notin D $, mais 1 $ \ in D $ depuis M_3 $ $ n'accepte pas 1 $.

Maintenant, supposons $ M_k $ décide $ D $ et rechercher la ligne $ k $ dans le tableau: s'il y a 1 $ en $ k $ -ième colonne, puis $ M_k $ accepte que l'entrée mais est pas en $ D $ , et s'il y a un $ 0 $ là, l'entrée est à $ D $ $ mais M_k $ ne l'accepte pas. Par conséquent, $ M_k $ ne décide pas $ D $, et nous avons atteint la contradiction.

Maintenant, pour votre question. Il y a plusieurs façons de prouver qu'une langue est indécidable. Je vais essayer de toucher les plus courantes.

1. Une preuve directe

La première méthode, est de montrer directement qu'une langue est indécidable, en montrant qu'aucun TM peut le décider. Cela fait suite à ususally la méthode de diagonalisation ci-dessus.

Exemple.

Montrer que le (en complément de la) langue diagonale $$ \ overline {L_D} = \ {\ langle M \ rangle \ mid \ langle M \ rangle \ Notin L (M) \} $$ est indécidable.

Preuve. Supposons $ \ overline {L_D} $ est décidable, et que $ M_D $ soit son decider. Il y a deux cas:

accepte $ M_D $ $ \ langle M_D \ rangle $ : mais, $ \ langle M_D \ rangle \ en L (M_D) $ si $ \ langle M \ rangle \ Notin \ overline { L_D} $. Donc, cela ne peut se produire si $ M_D $ décide $ \ overline {L_D} $.
$ M_D $ n'accepte pas $ \ langle M_D \ rangle $ : si $ \ Langle M_D \ rangle \ L Notin (M_D) $ et donc $ \ langle M \ rangle \ in \ overline {L_D} $. Mais si elle est en $ L_D $, $ M_D $ aurait accepté, et nous atteint une contradictionle gain.

2. propriétés de fermeture

Parfois, nous pouvons utiliser les propriétés de fermeture pour montrer une langue n'est pas décidable, sur la base d'autres langues que nous connaissons déjà pas décidable.

Plus précisément, si $ L $ est non décidable (nous écrivons $ L \ Notin R $), puis aussi son complément $ \ overline {L} $ est indécidable: s'il y a decider $ M $ pour $ \ overline {L} $ on pourrait juste l'utiliser pour décider $ L $ en acceptant chaque fois M $ $ rebuts et vice-versa. Depuis $ M $ toujours avec une réponse arrête (c'est un decider), on peut toujours inverser sa réponse.

Conclusion:. Le $ de langue diagonale {L_D} = \ {\ langle M \ rangle \ mid \ langle M \ rangle \ en L (M) \} $ est indécidable, L_D $ \ Notin R $

Un argument similaire peut être appliqué en faisant remarquer que si les deux $ L $ et son complément $ \ overline {L} $ sont récursivement dénombrable, les deux sont décidable. Ceci est particulièrement utile si l'on veut prouver qu'une langue n'est pas récursivement énumérable, une propriété forte que indécidabilité.

3. La réduction d'un problème indécidable

En général, il est assez difficile de prouver directement que la langue est indécidable (à moins qu'il ne soit déjà construit de façon « diagonale »). La dernière et la méthode la plus courante pour prouver indécidabilité est d'utiliser une autre langue que nous connaissons déjà indécidable. L'idée est de réduire d'une langue à l'autre: pour montrer que si l'on est décidable, l'autre doit également être décidable, mais l'un d'entre eux est déjà connu pour être indécidable qui conduit à la conclusion que le premier est indécidable. En savoir plus sur la réduction des "Quelles sont les techniques communes de réduire les problèmes les uns aux autres? ".

Exemple.

Montrer que la langue diagonale $$ HP = \ {\ langle M, x \ rangle \ mid M \ texte {} x sur des arrêts \} $$ est indécidable.

Preuve. Nous savons que $ L_D $ est indécidable. Nous réduisons $ L_D $ à $ HP $ (ce qui est noté L_D $ \ le HP $), qui est, nous montrons que si $ HP $ était décidable nous pourrions utiliser son decider pour décider L_D $ $, ce qui est une contradiction.

La réduction fonctionne en convertissant un $ candidat w $ pour $ L_D $ (soit une entrée pour chaque décideur potentiel / accepteur pour $ L_D $) à un $ candidat w '$ pour $ HP $ tel que $ w \ in L_D $ si et seulement si $ w » \ dans HP $. Nous veillons à ce que cette conversion est calculable. Ainsi, décider $ w '$ nous dit si oui ou non $ w \ dans L_D $, donc si nous pouvons décider HP nous serons également en mesure de décider .¹ L_D $ $

La conversion est suit comme. Prenez un peu de $ w = \ langle M \ rangle $, et la sortie $ w '= \ langle M', \ langle M \ rangle \ rangle $, ² où $ M '$ est un MC qui se comporte tout comme $ M $, mais si $ M $ rebuts, puis M '$ va $ dans une boucle infinie.

Soit s voir que $ w, w '$ satisfaire aux exigences.
Si $ w \ dans L_D $, cela signifie que $ M $ arrête et accepte l'entrée $ \ langle M \ rangle $. Par conséquent, M $ «Les $ arrêts et accepte l'entrée $ \ langle M \ rangle $. Ainsi, $ \ langle M », \ langle M \ rangle \ rangle \ dans HP $.
D'autre part, si $ w \ Notin L_D $, alors M $ $ rejette ou jamais sur $ arrête \ langle M \ rangle $. Dans les deux cas, M '$ $ entrera dans une boucle infinie sur $ \ langle M \ rangle $. Ainsi, $ \ langle M '\ langle M \ rangle \ rangle \ Notin HP $, et nous faites montrant que $ w \ dans L_D $ si et seulement si $ w' \ dans HP $, et ont ainsi montré que $ HP \ Notin R $.

Pour en savoir plus: de nombreux exemples de réductions et prouver undecidablility des langues se trouve via balise de réductions.

Il y en a plus de restrictions sur la réduction valide. La conversion elle-même doit être calculable , et bien défini pour toute entrée.
Une entrée de $ HP $ regarde comme $ \ langle M, x \ rangle $, où $ M $ est un MC et $ x $ est doncstring moi. Donc, ici, nous choisissons la chaîne $ x $ pour être un codage de la machine $ M $, ce qui est juste une chaîne de caractères ..

4. Le riz est le théorème

"Donc chaque fois que nous souhaitons prouver $ L $ est indécidable, nous devons réduire $ L_D $ (ou $ HP $) à elle? Est-il pas de raccourci?"

Eh bien, en fait, il y a. C'est le théorème de riz .

Le théorème dit que beaucoup de langues qui ont une certaine structure, sont indécidables. Parce que toutes ces langues ont cette certaine structure, nous pouvons faire la réduction, une fois et l'appliquer à toute langue qui admet une structure similaire.

Le théorème est formellement déclaré de la manière suivante,

Théorème (Rice). Compte tenu de propriété $ \ emptyset \ subsetneq S \ subsetneq RE $, la langue suivante $ L_S $ est indécidable $$ L_S = \ {\ langle M \ rangle \ mi L (M) \ in S \} $$

L'ensemble $ S $ est un sous-ensemble des langues de $ RE $; nous l'appelons une propriété parce qu'elle décrit une propriété de la L $ de langue acceptée (M) $. Tous les mémoires de traduction dont la langue satisfait à cette propriété appartiennent à $ L_S $.

Par exemple, $ S $ peut être la propriété que la L $ de langue acceptée (M) $ contient exactement deux mots:

$$ S_2 = \ {L \ mi | L | = 2, L \ RE \}. $$ Dans ce cas $ L_ {S_2} $ est l'ensemble de toutes les mémoires de traduction dont la langue se compose d'exactement deux mots: $$ L_ {S_2} = \ {\ langle M \ rangle \ mi L (M) \ dans S \} = \ {\ langle M \ rangle \ mi | L (M) | = 2 \}. $$

La propriété peut être très simple, mais il ne peut pas être tous les langues RE ou pas des langues RE. Si $ S = \ emptyset $ ou $ S = RE $, alors la propriété est dit être trivial , et la L_S $ induite $ est calculable. Un exemple pour un simple $ S $ est l'un des ne contient qu'une seule langue, disons $ S_ {complet} = \ {\ Sigma ^ * \} $. Notez que bien que $ S $ ne contient qu'une seule langue, il y a une infinité de machines M $ $ dont la langue est $ \ Sigma ^ * $, donc $ L_ {S_ {concurrence}} $ est infini, et indécidable.

Le théorème est très puissant pour prouver indécidabilité de nombreuses langues.

Exemple.

La langue $ L_ \ emptyset = \ {\ langle M \ rangle \ mid M texte \ {n'a jamais atteint l'état d'accepter} \} $, est indécidable

Preuve. Nous pouvons écrire $ L_ \ emptyset $ en $ \ {\ langle M \ rangle \ mi L (M) = 0 \} $, soit $ L_ \ emptyset = L_S $ pour la propriété $ S = \ {L \ RE , | L | = 0 \} $. Ceci est une propriété non triviale (elle inclut la langue $ L = \ emptyset $, mais ne comprend pas, par exemple, la langue $ L = \ {1, 11, 111, \ ldots \} $. Par conséquent, par Rice théorème, $ L_ \ emptyset $ est indécidable.

Nous allons maintenant démontrer le théorème. Comme mentionné ci-dessus, nous allons montrer une réduction de $ HP $ à $ L_S $ (pour tout $ non trivial arbitraire S $).

Preuve. Soit $ S $ une propriété non trivial, $ \ emptyset \ subsetneq S \ subsetneq RE $. Nous montrons $ HP \ le L_S $, qui est, nous réduisons $ HP $ à donc $ L_S $ que si nous pouvons décider $ L_S $, nous serons en mesure de décider $ HP $ (que nous savons être impossible, par conséquent, $ L_S $ ne peut pas être décidable). Dans la preuve ci-dessous, nous supposons que la langue vide ne fait pas partie de $ S $, qui est $ \ emptyset \ Notin S $. (Si la langue est vide dans $ S $, une preuve équivalente travaille sur la propriété du complément $ \ overline S = RE \ setminus S $, je vais omettre les détails). Depuis $ S $ est non négligeable, il comprend au moins une langue; Appelons cette langue $ L_0 $ et d'assumer M_0 $ est une machine qui accepte $ L_0 $ (telle machine existe, puisque $ S $ ne comprend que des langues RE).

Rappelons que dans la réduction de un (voir section 3 ci-dessus), nous devons montrer comment convertir un $ d'entrée w $ pour $ HP $ en un $ d'entrée w '$ pour L_S $ $ afin que $$ w \ dans HP \ quad \ texte {si et seulement si} \ quad w » \ dans L_S $$

Soit $ w = (\ langle M \ rangle, x) $, nous convert dans $ w '= \ langle M' \ rangle $ lorsque la description de la machine $ M '$ (sur une entrée $ x' $) est la suivante:

Run $ M $ sur $ x $.
Si l'étape 1 ci-dessus arrête, exécutez M_0 $ $ $ sur x '$ et accepter / rejeter en conséquence.

Nous voyons que cette conversion est valide. Notons d'abord qu'il est simple à construire la description de M $ 'donné $ w $ = (\ langle M \ rangle, x) $.

Si $ w \ dans HP $, puis $ M $ arrête de $ x $. Dans ce cas, $ M '$ passe à l'étape 2, et se comporte comme M_0 $ $. Par conséquent, sa langue acceptée est $ L (M) = M_0 \ dans S $. Par conséquent, $ w '= \ langle M' \ rangle \ dans L_S $.
Si $ w \ Notin HP $, alors les boucles M $ $ sur $ x $. Ce cas, $ M '$ boucles sur une entrée $ x' $ - si elle se bloque à l'étape 1. La langue acceptée par $ M '$ dans ce cas est vide, $ L (M) = \ emptyset \ Notin S $ . Par conséquent, $ w '= \ langle M' \ rangle \ Notin L_S $.

4.1 Le théorème étendu de riz

théorème de Rice nous donne un moyen facile de montrer qu'une certaine langue $ L $ qui satisfait à certaines propriétés est indécidable, qui est, $ L \ Notin R $. La version étendue du théorème de Rice nous permet de déterminer si la langue est récursive-dénombrable ou non, qui, détermine si $ L \ Notin RE $, en vérifiant si $ L $ satisfait des propriétés supplémentaires.

Théorème (riz, étendu). Étant donné une propriété $ S \ subseteq RE $, la langue $$ L_S = \ {\ langle M \ rangle \ mi L (M) \ in S \} $$ est récursive-dénombrable ($ L_S \ RE $) si et seulement si tous les trois énoncés suivants détiennent conjointement

Pour tout deux $ L_1, L_2 \ RE $, si L_1 $ \ en S $ et aussi $ L_1 \ subseteq L_2 $, alors aussi L_2 $ \ en S $.

Si $ L_1 \ dans S $, alors il existe un sous-ensemble fini $ L_2 \ subseteq L_1 $ pour que L_2 $ \ en S $.

L'ensemble de tous les fini langues en $ S $ est dénombrable. (Autrement dit: il y a un TM qui énumère toutes les langues finies $ L \ in S $)

Preuve. Ceci est un « si et seulement si » théorème, et nous devons prouver ses deux directions. Tout d'abord, nous montrons que si l'une des conditions (1,2,3) ne tient pas, alors $ L_S \ Notin RE $. Après cela, nous allons montrer que si les trois conditions tiennent simultanément, puis $ L_S \ RE $.

Si (1,2) en attente, mais (3) ne pas, alors $ L_S \ Notin RE $ .
Supposons que $ L_S \ RE $, et nous verrons que nous avons un moyen d'accepter toutes les langues finies en $ S $ (et donc, l'ensemble de toutes ces langues est RE), l'état ainsi (3) détient et nous arrivons à une contradiction. Comment décider si un $ fini L $ appartient à $ S $ ou non? Facilement - nous utilisons la description de $ L $ pour construire une machine $ M_L $ qui accepte seulement les mots $ L $, et maintenant nous courons la machine de $ L_S $ sur $ M_L $ (souvenez-vous - nous supposions $ L_S \ en RE $, donc il y a une machine qui accepte $ L_S $!). Si $ L \ dans S $, alors $ \ langle M_L \ rangle \ dans L_S $ et $ depuis L_S \ RE $, sa machine dire oui à l'entrée $ \ langle M_L \ rangle $, et nous fait.

Si (2,3) en attente, mais (1) ne pas, alors $ L_S \ Notin RE $ .
Nous partons du principe que $ L_S \ RE $ et nous allons montrer que nous avons un moyen de décider $ HP $, conduisant à une contradiction.

Parce que la condition (1) ne tient pas, il y a un langage $ L_1 \ en S $ et un surensemble de celui-ci, $ L_2 \ supseteq L_1 $ pour que $ L_2 \ Notin S $. Maintenant, nous allons répéter l'argument utilisé à l'article 4 de décider $ HP $: étant donné une entrée $ (\ langle M \ rangle, x) $ pour $ HP $, on construit une machine $ M '$ dont la langue est $ L_1 $ si $ (\ langle M \ rangle, x) \ Notin HP $ ou autrement, sa langue est $ L_2 $. Ensuite, nous pouvons décider $ HP $: soit $ M $ arrêts sur $ x $, ou la machine RE pour $ accepte L_S $ $ 'M $; nous pouvons exécuter les deux en parallèle et sont garantis qu'au moins un Empeschera.

Nous allons donner les détails de la construction M $ '$ (sur l'entrée $ x' $):

Effectuez les opérations suivantes en parallèle:
1,1 M $ run $ sur $ x $.
1.2 tourner la machine de $ L_1 $ sur $ x '$
Si 1.2 et accepter des arrêtss -. accepter
Si 1.1 arrête:. Tourner la machine de $ L_2 $ sur $ x '$

Pourquoi ce travail? Si $ (\ langle M \ rangle, x) \ Notin HP $ 1.1 puis jamais arrête et M $ 'accepte $ exactement toutes les entrées qui sont acceptées à l'étape 1.2, $ L (M) = L_1 $. D'autre part, si $ (\ langle M \ rangle, x) \ dans HP $, alors, à quelque pas du point 1.1 M $ et arrête 'accepte $ exactement $ L_2 $. Il peut arriver que $ 1.2 $ accepte à l'avance, mais depuis $ L_1 \ subseteq L_2 $, cela ne change pas la langue de $ M '$ dans ce cas.

Si (1,3) prise, mais (2) ne pas, alors $ L_S \ Notin RE $ .
Encore une fois, nous supposerons $ L_S \ RE $ et montrer que $ HP $ devient décidable, ce qui est une contradiction.

Si la condition (2) ne tient pas, alors pour tout L_1 $ \ en S $, tous ses sous-ensembles finis $ L_2 \ subseteq L_1 $ $ L_2 satisfont \ Notin S $ (note qui doit être infinie $ L_1 $, depuis $ L_1 \ subseteq L_1 $). Comme dans ce qui précède, afin de décider $ HP $ pour un $ d'entrée donné (\ langle M \ rangle, x) $, on construit une machine $ M '$ dont la langue est $ L_1 $ si $ (\ langle M \ rangle , x) \ Notin HP $ et quelques $ fini L_2 $ autrement. La contradiction suit d'une manière similaire à celle ci-dessus.

La construction de cette machine est assez similaire à la précédente $ M '$ nous avons construit. La machine $ M '$ (en entrée x $' $) t:

Runs $ M $ sur $ x $ pour $ | x '|. $ Étapes
Si $ M $ au cours de haltes étape 1 - rejeter
Dans le cas contraire, exécutez la machine de $ L_1 $ sur $ x '$.

Il estime que, si $ (\ langle M \ rangle, x) \ dans HP $, puis à un moment donné, dire après 1000 étapes, M $ $ arrêts sur $ x $. Par conséquent, l'étape 1 va arrêter le (et rejeter) toute entrée x $ '$ de longueur $> $ 1000. Par conséquent, dans ce cas, $ L (M) $ est fini . Notez également que $ L (M ') \ subseteq L_1 $, et en particulier par nos hypothèses sur l'invalidité de la condition (2), nous avons que $ L (M) \ Notin S $.

Par contre, si $ (\ langle M \ rangle, x) \ Notin HP $, alors l'étape 1 jamais arrête, et nous rejetons jamais à l'étape 2. Dans ce cas, il est facile de voir que L $ ( M) = L_1 $ et, en particulier, $ L (M) \ in S $.

Il nous reste à montrer l'autre sens du théorème étendu. Autrement dit, nous devons montrer que si toutes les conditions (1,2,3) en attente, alors nous avons un MC qui accepte L_S $ $, qui est, L_S $ \ RE $. En d'autres termes, nous devons montrer une machine $ m_s $ de sorte que pour une entrée $ \ langle M \ rangle $ pour lesquels $ L (M) \ en S $, la machine accepte cette entrée, m_s $ (\ langle M \ rangle) \ à \ textsf {accept} $.

Voici comment la machine m_s $ se comporte de $ (sur l'entrée $ \ langle M \ rangle $):

Soit M $ _ {\ texte {} ENUM S} $ soit la machine qui énumère toutes les langues finies en $ S $, garantie par condition (3).
Exécuter ce qui suit en parallèle (par imbrication, voir par exemple, cette et this ) pour $ i = 1,2, ... $
2.1 Run M $ _ {\ texte {S}} ENUM $ jusqu'à ce qu'il génère la langue $ L_i $
2.2. Vérifiez si $ M $ accepte tous les mots de $ L_i $ ($ M $ courir sur ces mots, encore une fois en parallèle).
2.3. Si pour quelque $ i $, $ M $ accepte tous les mots de L_i $ - accepter.

Pourquoi ça marche? Si $ L (M) \ dans S $, alors il a un sous-ensemble fini $ L_j \ en S $, et une fois M $ _ {\ texte {ENUM} S} $ sorties ce sous-ensemble, étape 2.2 / 2.3 constatera que $ M $ accepte tous les mots dans cette langue et accepter.

Par contre, si $ L (M) \ Notin S $ il ne peut pas être accepter tous les mots $ L_i $ pour tout $ i = 1,2, ... $. En effet, par condition (1), toute L $ \ supseteq L_i $ est en $ S $, donc si $ M $ accepte tous les mots $ L_i $ pour un i $ $, puis $ L (M) \ supseteq L_i $ et donc $ L (M) \ en S $, en contradiction.

Enfin, notez que ce qui suit est un simple (et très utile) corollaire de ce qui précède:

Corollaire (riz, étendu). Étant donné une propriété $ non trivial S \ subsetneq RE $, de sorte que $ \ emptyset \ en S $, la langue $$ = L_S \ {\ langle M \ rangle \ mi L(M) \ in S \} $$ n'est pas récursive-dénombrable, qui est, $ L_S \ Notin RE $.

Autres conseils

Un outil utile est Le riz théorème est . Voici ce qu'il dit:

Soit $ \ emptyset \ subsetneq P \ subsetneq \ mathcal {P} $ un ensemble non négligeable de partiellement calculables fonctions unaires et $ \ varphi $ Gödel numérotation de $ \ mathcal {P} $. Ensuite, l'ensemble d'indices de $ P $

$ \ qquad I_P = \ {i \ in \ mathbb {N} \ mid \ varphi_i \ dans P \} $

est pas récursive.

Vous trouvez qu'il a également exprimé en termes de codages machines de Turing (ou tout autre langage de programmation Turing-complet), soit $ I_P = \ {\ langle M \ rangle \ mid M \ \ mathrm {TM}, f_m \ dans P \} $; ici $ \ langle. \ Rangle $ définit une numérotation Gödel.

C'est, vous pouvez utiliser le théorème de Rice pour prouver de tels ensembles $ S $ ensembles non récursif qui sont des ensembles d'index de la fonction non triviale (ou tel est réductible à $ S $).

Notez qu'il existe une extension qui peut être utilisé pour montrer que certains ensembles d'index ne sont pas récursivement énumérable.

Exemple

Soit $ \ varphi $ une numérotation Gödel. Considérons l'ensemble de Naturals

$ \ qquad A = \ {i \ in \ mathbb {N} \ mid \ varphi_i (j) = 1 \ texte {pour tout} j \ dans 2 \ mathbb {N} \} $.

Maintenant, puisque pour $ P = \ {f \ in \ mathcal {P} \ mid f (j) = 1 \ text {} pour tous j \ dans 2 \ mathbb {N} \} $

$ A = I_P $,
$ (n \ mapsto 1) \ in P $ et
$ (n \ mapsto 2) \ P $ notin,

théorème de riz peut être appliqué et $ A $ est pas décidable.

Étant donné que beaucoup ne sont pas familiers avec les numérotations Gödel, notez que l'exemple fonctionne aussi bien en termes de machines de Turing (c.-à-programmes) en utilisant $ A = \ {\ langle M \ rangle \ mid f_m (x) = 1 \ text {} pour tout x \ dans 2 \ mathbb {N} \} $.

Unexample

Considérons l'ensemble de Naturals

$ \ qquad A = \ {i \ in \ mathbb {N} \ mid \ varphi_i (j) = i \ texte {} pour tous j \ dans 2 \ mathbb {N} \} $

qui est certainement pas calculable. Cependant, $ A $ est pas un ensemble d'indices pour tout $ $ P! Soit $ f = \ varphi_i $ pour quelque $ i \ dans A $. Depuis $ \ varphi $ est Gödel numérotation, il y a (une infinité) $ j \ neq i $ avec $ \ varphi_j = f $, mais pour tous $ j \ Notin A $ tient parce que $ f ( 2) = i \ neq j $.

Méfiez-vous de tout cela! En règle générale, si l'indice de la fonction est utilisée sur « le côté droit » ou en tant que paramètre de la fonction dans la définition du jeu, il est probablement pas un ensemble d'indices. Vous devrez peut-être $ S_ {mn} $ la propriété de numérotations Gödel et fixpoint théorème pour montrer qu'un ensemble est pas ensemble d'index.

Voir et ici pour les postes connexes sur le théorème de Rice.

Licencié sous: CC-BY-SA avec attribution

Non affilié à cs.stackexchange