== '''Machine de Turing''' ==

La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

== '''Définition''' ==

La machine de Turing est composée:

- D' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- D’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- Un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

== '''Exemple''' ==

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema.jpg]]

En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par '''l’état 1''', qui lit le symbole '''VIDE''' (une case blanche) puis le remplace par le symbole VIDE puis se déplace à '''gauche'''.

Elle passe à '''l’état 2''', elle remplace le symbole lu par le même symbole et se déplace à '''gauche''' et quand se retrouve tout à droite du nombre et rencontre un symbole '''VIDE''' elle écrit '''VIDE''' et se déplace à '''droite''' .

Elle passe à '''l’état 3''', quand elle lit un symbole '''0''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme, quand elle lit un symbole '''1''' elle écrit '''0''' puis se déplace à '''droite''' et quand elle lit le symbole '''VIDE''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme.

Voici un programme qui ajoute 1 pour n'importe quel nombre. [[Fichier:ajouter_1_turing_v2.txt]]

== '''Machine de Turing universelle ''' ==

La machine de Turing universelle est une machine qui prend en paramètre une autre machine de Turing, ce qui nous permet de faire n’importe quel calculs.
Grâce à la machine de Turing universelle, l'ordinateur peut éditer n'importe quel programme.

Voici un programme qui représente une machine de Turing universelle.[[Fichier:machine_universelle.txt]]

Machines de Turing

2022-05-23T13:27:43Z

Echollet : /* Machine de Turing universelle */

== '''Machine de Turing''' ==

La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

== '''Définition''' ==

La machine de Turing est composée:

- D' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- D’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- Un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

== '''Exemple''' ==

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema.jpg]]

En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par '''l’état 1''', qui lit le symbole '''VIDE''' (une case blanche) puis le remplace par le symbole VIDE puis se déplace à '''gauche'''.

Elle passe à '''l’état 2''', elle remplace le symbole lu par le même symbole et se déplace à '''gauche''' et quand se retrouve tout à droite du nombre et rencontre un symbole '''VIDE''' elle écrit '''VIDE''' et se déplace à '''droite''' .

Elle passe à '''l’état 3''', quand elle lit un symbole '''0''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme, quand elle lit un symbole '''1''' elle écrit '''0''' puis se déplace à '''droite''' et quand elle lit le symbole '''VIDE''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme.

Voici un programme qui ajoute 1 pour n'importe quel nombre. [[Fichier:ajouter_1_turing_v2.txt]]

== '''Machine de Turing universelle ''' ==

La machine de Turing universelle est une machine qui prend en paramètre une autre machine de Turing, ce qui nous permet de faire n’importe quel calculs.
Grâce à la machine de Turing universelle, l'ordinateur peut éditer n'importe quel programme.
Voici un programme qui représente une machine de Turing universelle.[[Fichier:machine_universelle.txt]]

2022-05-18T10:17:30Z

Echollet :

2022-05-13T10:52:33Z

Echollet :

Machines de Turing

2022-05-13T10:52:05Z

Echollet :

'''Machine de Turing : '''
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

'''Définition :'''
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema.jpg]]

En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par '''l’état 1''', qui lit le symbole '''VIDE''' (une case blanche) puis le remplace par le symbole VIDE puis se déplace à '''gauche'''.

Elle passe à '''l’état 2''', elle remplace le symbole lu par le même symbole et se déplace à '''gauche''' et quand se retrouve tout à droite du nombre et rencontre un symbole '''VIDE''' elle écrit '''VIDE''' et se déplace à '''droite''' .

Elle passe à '''l’état 3''', quand elle lit un symbole '''0''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme, quand elle lit un symbole '''1''' elle écrit '''0''' puis se déplace à '''droite''' et quand elle lit le symbole '''VIDE''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme.

'''Machine de Turing universelle :'''

La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

'''Machine de Turing non-déterministe :'''

Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

[[Fichier:schema2.jpg]]
- soit elle peut exécuter q0 2x

- soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

[[Fichier:schema3.jpg]]
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

Machines de Turing

2022-05-13T10:50:27Z

Echollet :

'''Machine de Turing : '''
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

'''Définition :'''
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema.jpg]]

En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par '''l’état 1''', qui lit le symbole '''VIDE''' (une case blanche) puis le remplace par le symbole VIDE puis se déplace à '''gauche'''.

Elle passe à '''l’état 2''', elle remplace le symbole lu par le même symbole et se déplace à '''gauche''' et quand se retrouve tout à droite du nombre et rencontre un symbole '''VIDE''' elle écrit '''VIDE''' et se déplace à '''droite''' .

Elle passe à '''l’état 3''', quand elle lit un symbole '''0''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme, quand elle lit un symbole '''1''' elle écrit '''0''' puis se déplace à '''droite''' et quand elle lit le symbole '''VIDE''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme.

'''Machine de Turing universelle :'''

La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

'''Machine de Turing non-déterministe :'''

Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

[[Fichier:schema2.jpg]]
- soit elle peut exécuter q0 2x

- soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

Machines de Turing

2022-05-13T10:49:37Z

Echollet :

'''Machine de Turing : '''
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

'''Définition :'''
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema.jpg]]

En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par '''l’état 1''', qui lit le symbole '''VIDE''' (une case blanche) puis le remplace par le symbole VIDE puis se déplace à '''gauche'''.

Elle passe à '''l’état 2''', elle remplace le symbole lu par le même symbole et se déplace à '''gauche''' et quand se retrouve tout à droite du nombre et rencontre un symbole '''VIDE''' elle écrit '''VIDE''' et se déplace à '''droite''' .

Elle passe à '''l’état 3''', quand elle lit un symbole '''0''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme, quand elle lit un symbole '''1''' elle écrit '''0''' puis se déplace à '''droite''' et quand elle lit le symbole '''VIDE''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme.

'''Machine de Turing universelle :'''

La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

'''Machine de Turing non-déterministe :'''

Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

[[Fichier:schema2.jpg]]
soit elle peut exécuter q0 2x
soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

Machines de Turing

2022-05-13T10:47:56Z

Echollet :

'''Machine de Turing : '''
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

'''Définition :'''
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema.jpg]]

En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par '''l’état 1''', qui lit le symbole '''VIDE''' (une case blanche) puis le remplace par le symbole VIDE puis se déplace à '''gauche'''.

Elle passe à '''l’état 2''', elle remplace le symbole lu par le même symbole et se déplace à '''gauche''' et quand se retrouve tout à droite du nombre et rencontre un symbole '''VIDE''' elle écrit '''VIDE''' et se déplace à '''droite''' .

Elle passe à '''l’état 3''', quand elle lit un symbole '''0''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme, quand elle lit un symbole '''1''' elle écrit '''0''' puis se déplace à '''droite''' et quand elle lit le symbole '''VIDE''' elle écrit '''1''' puis se déplace à '''droite''' et c’est la '''FIN''' du programme.

'''Machine de Turing universelle :'''

La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

'''Machine de Turing non-déterministe :'''

Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

[[Fichier:schema1.jpg]]
soit elle peut exécuter q0 2x
soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

Fichier:Schema2.jpg

2022-05-13T10:47:07Z

Echollet : Echollet a téléversé une nouvelle version de Fichier:Schema2.jpg

2022-05-12T16:38:00Z

Echollet :

Machines de Turing

2022-05-12T16:37:50Z

Echollet :

Machine de Turing :
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

Définition :
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema.jpg]]
En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par l’état 1, qui lit le symbole VIDE (une case blanche) puis le remplace par le symbole VIDE puis se déplace à gauche.
Elle passe à l’état 2, elle remplace le symbole lu par le même symbole et se déplace à gauche et quand se retrouve tout à droite du nombre et rencontre un symbole VIDE elle écrit VIDE et se déplace à droite
Elle passe à l’état 3, quand elle lit un symbole 0 elle écrit 1 puis se déplace à droite et c’est la FIN du programme, quand elle lit un symbole 1 elle écrit 0 puis se déplace à droite et quand elle lit le symbole VIDE elle écrit 1 puis se déplace à droite et c’est la FIN du programme.

Machine de Turing universelle :
La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

Machine de Turing non-déterministe :
Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

↓ ↷
a .
q0 q1

soit elle peut exécuter q0 2x
soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

Machines de Turing

2022-05-12T16:35:00Z

Echollet :

Machine de Turing :
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

Définition :
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:schema_turing1.jpg]]
En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par l’état 1, qui lit le symbole VIDE (une case blanche) puis le remplace par le symbole VIDE puis se déplace à gauche.
Elle passe à l’état 2, elle remplace le symbole lu par le même symbole et se déplace à gauche et quand se retrouve tout à droite du nombre et rencontre un symbole VIDE elle écrit VIDE et se déplace à droite
Elle passe à l’état 3, quand elle lit un symbole 0 elle écrit 1 puis se déplace à droite et c’est la FIN du programme, quand elle lit un symbole 1 elle écrit 0 puis se déplace à droite et quand elle lit le symbole VIDE elle écrit 1 puis se déplace à droite et c’est la FIN du programme.

Machine de Turing universelle :
La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

Machine de Turing non-déterministe :
Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

↓ ↷
a .
q0 q1

soit elle peut exécuter q0 2x
soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

Machines de Turing

2022-05-12T16:33:55Z

Echollet :

Machine de Turing :
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

Définition :
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:shema_turing1.jpg]]
En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }

[[Fichier:exemple1.jpg]]

La machine commence par l’état 1, qui lit le symbole VIDE (une case blanche) puis le remplace par le symbole VIDE puis se déplace à gauche.
Elle passe à l’état 2, elle remplace le symbole lu par le même symbole et se déplace à gauche et quand se retrouve tout à droite du nombre et rencontre un symbole VIDE elle écrit VIDE et se déplace à droite
Elle passe à l’état 3, quand elle lit un symbole 0 elle écrit 1 puis se déplace à droite et c’est la FIN du programme, quand elle lit un symbole 1 elle écrit 0 puis se déplace à droite et quand elle lit le symbole VIDE elle écrit 1 puis se déplace à droite et c’est la FIN du programme.

Machine de Turing universelle :
La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

Machine de Turing non-déterministe :
Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

↓ ↷
a .
q0 q1

soit elle peut exécuter q0 2x
soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

Fichier:Exemple1.jpg

2022-05-12T16:32:04Z

Echollet :

Machines de Turing

2022-05-12T16:31:43Z

Echollet :

Machine de Turing :
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

Définition :
La machine de Turing est composée:

- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches

- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure

- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci

- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre

[[Fichier:shema_turing1.jpg]]
En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

Exemple de table de transition :
[[Fichier:tableau_etat1.png]]

Exemple pour ajouter 1 au nombre : { 10101 }
[[Fichier:exemple1.jpg]]
Etape
Etat
Ruban

Etape
Etat
Ruban

Etape
Etat
Ruban
1
e1
_10101

4
e2
10101

7
e2
10101_
2
e2
10101

5
e2
10101

8
e3
10100
3
e2
10101

6
e2
10101

9
e3
10110 FIN

La machine commence par l’état 1, qui lit le symbole VIDE (une case blanche) puis le remplace par le symbole VIDE puis se déplace à gauche.
Elle passe à l’état 2, elle remplace le symbole lu par le même symbole et se déplace à gauche et quand se retrouve tout à droite du nombre et rencontre un symbole VIDE elle écrit VIDE et se déplace à droite
Elle passe à l’état 3, quand elle lit un symbole 0 elle écrit 1 puis se déplace à droite et c’est la FIN du programme, quand elle lit un symbole 1 elle écrit 0 puis se déplace à droite et quand elle lit le symbole VIDE elle écrit 1 puis se déplace à droite et c’est la FIN du programme.

Machine de Turing universelle :
La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

Machine de Turing non-déterministe :
Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

↓ ↷
a .
q0 q1

soit elle peut exécuter q0 2x
soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.

2022-05-12T16:01:56Z

Echollet :

Machine de Turing

Machine de Turing :
La machine de Turing à été inventée par Alan Turing en 1936.
Elle représente le fonctionnement d’un appareil mécanique de calcul comme par exemple un ordinateur, c’est ce qui a donner une idée précise du concept de l’algorithme
Le concept de Machine de Turing a été inventé avant l’ordinateur. Elle devait représenter une personne virtuelle qui devait exécuter une procédure définie par l’utilisateur qui consiste à changer le contenu des cases d’un ruban infini, et en choisissant ce contenu parmi un ensemble fini de symbole.

Un problème = une solution

Définition :
La machine de Turing est composée:
- d' un ruban infini à droite et à gauche sur lequel il y a des cases, chaque case peut contenir des symboles. Si il n’y a pas de symboles, c’est des cases blanches
- d’une tête de lecture / écriture : lit et écrit les symboles sur le rubans puis se déplace à droite ou à gauche selon la procédure
- un registre d’état : c’est un registre mémorise l’état dans lequel il se trouve, il existe un spécial, c’est l’état de départ qui initialise la machine avant l'exécution de celle ci
- Table d’action : la table indique à la machine quel symbole écrire et comment se déplacer la tête de lecture et elle dit aussi le nouvel état à exécuter. Si il n’y a plus d’action à faire, la machine s’arrête.

Exemple:

La machine de Turing à pour symbole {‘0’,’1’} et un autre qui correspond au symbole de la case vide. Nous avons en entrée de cette machine une suite de 1 et de 0. La tête de lecture/écriture se trouve à gauche de la suite de nombre
En exemple on va ajouter 1 à un nombre binaire. Pour cette fonction il nous faut 3 états.

Exemple de table de transition :
Etat
Symbole lu
Symbole écrit
Mouvement
Nouvel état
E1
VIDE
VIDE
gauche
e2
E2
0
0
gauche
e2
|
1
1
gauche
e2
|
VIDE
VIDE
droite
e3
E3
0
1
droite
FIN
|
1
0
droite
e3
|
VIDE
1
droite
FIN

Exemple pour ajouter 1 au nombre : { 10101 }

Etape
Etat
Ruban

Etape
Etat
Ruban

Etape
Etat
Ruban
1
e1
_10101

4
e2
10101

7
e2
10101_
2
e2
10101

5
e2
10101

8
e3
10100
3
e2
10101

6
e2
10101

9
e3
10110 FIN

La machine commence par l’état 1, qui lit le symbole VIDE (une case blanche) puis le remplace par le symbole VIDE puis se déplace à gauche.
Elle passe à l’état 2, elle remplace le symbole lu par le même symbole et se déplace à gauche et quand se retrouve tout à droite du nombre et rencontre un symbole VIDE elle écrit VIDE et se déplace à droite
Elle passe à l’état 3, quand elle lit un symbole 0 elle écrit 1 puis se déplace à droite et c’est la FIN du programme, quand elle lit un symbole 1 elle écrit 0 puis se déplace à droite et quand elle lit le symbole VIDE elle écrit 1 puis se déplace à droite et c’est la FIN du programme.

Machine de Turing universelle :
La machine de Turing universelle est une machine qui peut faire n’importe quel calculs, tout ce qui est calculable, n’importe quelle fonction récursive et peut analyser n’importe quel langage récursive

Machine de Turing non-déterministe :
Le but d’une machine de Turing non déterministe c’est pour chaque point c’est faire un choix, elle peut exécuter au moins 2 transitions différentes à un endroit.

↓ ↷
a .
q0 q1

soit elle peut exécuter q0 2x
soit elle peut exécuter q1

ex :
Le langage sur {a,b} des mots dont la 6ème lettre en partant de la fin est un a est-il régulier ?

a,b
⟳ a a,b a,b a,b a,b a,b
→ O → O → O → O → O → O → O
6e 5e 4e 3e 2nd 1er
Le langage est régulier
Il existe un automate déterministe le reconnaissant avec au plus 128 états (automates minimal en à 64)
Machine de Turing Non-déterministe permettent de façon simple de donner des indications sur la complexité déterministe d’un problème ou comment l’aborder efficacement

Def : Une machine de Turing non déterministe décide un langage L, si tout :
il n’y a aucun calcul infini
Un mot est dans L si et seulement s’il existe un calcul pour ce mot passant par une configuration finale

Une machine de Turing non déterministe est utile pour optimiser, transport routier, ordonnancement de tâche, gestion d’usine… C’est un outil théorique et qui donne beaucoup d'informations sur la nature du problème et sur comment l’aborder mais ne résout pas le problème.