Pour prouver que la 3-coloration est décidable, suffit-il de dire:
- Chaque nœud du graphique a 3 couleurs possibles
- Par conséquent, nous pouvons énumérer les possibilités, puis vérifier qu'il n'y a pas deux arêtes reliant les nœuds de la même couleur
Cela prouve-t-il que la coloration 3 est décidable? Ou dois-je construire une machine de Turing pour une preuve appropriée?
Par 3 coloriages, je parle du problème de coloration des graphes; c'est-à-dire affecter une des 3 couleurs à chaque nœud dans un graphe non orienté de telle sorte qu'il n'y ait pas deux nœuds adjacents de la même couleur.
Réponses:
Cela dépend entièrement du niveau de formalité que vous visez. La description informelle d'un algorithme dans votre question est tout à fait suffisante pour me convaincre que la colorabilité 3 est décidable. Si vous vouliez être un peu plus formel, vous pourriez donner un pseudocode. Si vous vouliez être encore plus formel, vous pourriez décrire une machine Turing en anglais. Si vous voulez être encore plus formel, vous pouvez écrire la description complète de la machine de Turing et prouver qu'elle décide vraiment de la 3-colorabilité.
Cela dit, parmi les options que j'ai énumérées, il est plus probable qu'il y ait une erreur dans la description de la machine Turing ou dans sa preuve d'exactitude! Il n'est donc pas clair quelle preuve serait la plus crédible.
la source
la source