Séance de cours

Halting Problem : des problèmes insolubles

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours traite du concept de problèmes insolubles dans les algorithmes, en se concentrant sur le problème d'arrêt introduit par Turing. Il présente une esquisse de preuve démontrant qu'il ne peut pas y avoir de procédure pour déterminer si un programme va s'arrêter. La séance de cours se termine en soulignant les limites des algorithmes dans la résolution de chaque problème.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Concepts associés (32)

Dixième problème de Hilbert

Le dixième problème de Hilbert fait partie de la liste des 23 problèmes posés par David Hilbert en 1900 à Paris, lors de sa conférence au congrès international des mathématiciens. Il énonce : énoncé| X. — De la possibilité de résoudre une équation diophantienne. On donne une équation diophantienne à un nombre quelconque d'inconnues et à coefficients entiers rationnels : On demande de trouver une méthode par laquelle, au moyen d'un nombre fini d'opérations, on pourra distinguer si l'équation est résoluble en nombres entiers rationnels.

Problème du mot pour les groupes

En mathématiques, plus précisément dans le domaine de la théorie combinatoire des groupes, le problème du mot pour un groupe de type fini G est le problème algorithmique de décider si deux mots en les générateurs du groupe représentent le même élément. Plus précisément, si X un ensemble fini de générateurs pour G, on considère le langage formel constitué des mots sur X et son ensemble d'inverses formels qui sont envoyés par l'application naturelle sur l'identité du groupe G.

Oméga de Chaitin

thumb|right|upright=1.2|Un nombre Oméga de Chaitin est une suite de bits représentant, sous forme concentrée, la solution du problème de l'arrêt pour tous les programmes d'une machine de Turing universelle donnée. En théorie algorithmique de l'information, une constante 'Oméga de Chaitin' (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement précise un nombre réel, qui possède la particularité d'être aléatoire et de ne pas être calculable au sens de Turing : un algorithme donné ne permet de calculer qu'un nombre fini de ses décimales.

Machine de Turing universelle

vignette|upright=1.5|Une machine de Turing quelconque M réalise un calcul à partir d'une entrée écrite sur son ruban. Une machine de Turing universelle U simule le calcul de M sur l'entrée de M à partir d'une description de M et de l'entrée de M écrits sur le ruban de U. En informatique, plus précisément en informatique théorique, une machine de Turing universelle est une machine de Turing qui peut simuler n'importe quelle machine de Turing sur n'importe quelle entrée.

Computability

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.

Afficher plus

Séances de cours associées (33)

Théorie de la calculabilité et problème d'arrêt MOOC: Information, Calcul, Communication: Introduction à la pensée informatique

Couvre la théorie de la calculabilité et le problème de l'arrêt dans les algorithmes.

Théorie de calcul : Problèmes Définition et comptage (Dnumérabilité)

Explore la théorie du calcul, mettant l'accent sur la définition des problèmes, le comptage et les limites du calcul algorithmique.

L'indécidabilité : langages récursifs et machines de Turing

Explore l'indécidabilité à travers les langages récursifs, les machines de Turing et le problème de l'arrêt.

Énumérabilité récursive: Machines de Turing et langages indécidables

Couvre les langages énumérables récursivement, les machines de Turing et la construction de langages indécidables.

Théorie de calcul : problèmes indécis

Explore l'existence de fonctions qui ne peuvent pas être calculées, illustrées par des paradoxes célèbres et le concept de problèmes indécis.

Afficher plus

Concepts associés (32)

Dixième problème de Hilbert

Problème du mot pour les groupes

Oméga de Chaitin

Machine de Turing universelle

Computability

Afficher plus