Les programmes impossible

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour tout le monde ! Ce soir je me suis poser une grande question metainformatique.. Je sais qu'il existe des problèmes insoluble par un programme mais soluble par un humain. L'exemple le plus connu est le "Halting Problem" (même si je n'ai pas vraiment compris leur demonstration), mais je vous propose d'énoncer d'autres programmes impossible. J'éditerais la liste ci dessous ! Je vous rappel que l'on considère un problème comme insoluble par un programme si celui-ci possède une précision de calcul infini, un temps un infini et une mémoire infini. Il ne s'agit même pas de trouver une solution optimale, simplement une solution !

Petite question personnelle : Est il possible de créer une IA pour ce jeu ?

Édité par Coyote

+1 -0

Cette réponse a aidé l'auteur du sujet

Lu'!

Concrètement, tout problème que tu peux réduire au problème de l'arrêt est indécidable. Par exemple la libération correcte de ressources : on fait une machine qui libère ses ressources après l'exécution d'une autre machine, comme on ne sait pas si la première s'arrête, on ne peut pas décider si les ressources seront correctement libérées, etc …

Après, il faut bien voir que c'est le cas général, quand on a quelques connaissances de son problème, on peut résoudre certaines choses quand même. Typiquement les analyses statiques sont indécidables mais on peut faire plein de chose quand même avec (même résoudre l'arrêt sur un certain nombre de programme en associant par exemple des variants aux boucles et aux récursions).

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+2 -0

J'avais oublié cette partie du post :

Petite question personnelle : Est il possible de créer une IA pour ce jeu ?

Ricocotam

Oui, on peut. Après ça doit être au moins NP, je pense :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
solve(g : grid, lp : list pairs) : bool 
  if lp = []
     return true

  (s1, s2) :: tl <- lp

  impossible_path : list path
  do
    p <- find_path_not_in(g, s1, s2, impossible_path)
    if p = []
      return false

    g' <- mark(g, p)
    impossible_path <- p :: impossible_path
  while !solve(g', tl)

  return true

C'est du gros pseudo-code à l'arrache mais on voit vite que ça explose en temps ^^ .

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+0 -0

Petite question personnelle : Est il possible de créer une IA pour ce jeu ?

Ricocotam

Oui, très certainement. Une approche en profondeur ou en largeur doit pouvoir être applicable à ce genre de problèmes. Il doit même y avoir moyen de faire des choses intelligentes – je soupçonne des transpositions à la théorie des graphes qui offrira des techniques déjà éprouvées pour ces problèmes.

+0 -0

Histoire d'être exact, un problème de décision (question à laquelle on répond par oui ou non) peut être :

  • Décidable : il existe un programme donnant la réponse au problème en un temps fini, que la réponse soit positive ou négative.
  • Semi décidable : il existe un programme qui répond oui sur toute entrée positive du problème, et qui répond non ou ne termine pas sur une instance négative du problème (on n'est donc pas assuré d'obtenir une réponse).
  • Co semi décidable : le symétrique (on termine toujours sur une instance négative du problème, mais on n'est pas assuré d'obtenir une réponse sur une instance positive).
  • Et enfin indécidable : il n'existe pas de programme donnant de réponse en temps fini au problème.

Le problème de l'arrêt est semi-décidable : on peut écrire un programme qui répond en temps fini sur une instance positive du problème.

1
2
3
Halt(P, n):
    P(n)
    retourner vrai

Le problème de l'arrêt universel (un programme donné termine-t-il sur toutes ses entrées?) est lui en revanche indécidable.

Pour ton jeu, le problème est bien évidemment décidable : on peut naïvement tester toutes les solutions.

Je vais tenter d'expliquer la preuve, mais je ne sais pas si je ferai mieux que Wikipédia.

Considérons qu'il existe un programme $HALT(P, n)$, qui, étant donné un programme $P$ et une entrée $n$ pour ce programme répond vrai si le programme termine sur cette entrée, et faux sinon (quel que soit le programme, et quelle que soit l'entrée).

On définit alors un programme $DIAG(n)$ qui boucle indéfiniment si $HALT(n, n)$1 répond vrai et qui termine sinon. Que se passe-t-il si on essaie d'appliquer $HALT(DIAG, DIAG)$ ? Si $HALT$ répond vrai, alors, par construction, $DIAG$ devrait boucler. Mais s'il boucle, $HALT$ doit répondre faux. C'est une incohérence, donc $HALT$ n'existe pas. Donc le problème n'est pas décidable, mais comme je l'ai montré dans mon message précédent, il est semi décidable (l'ensemble des problèmes décidables est inclus dans l'ensemble des problèmes semi décidables).


  1. On peut choisir, par facilité, de considérer nos programmes comme des entiers. En effet, l'ensemble des programmes qu'il est possible d'écrire est en bijection avec $\mathbb{N}$. On peut donc lire $HALT(n, n)$ comme : le programme codé par l'entier $n$ appliqué à l'entier $n$ termine-t-il? 

Bonjour tout le monde !

Petite question personnelle : Est il possible de créer une IA pour ce jeu ?

Petite question personnelle : Est il possible de créer une IA pour ce jeu ?

Ricocotam

Je vais être tatillon sur les mots. Est-ce qu'il est possible de créer un algorithme pour solutionner ce jeu ? Oui. Aucun doute. Explorer toutes les combinaisons, sur une grille d'une petite centaine de cases, ça devrait pouvoir se faire en moins d'1 minute avec n'importe quel langage.

Est-ce qu'il existe une IA pour ce jeu ?

Pour moi, le terme IA n'est pas adapté. Le terme IA caractérise en principe les programmes qui s'auto-améliorent au fil du temps, par accumulation d'expérience. Par exemple, un programme de jeu d'échecs qui mémoriserait toutes les parties jouées, et qui conclurait : des fois, je tente des pièges 'basiques', des fois je cherche à consolider ma défense, et je constate que sur la durée, les pièges me font gagner plus souvent que l'autre stratégie. Et le programme ferait donc évoluer sa stratégie au fil du temps. Le programme pourrait même analyser le profil de son adversaire, est-ce un joueur 'livresque', ou un joueur fantasque, et adapter sa stratégie.

Aux échecs, cela s'applique peu, car on joue à cartes ouvertes. Au bridge ou au poker, ça pourrait s'appliquer un peu plus.

Édité par elegance

+0 -0
Auteur du sujet

J'ai lu un livre sur l'intelligence artificielle, et dans la definition ils disent que chacun a sa propre definition mais que globalement une IA est un programme qui resoud des probleme plus ou moins complexe avec une approche non force brute (intelligente quoi). Ma definition c'est plutot un programme qui agit comme l'humain, soit parce qu'il "reflechit" comme nous (resolution de sudoku par exemple), soit parce qu'il analyse et choisit la meilleur solution (echec), ily a d'autres truc mais voici les principales ! le fait qu'un programme evolue au fil du temps est un outil pour moi, en effet si ton programme agit comme un humain il se souvient de ce qui s'est passé avant ! :)

+0 -0

@elegance, ce que tu décris, c'est une branche du Machine Learning à laquelle le Reinforcement Learning appartient. Dans le ML, on trouve aussi les RdN et autres SVM qui au fond ne sont que des maths. Mais l'IA c'est aussi les algo bêtes et méchants : recherche en profondeur/largeur, les min-max & cie, l'A*, et plein d'autres choses. Les aspects qui ont dominé l'IA dans les années 70 (?) étaient très loin de l'intelligence animale.

+2 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte