Les programmes impossible

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 !

• Halting Problem

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

J'avais oublié cette partie du post :

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 .

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.

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 crois que je vais m'amuser a le faire

J'ai pas vraiment comptis la pteuve par l'absurde detaillée dans wikipedia, en fait je comprend pas en quoi la fonction halt implique la fonction diagonal !

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)$¹ 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).

J'ai mieux compris ! Merci

Voici une video pour ceux qui n'ont pas compris, elle est assez interessante !

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.

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 !

@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.