Calculabilité

[invite72334b6e]

Bonjour,

Est-ce que toute fonction f : N -> {0,1} telle que f(n) n'est pas défini si n>42, est calculable ?

Merci d'avance.
-----

[Chanur]

Bonjour,
Si N désigne l'ensemble des entiers naturels, l'ensemble des fonctions f est fini. Tu peux en faire la liste exhaustive. C'est laquelle qui ne te semble pas calculable ?
Et si N désigne autre chose, tu devrais dire quoi, si tu veux une réponse ...
Au revoir.

[invite72334b6e]

Merci.

N désigne effectivement l'ensemble des entiers naturels. Ce qui me gêne, c'est qu' "une fonction calculable est une fonction qui peut être définie par un algorithme". Donc comment écrire un algorithme (une procédure) qui calcule f ?

[Médiat]

Bonjour,

Comme il suffit de définir les images de 0 à 41, l'algorithme est on ne peut plus simple, il suffit de lister les 42 images.

[A voir en vidéo sur Futura]

[invite72334b6e]

D'accord merci. Mais dans le même principe : par exemple, est-ce que toute fonction totale f : N -> {0,1} telle que f(n) = 1 ssi n >= 42, est-elle calculable ?

[Médiat]

Vous venez de donner l'algorithme

[invite4492c379]

Hello,

pour les fonctions partielles tu peux faire une liste exhaustive mais il y en a quand même 2⁴² ...
Tu peux ordonner tes fonctions partielles, nommons les à , et considère tout simplement que renvoie le n^ème bit de l'écriture binaire de k, par exemple.

Si tu prends les fonctions totales alors tu peux considérer qu'une telle fonction te renvoie le nème bit de l'écriture binaire d'un réel, la question est donc est-ce que tous les réels sont calculables ? la réponse est non. Enfin si je ne me trompe pas, quelqu'un peut-il valider ma proposition ?

[invite72334b6e]

Je ne comprend pas votre message Médiat :s

[Médiat]

Je ne comprend pas votre message Médiat :s

Vous connaissez l'algorithme qui va calculer l'image des nombres de 0 à 41, et vous même avez donné l'algorithme pour n >= 42 : f(n) = 1 ; vous avez donc un algorithme qui calcule votre fonction pour tout n.

[invite72334b6e]

Hum d'accord. Mais comment justifier que toute fonction totale f : N -> {0,1} telle que f(n) = 1 ssi n >= 42, est primitive récursive, autrement dit calculable ?
(sans prend en compte le fait que toute fonction f : N -> {0,1} telle que f(n) n'est pas défini si n>42, est calculable)

[invite4492c379]

Tout ce que je dis est «toute fonction totale f:IN->{0,1} n'est pas calculable», identique à «Il existe au moins une fonction totale f:IN->{0,1} qui n'est pas calculable» cela ne signifie pas «aucune fonction totale f:IN->{0,1} n'est calculable».

D'accord merci. Mais dans le même principe : par exemple, est-ce que toute fonction totale f : N -> {0,1} telle que f(n) = 1 ssi n >= 42, est-elle calculable ?

pour la question là la réponse est oui (j'ai effectivement répondu un peu trop large). Elle l'est car tu as donné toi même un algorithme pour la calculer, que ce soit le cas où f(n) vaut 0 pout n<42 où le cas où tu étends la définition des fonctions partielles de ton premier post.

[Tryss]

Heu... il me semble qu'une fonction de N dans {0,1} telle que seul les 42 premiers termes sont définis n'est pas calculable... puisque non totale ! (f(100) n'est pas définie alors que 100 appartient à N)

[invite4492c379]

Oui tu as raison, une fonction calculable est une fonction semi calculable qui est aussi totale.

[invite72334b6e]

Êtes-vous sur ? car mon énoncé me demande justement de justifier qu'elle est calculable. Cependant, vos explications me semblent logiques, donc l'erreur vient probablement de l'énoncé.

J'aimerai quand même revenir sur le fait de : comment montrer que toute fonction totale f : N -> {0,1} telle que f(n) = 1 ssi n >= 42, est calculable ? En effet, je n'arrive pas à voir l'algorithme qui se cache derrière. Quel serait concrètement l'algorithme pour la calculer ?

[invite4492c379]

Tu prends la même définition que les f_k que j'ai donné si n<42 et si n>42 f_k(n)=0.

[invite72334b6e]

"f(n) = 1 ssi n >= 42" donc f(n) est toujours égale à 0 si n<42, non ?

[invite4492c379]

ça va dépendre ... quel est l'énoncé exact ?

[invite72334b6e]

Justifier que : toute fonction totale f : N -> {0,1} telle que f(n) = 1 ssi n >= 42, est primitive récursive.

[invite4492c379]

Justifier que : toute fonction totale f : N -> {0,1} telle que f(n) = 1 ssi n >= 42, est primitive récursive.

Donc rien n'est spécifié pour n<42, donc il y a 2⁴² fonctions possibles etc ...

[invite7723032d]

A babaa : tu peux montrer que toute fonction totale f : N -> {0,1} telle que f(n) = 1 ssi n >= 42 est primitive récursive à l'aide des fonctions initiales (il me semble). Et tu sais que primitif récursif => calculable.

A Tryss :
http://www.labri.fr/perso/betrema/MC/MC2.html#fc
D'après ce lien : << Dans tout modèle de calcul, il existe des fonctions calculables partielles (strictement)>>

[invite72334b6e]

Qu'entendez-vous par fonctions initiales ? constantes, succession, projection... ?

[invite7723032d]

Oui,par exemple pour la fonction f(n) = 0 si n<42
1 si n >= 42

on pourrait écrire f(n) = Zero(n) si n < 42
Succ(Zero(n)) si n >= 42

[invite72334b6e]

D'accord merci.
Par contre pour revenir à mon 1er post : justifier que toute fonction f : N -> {0,1} telle que f(n) n'est pas défini si n>42, est calculable.
J'ai un peu de mal à comprendre le principe des fonctions partielles.

[invite15554134]

hey !

la question juste au dessus m'interesse également

et est ce que vous pourriez m'aider par rapport à ceci :

si on prend un programme P semi décidable, justifiez qu'il existe une réduction de P à univ

, univ étant définie comme ceci : (n,m) est une instance positive si le programme Pn termine sur l'entrée m !

merci bien