Séance de cours

Machines de Turing: Basics

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.

Description

Cette séance de cours présente les machines de Turing comme de simples automates avec un nombre fini d'états et une bande pour la lecture. Contrairement aux automates finis ou aux automates pushdown, les machines de Turing ont la capacité de manipuler la bande en se déplaçant à gauche ou à droite, en lisant et en écrivant des symboles. La séance de cours couvre la fonction de transition, le concept d'états, l'alphabet de bande, et l'importance des configurations dans l'exécution d'une machine de Turing. Il aborde également le déterminisme, le non-déterminisme et la relation entre les problèmes résolubles par les machines de Turing déterministes et non déterministes.

Source officielle

Concepts associés (32)

Machine de Turing

En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.

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.

Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.

Machine de Turing non déterministe

Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné. Alors que, connaissant le caractère lu sur le ruban et l'état courant, une machine de Turing déterministe dispose d'au plus une transition possible, une machine de Turing non déterministe peut en avoir plusieurs.

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

Afficher plus

Séances de cours associées (32)

Définition formelle des turbines

Explore la définition théorique du calcul et introduit les machines Turing.

Turing Machines: Langues récursives

Explore les machines Turing, les langages récursifs, l'indécidabilité et l'élimination des symboles.

Exemple de machine de turing: Test pour des nombres égaux

Démontre une machine de test Turing pour des nombres égaux en utilisant l'entrée binaire.

Turing Machines: Langues récursives

Couvre les machines Turing, les langages récursifs, l'indécidabilité et les exécutions infinies en théorie computationnelle.

Machines de turing : Décidabilité et théorie de la récursion

Explore la décidabilité dans les machines Turing et les langages récursifs.

Afficher plus

Concepts associés (32)

Machine de Turing

Machine de Turing universelle

Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.

Machine de Turing non déterministe

Theory of computation

Afficher plus