Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Turing Machines: Langues récursives

Description

Cette séance de cours couvre le concept de Turing machines, les langages récursifs, l'indécidabilité, et la séquence d'état initial. Il explique la configuration de la tête, de l'alphabet et de la fonction de transition. La séance de cours se penche également sur l'élimination des symboles et le mouvement de la tête.

Source officielle

Concepts associés (31)

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

Alphabet

thumb|Lettres de l'alphabet phénicien. Un alphabet (de alpha et bêta, les deux premières lettres de l’alphabet grec) est un système d'écriture constitué d'un ensemble de symboles dont chacun représente, par exemple, un des phonèmes d’une langue. Chacun des symboles d'un alphabet ou graphèmes, est appelé « lettre ». Dans les cas les plus simples, chaque lettre correspond à un phonème de la langue et inversement.

Langage récursif

En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing-decidable. Il y a plusieurs définitions équivalentes de langage récursif. On peut définir cette notion directement, comme une généralisation de celle d'ensemble récursif (des sous-ensembles d'entiers ou de uples d'entiers), ou passer par des codages dans les entiers, en utilisant la théorie de la calculabilité.

Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages.

Latin alphabet

The Latin alphabet, also known as the Roman alphabet, is the collection of letters originally used by the ancient Romans to write the Latin language. Largely unaltered with the exception of extensions (such as diacritics), it forms the Latin script that is used to write many modern European languages, including English. With modifications, it is also used for other alphabets, such as the Vietnamese alphabet. Its modern repertoire is standardised as the ISO basic Latin alphabet.

Afficher plus

Séances de cours associées (31)

Indécidabilité: Partie 1

Introduit l'indécidabilité dans les langages récursifs et les machines Turing, montrant des langages sans reconnaissance algorithmique.

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.

Turing Machines: Langues récursives

Explore les machines Turing, les langages récursifs, et la décidabilité dans la théorie du calcul.

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.

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 (31)

Machine de Turing

Alphabet

Langage récursif

Recursively enumerable language

Latin alphabet

Afficher plus