Super-Turing ?

[invite0a547b27]

Salut,

Soit une machine de Turing à plusieurs états, nous sommes capables une fois une machine de Turing lancer à faible vitesse d'écrire sur une bande annexe l'état dans le quelle se trouve la machine.
Existe-t-il une machine de Turing capable d'en faire autant, pour n'importe qu'elle autre machine de Turing ?

La seule chose au quelle cette machine a accès est le ruban, or 2 machines de Turing aux états très différents peuvent produire les même ruban, donc cela n'est pas calculable au sens de Church mais pourtant très facilement faisable.

Les super-T possèdent une bande d'écriture en plus ou elle note les changements d'états.

Une machine super-T n'est rien d'autre qu'une machine qui garde les traces des ces calculs.

Nos ordinateurs sont-ils des super-T ?
-----

[invite0a547b27]

Si la réponse est oui alors il n'existe pas de fonction à sens unique et donc tout protocole de sécurité même prouvé impossible n'est pas sur avec de tel machine.
Car la preuve de sécurité est faîte avec des machines de Turing simple.

Conclusion, les super-Turing serait de super-espions.

[Deedee81]

Salut,

Il me semble que ce que tu appelles Turing sont les "machines de Turing universelles". Très utilisées en logique ou dans la théorie de la complexité, etc...

La réponse est donc oui, ça existe.

Et non, il n'existe pas de fonction de protocole asymétrique à sens unique. Tout code peut être cassé. L'astuce consiste non pas à concevoir un protocole incassable mais trop dur à casser car nécessitant des machines totalement hors de portée pour le moment (à moins de disposer de calculateur quantique).

A noter que la conjecture P!=NP garantissant cette sécurité classique n'est pas démontré (ni infirmé et il y a un million de dollars pour celui qui démontre la conjecture ou son contraire, ça fait partie des prix du milénium).

Le seul algo strictement incassable est le "one pad". Mais cela nécessite de faire transiter les clés par un moyen sécurisé alternatif, par exemple (au moins à une époque) par la valise diplomatique (je ne sais pas si le one pad est encore utilisé).

Même la cryptographie quantique n'est pas inviolable mais on peut rendre le protocole aussi sûr qu'on veut jusqu'à rendre le risque plus proche de zéro que les records actuels de zéro absolu

[Superbenji]

Bonjour,

Je ne suis pas sûr d'avoir bien compris, mais ce que tu décris n'est rien d'autre qu'une machine de Turing
universelle qui enregistre sur son ruban un historique de la description de la machine simulée. C'est
parfaitement calculable pour toute machine, si.

Mais cela ne fera pas de cette machine universelle une super-T, elle est Turing-équivalente. Le contraire
serais contradictoire puisque cette machine peut très bien être elle même simulée par une autre.

Quelque soit le nombre fini de ruban, cela n'y changera rien. La seule solution pour avoir une super-T
est que la machine possède un nombre infini d'états, ou un alphabet de ruban infini, ou puisse calculer sur
des nombre transfini d'étapes, etc... On peut aussi considérer une machine avec un oracle répondant a des
questions non Turing-calculable.

Donc non, nos ordinateurs ne sont que Turing-équivalent (sans tenir compte de la finitude de la mémoire et du temps de calcul de ceux ci).

[A voir en vidéo sur Futura]

[invite0a547b27]

Salut,

1/Il me semble que ce que tu appelles Turing sont les "machines de Turing universelles". Très utilisées en logique ou dans la théorie de la complexité, etc...

2/La réponse est donc oui, ça existe.

3/Et non, il n'existe pas de fonction de protocole asymétrique à sens unique. Tout code peut être cassé. L'astuce consiste non pas à concevoir un protocole incassable mais trop dur à casser car nécessitant des machines totalement hors de portée pour le moment (à moins de disposer de calculateur quantique).

A noter que la conjecture P!=NP garantissant cette sécurité classique n'est pas démontré (ni infirmé et il y a un million de dollars pour celui qui démontre la conjecture ou son contraire, ça fait partie des prix du milénium).

Le seul algo strictement incassable est le "one pad". Mais cela nécessite de faire transiter les clés par un moyen sécurisé alternatif, par exemple (au moins à une époque) par la valise diplomatique (je ne sais pas si le one pad est encore utilisé).

Même la cryptographie quantique n'est pas inviolable mais on peut rendre le protocole aussi sûr qu'on veut jusqu'à rendre le risque plus proche de zéro que les records actuels de zéro absolu

Salut,

1/Effectivement je me suis avancé super-T est calculable car elle peut-être simuler par une machine de Turing.

2/La question est plus tôt est ce que les PC sont des super-T ? il me semble que oui.

3/Une fonction à sens unique n'est pas impossible à casser elle l'est mais par des algo exponentiels.

[invite0a547b27]

Bonjour,

Je ne suis pas sûr d'avoir bien compris, mais ce que tu décris n'est rien d'autre qu'une machine de Turing
universelle qui enregistre sur son ruban un historique de la description de la machine simulée. C'est
parfaitement calculable pour toute machine, si.

Mais cela ne fera pas de cette machine universelle une super-T, elle est Turing-équivalente. Le contraire
serais contradictoire puisque cette machine peut très bien être elle même simulée par une autre.

Quelque soit le nombre fini de ruban, cela n'y changera rien. La seule solution pour avoir une super-T
est que la machine possède un nombre infini d'états, ou un alphabet de ruban infini, ou puisse calculer sur
des nombre transfini d'étapes, etc... On peut aussi considérer une machine avec un oracle répondant a des
questions non Turing-calculable.

1/Donc non, nos ordinateurs ne sont que Turing-équivalent (sans tenir compte de la finitude de la mémoire et du temps de calcul de ceux ci).

Bonsoir,

1/Le concept de super-T est intéressant car une telle machine ne peut pas utiliser de manière effective de fonction à sens unique et donc tout protocole de sécurité y est cassable, car on peut y retrouver les traces des calculs antérieurs.

[Deedee81]

Salut,

Je ne comprend pas trop bien ce que tu entends par "super Turing" (une petite définition formelle serait sympa). Mais en supposant que c'est juste des machines de Turing universelle, alors oui les ordinateurs sont des "Super Turing" (mais avec une mémoire limitée. Les machines de Turing sont des machines théoriques avec une bande mémoire infinie. Mais si on limite la bande, on sait les réaliser effectivement. J'en avais même vu une fabriquée avec, si ma mémoire est bonne, du Fisher Technik). Ce sont des calculateurs universels, c'est même dans ce but qu'on les a inventés.

Un truc qui pourrait peut être t'intéresser :
http://fr.wikipedia.org/wiki/Th%C3%A8se_de_Church

Et des articles connexes utiles :
http://fr.wikipedia.org/wiki/Calculabilit%C3%A9
http://fr.wikipedia.org/wiki/Om%C3%A9ga_de_Chaitin

[Médiat]

J'en avais même vu une fabriquée avec, si ma mémoire est bonne, du Fisher Technik).

Bonjour
l'ENS Lyon en a construite une en Lego : http://www.ens-lyon.eu/actualites/la...ON-FR-evenemen

[invite0a547b27]

Salut,

Je ne comprend pas trop bien ce que tu entends par "super Turing" (une petite définition formelle serait sympa). Mais en supposant que c'est juste des machines de Turing universelle, alors oui les ordinateurs sont des "Super Turing" (mais avec une mémoire limitée. Les machines de Turing sont des machines théoriques avec une bande mémoire infinie. Mais si on limite la bande, on sait les réaliser effectivement. J'en avais même vu une fabriquée avec, si ma mémoire est bonne, du Fisher Technik). Ce sont des calculateurs universels, c'est même dans ce but qu'on les a inventés.

Un truc qui pourrait peut être t'intéresser :
http://fr.wikipedia.org/wiki/Th%C3%A8se_de_Church

Et des articles connexes utiles :
http://fr.wikipedia.org/wiki/Calculabilit%C3%A9
http://fr.wikipedia.org/wiki/Om%C3%A9ga_de_Chaitin

Salut,

Une S-T est une machine de Turing avec une bande d'écriture supplémentaire où est noté les états par lesquels est passés cette machine.
C'est un peu comme si l'on avait un processeur qui enregistrerait toute les opérations demandaient et avec un tel matériel toute calcul de fonction y est réversible il se suffit de lire les opérations effectuer. Et donc impossible d'y faire de la cryptographie sûr.

[invite0a547b27]

Une définition plus formelle serait :
soit la machine de Turing définit par (e_f(i),b_(2*i))->(nouvelle état : e_g(i),écrire : b_(2*i+1),direction : d_i) alors la s-T dérivé comporte une bande d'écriture en plus tel que e_f(i)->(e_g(i),e_f(i),Droite).

[invite0a547b27]

Une définition plus formelle serait :
soit la machine de Turing définit par (e_f(i),b_(2*i))->(nouvelle état : e_g(i),écrire : b_(2*i+1),direction : d_i) alors la s-T dérivé comporte une bande d'écriture en plus tel que (e_f(i),lu dans la bande classique : b_(2*i))->(e_g(i),e_f(i),Droite).

Petit oubli de ma part.

[Deedee81]

l'ENS Lyon en a construite une en Lego

Merci, j'avais hésité sur la marque

Une S-T est une machine de Turing avec une bande d'écriture supplémentaire où est noté les états par lesquels est passés cette machine.

D'accord, merci.

Il existe de nombreuses variantes de Turing, certaines avec des multi-bandes.

La plupart sont équivalentes aux Turing classiques (dans la mesure où toute machine d'un type peut être programmée avec un autre type, un peut comme un programme sur un IBM peut aussi être écrit pour une HP).

Les exceptions sont :
- des machines avec certaines contraintes les empêchant d'être universelles
- des possibilités non calculables, comme un vrai générateur aléatoire par exemple (on a aussi parlé des Oracles, très utilisés dans l'informatique théorique).

[Superbenji]

Salut,

Je ne comprend pas trop bien ce que tu entends par "super Turing" (une petite définition formelle serait sympa). Mais en supposant que c'est juste des machines de Turing universelle, alors oui les ordinateurs sont des "Super Turing"

Bonjour,
Le concept de super-Turing ou d'hypercalcul c'est normalement ça:
http://fr.wikipedia.org/wiki/Hypercalcul
J'ai cru que c'est ce dont il parlait, mais apparement il y donne un autre sens.

[invite0a547b27]

Bonjour,
Le concept de super-Turing ou d'hypercalcul c'est normalement ça:
http://fr.wikipedia.org/wiki/Hypercalcul
J'ai cru que c'est ce dont il parlait, mais apparement il y donne un autre sens.

Bonjour,

Effectivement, ce qui m'intéresse dans ces machines c'est que toute tentative de cryptographie sûr y est illusoire.

D'où ma question est-ce que les PC le sont également ?

Si oui inutile de rêver à de la crypto sûr civile...

[Superbenji]

Bonjour,

Effectivement, ce qui m'intéresse dans ces machines c'est que toute tentative de cryptographie sûr y est illusoire.

D'où ma question est-ce que les PC le sont également ?

Si oui inutile de rêver à de la crypto sûr civile...

En fait tu songe plutôt a un idée de calcul réversible, non ? Si je comprends bien.
Par exemple chez les automates cellulaire, dans le paragraphe sur les automates réversible:
http://fr.wikipedia.org/wiki/Automat...C3.A9versibles

[Deedee81]

Effectivement, ce qui m'intéresse dans ces machines c'est que toute tentative de cryptographie sûr y est illusoire.
D'où ma question est-ce que les PC le sont également ?

J'avais déjà répondu plus haut. En dehors du "one pad" (dont la fiabilité totale est démontrée mais de toute façon évidente), aucun système n'est incassable. Et cela s'applique aux PC.

Mais tout dépend de ce que tu appelles "cryptographie sûre". "Sûr" en cryptographie est synonyme de "difficile à casser" et pas "inviolable".

[invite0a547b27]

Je parle de la crypto qui se base sur l'existence de fonction à sens unique, c'est à dire la crypto-moderne.

http://fr.wikipedia.org/wiki/Fonctio...A0_sens_unique

[invite0a547b27]

En fait tu songe plutôt a un idée de calcul réversible, non ? Si je comprends bien.
Par exemple chez les automates cellulaire, dans le paragraphe sur les automates réversible:
http://fr.wikipedia.org/wiki/Automat...C3.A9versibles

Non pas exactement, je pense à des machines de Turing qui garde une trace de leurs calculs tel que
Si T_a=T_b, c<>d on calcule T_a(c) et T_b(d) alors T_a<>T_b.

[invite0a547b27]

Non pas exactement, je pense à des machines de Turing qui garde une trace de leurs calculs tel que
Si T_a=T_b, c<>d on calcule T_a(c) et T_b(d) alors T_a<>T_b.

Il me semble qu'une tel machine ne puisse pas être simuler par une machine Turing, non ?

[invite0a547b27]

doublons doublons

[Deedee81]

Je parle de la crypto qui se base sur l'existence de fonction à sens unique, c'est à dire la crypto-moderne.

http://fr.wikipedia.org/wiki/Fonctio...A0_sens_unique

Les fonctions à sens uniques sont mal nommées. Elles ne sont pas à sens uniques mais seulement très difficiles à calculer dans "l'autre sens".

Il me semble qu'une tel machine ne puisse pas être simuler par une machine Turing, non ?

Si, si.

[invite0a547b27]

Les fonctions à sens uniques sont mal nommées. Elles ne sont pas à sens uniques mais seulement très difficiles à calculer dans "l'autre sens".



1/Si, si.

Ce n'est pas moi qui ait choisis le nom.

1/ Comment procèdes tu alors ?
En effet Ta=Tb si leurs tables d'action est identiques.
Or Sta=Stb si leurs tables d'action identiques et ruban identique...
Supposons qu'il existe Ta qui simule Sta et Tb qui simule Stb tel que Sta=Stb alors Ta=Tb donc ils ont même table d'action.
Stb(c) et Sta(d) tel que c<>d alors Stb<>Sta donc Ta<>Tb or on ne peut modifier la table d'action d'une machine de Turing par définition ->absurde.

[Deedee81]

Salut,

Ce n'est pas moi qui ait choisis le nom.

Je n'ai pas dit ça

1/ Comment procèdes tu alors ?
En effet Ta=Tb si leurs tables d'action est identiques.
Or Sta=Stb si leurs tables d'action identiques et ruban identique...
Supposons qu'il existe Ta qui simule Sta et Tb qui simule Stb tel que Sta=Stb alors Ta=Tb donc ils ont même table d'action.
Stb(c) et Sta(d) tel que c<>d alors Stb<>Sta donc Ta<>Tb or on ne peut modifier la table d'action d'une machine de Turing par définition ->absurde.

J'avoue que je n'ai rien compris à ta question !!!!!

Si tu veux parler de "comment simuler une super Turing avec une Turing" il ne s'agit évidemment pas d'avoir des machines identiques. Donc, leur tables d'actions peuvent être très différentes.

Le principe est de trouver un codage permettant de représenter sur un seul ruban le contenu des deux rubans de la Super Turing (par exemple une case sur deux sur la bande unique. Ca ne marche que parce que ces bandes sont infinies. C'est l'hôtel de Hilbert version Turing ). Puis une table d'action (éventuellement très complexe) et un programme initial permettant de reproduire ce que fait la Super Turing avec ce seul ruban et son codage particulier.

Il existe des méthodes de construction systématique, mais elles sont assez compliquées. On trouve ça sur le net (j'ai déjà lu mais c'était il y a quinze ans. Je ne sais plus où c'est. Mais on doit trouver facilement, il y a beaucoup de cours sur Turing sur le net).

[invite0a547b27]

Salut,



Je n'ai pas dit ça




J'avoue que je n'ai rien compris à ta question !!!!!

1/Si tu veux parler de "comment simuler une super Turing avec une Turing" il ne s'agit évidemment pas d'avoir des machines identiques. Donc, leur tables d'actions peuvent être très différentes.

Le principe est de trouver un codage permettant de représenter sur un seul ruban le contenu des deux rubans de la Super Turing (par exemple une case sur deux sur la bande unique. Ca ne marche que parce que ces bandes sont infinies. C'est l'hôtel de Hilbert version Turing ). Puis une table d'action (éventuellement très complexe) et un programme initial permettant de reproduire ce que fait la Super Turing avec ce seul ruban et son codage particulier.

Il existe des méthodes de construction systématique, mais elles sont assez compliquées. On trouve ça sur le net (j'ai déjà lu mais c'était il y a quinze ans. Je ne sais plus où c'est. Mais on doit trouver facilement, il y a beaucoup de cours sur Turing sur le net).

Salut,

1/ Exactement.
Je pense que cela n'est pas possible car pour cela il faudrait qu'une machine de Turing soit caractériser par sa table d'action et son ruban ce qui n'est pas le cas...