Machine de Quentin

Quentino37

Bonjour, ayant découvert le fonctionnement des ordinateurs, et les machines de Turing grâce aux Étincelles du palais de la découverte, j'ai eu une idée ce soir (pour être plus précis je voulais déjà le faire depuis longtemps mais j'ai commencé à y réfléchir vraiment ce soir), de faire un ordinateur programmable dans le jeu Minecraft, je suppose que je ne commencerai jamais ou finirai jamais par manque de temps, mais cela m'a fait réfléchir au fonctionnement de mon "langage de programmation" et le fonctionnement général que j'utiliserai pour que l'ordinateur soit le plus simple à faire, j'avais plusieurs idées partant un peu dans tout les sens mais hélas pas de très bonnes idées... Puis j'ai eu une idée plus théorique que pratique, 
On a une liste d'éléments, valant à la base 0 qui peuvent valoir 0 ou 1.
Il existe deux instructions possibles : 
1) Donner comme valeur à l'élément numéro C la sortie obtenue avec un non-et en prenant en porte d'entrée la valeur de l'élément de la liste A et l'élément B 
C=Non-et(A,B)
2) Revenir à la ligne numéro D (de mon programme, une instruction par ligne) si la valeur de l'élément numéro E est égale à 1.
Aller à(E) 
Puisque qu'avec un non et on peut faire la porte logique que l'on veut, je me demandais si avec "mon" système, je pouvais programmer ce que je voulais en prenant en entrée une partie de la mémoire et en sortie une autre... (exemple calculer pi puissance n en binaire ou programmer un jeu comme Tetris si on attribue un pixel à un/groupe d'éléments de la mémoire (en supposant que chaque ligne prenne un certain temps) ?
Je sais qu'il y a des choses non-calculables avec la machine de Turing donc pareil pour mon truc mais où sont les limites de la machine ?
PS.
1) C'est sûrement mal expliqué.
2) C'est sûrement bourré de fautes d'orthographe !
3) Ma question est sûrement très bête...

nicolas.patrois

Essaie d’insérer le langage minimaliste Brainfuck dans Minecraft.

Quentino37

nicolas.patrois

J'ai regardé ce que c'était et c'est une très bonne idée ! Par contre j'ai encore un léger truc que je n'ai pas compris. Quand le compteur de la case atteint 255 (1 octet) et que l'on incrémente 1, que se passe-t-il ?

dp

La cellule repasse à zéro. C’est pourquoi les instructions [+] ou [-] (que l’on peut lire « tant que la cellule n’est pas nulle : incrémenter (+) ou décrémenter (-) »), par exemple, sont utilisées pour remettre la cellule à zéro.
En réalité dans les interpréteurs un peu sophistiqués, ces instructions sont même directement simplifiées en « mettre 0 dans la cellule » évitant ainsi toute l'étape d'incrémentation ou de décrémentation et économisant du temps de calcul.

Quentino37

A ok ! Est-ce que je peux donc aussi le faire avec un bit par case ? (Je ne sais donc pas quoi faire de la 8eme instruction économisé...)

dp

Que veux-tu dire par « le faire avec un bit par case » ?

nicolas.patrois

Quentino37 a dit :

J'ai regardé ce que c'était et c'est une très bonne idée ! Par contre j'ai encore un léger truc que je n'ai pas compris. Quand le compteur de la case atteint 255 (1 octet) et que l'on incrémente 1, que se passe-t-il ?

Comme tu veux.

Habituellement, comme le dit dp, on repasse à 0 mais tu fais comme tu veux.

Homo Topi

Un superordinateur récent construit dans Minecraft

Une vidéo sur l'histoire des superordinateurs construits dans Minecraft

Une vidéo sur les circuits logiques et machines à calculer dans Super Mario Maker

En principe, l'environnement d'un jeu vidéo n'est qu'une "sur-couche". Un circuit logique, c'est juste une construction physique dont notre interprétation de son fonctionnement est le même que celui d'une des fonctions logiques naturelles de notre cerveau. Donc c'est une construction physique, dynamique, qui représente une fonction. Il faut 3 choses pour faire ça (dans un jeu vidéo ou non) :

1) une bonne connaissance des fonctions logiques qu'on veut représenter physiquement. Là c'est "juste" des maths.

2) que la physique du jeu vidéo en question permette la dynamique nécessaire au fonctionnement d'un circuit logique. Exemple dans Mario Maker (je préfère, parce que c'est visuel, contrairement à la redstone Minecraft qui ne l'est pas toujours) : pour faire un "switch" qui déclenche une fonction ou un calcul, on peut sauter dans un bloc, le bloc bouge (Mario récupère la pièce), la carapace posée sur le bloc est mise en mouvement, la carapace actionne un autre bloc qui démarre le circuit. C'est un circuit à usage unique : une fois la pièce récupérée, on ne peut plus interagir avec le bloc ni le remettre dans son état initial pour réutiliser la machine (sauf en réinitialisant le niveau, ce qui efface l'utilisation précédente de la mémoire interne du jeu).

3) des éléments dans le jeu dont le comportement peut émuler les fonctions logiques en question. Là, il faut une bonne connaissance du jeu et de la manière dont les éléments du jeu ont été programmés. Peut-être qu'on peut faire un circuit logique à l'aide des préférences qu'ont les zombies à ramasser des blocs (un zombie qui tient un objet peut le lâcher pour en préférer un autre, ça cache une relation d'ordre...), ou des choses comme ça. La redstone pure, je connais moins, mais c'est rempli de choses comme ça évidemment.

dp

@nicolas.patrois Bof car c'est au risque d'être incompatible avec l'existant et d'integer overflows... dans les deux cas c'est pas ouf. M'enfin, oui certes, il peut choisir de s'en ficher totalement et faire comme bon lui semble ; mais il aura de drôles de surprises, ne serait-ce déjà qu'avec les deux exemples que j'ai donné qui sont utilisés dans presque tous les programmes qui se respectent.

nicolas.patrois

Si c’est écrit en Python, pas de risque de dépassement.

En revanche, on perd évidemment [-] et [+].

C’est cependant l’occasion de vérifier ce que la machine de Minecraft a dans le ventre.

Foys

Le langage de programmation (exotique) le plus simple imaginable est la "logique combinatoire" de Moses Schönfinkel et Haskell Curry.

1°) Fixons un ensemble $V$ (par exemple l'ensemble des chaînes de caractères ne contenant pas $),(,K$ ni $S$). Les termes de ce langage sont:

-une des deux constantes $S,K$

-un élément de $V$

-$\bf x (y)$ où $\bf x,y$ sont des termes.

2°) Etant donnés deux termes $x,y$ dit que le terme $x$ se réduit élémentairement en $y$ si l'une de ces situations se produit:

(i) $x$ est de la forme $K(a)(b)$ et $y = b$

(ii) $x$ est de la forme $S(a)(b)(c)$ et $y = a(c)(b(c))$

(iii) $x$ est de la forme $a(b)$, $b$ se réduit élémentairement en $b'$ et $y= a(b')$

(iv) $x$ est de la forme $a(b)$, $a$ se réduit élémentairement en $a'$ et $y= a'(b)$

On appelle rédex d'un terme $t$ un terme de la forme $K(u)(v)$ ou $S(u)(v)(w)$ apparaissant dans $t$ et pour résumer la définition précédente, étant donné un terme $t'$, $t$ se réduit élémentairement en $t'$ lorsqu'un de ses rédexes a été remplacé dans $t'$ par la forme correspondante décrite aux points (i) et (ii).

 
3°) On dit qu'un terme $t$ se réduit en $t'$ s'il existe une suite de réductions élémentaires successives passant de $t$ à $t'$ autrement dit des termes $t_0,...,t_n$ tels que $t_{i}$ se réduit élémentairement en $t_{i+1}$ pour tout $i\leq n-1$ (avec éventuellement $n=0$ et $t=t'$). 

4°) On dit qu'un terme est en forme normale si aucune réduction élémentaire ne peut lui être appliquée (autrement dit s'il ne contient aucun rédex). La seule réduction qui peut partir d'un tel terme est la réduction de longueur triviale. 

On dit qu'un terme $q$ est une forme normale d'un terme $p$ lorsque $q$ est une forme normale et que $p$ se réduit en $q$.

5°) Le bon comportement de la réduction est garanti par les deux théorèmes (non triviaux, surtout le deuxième) suivants.

5.1) (Church Rosser) Soient $a,b,c$ trois termes tels que $a$ se réduit en $b$ et en $c$. Alors il existe un terme $d$ tel que $b$ se réduit en $d$ et $c$ se réduit en $d$.

Ce résultat a pour corollaire le suivant: tout terme possède au plus une seule forme normale. Cette forme normale peut s'interpréter comme le résultat du "calcul" du terme en question. Certains termes ne possèdent pas de forme normale. Ce résultat est démontré dans ce livre: https://www.researchgate.net/publication/220688772_Introduction_to_Combinators_and_Lambda-Calculus

5.2) (Réduction la plus à gauche) Soit $t$ un terme ayant une forme normale $u$ (donc unique d'après 5.1).

La suite de réductions élémentaires obtenue à partir de $t$ en remplaçant systématiquement le rédex le plus à gauche dans les termes successifs finit par tomber systématiquement sur $u$.

Ce théorème fournit un mécanisme d'évaluation déterministe des termes (alors que plusieurs réductions sont possibles) et fait donc de la logique combinatoire un langage de programmation.

Il s'agit d'un corollaire d'un autre théorème dit de "standardisation". Pour une preuve on pourra consulter "Combinatory Logic, vol. II" par Curry,Hindley et Seldin.

Avec ce résultat, l'écriture d'un interpréteur de logique combinatoire devient un simple exo de python ou ocaml (ou soyons fous, de Minecraft).

6°) Compilateur de lambda-expressions.

6.1) Pour tout terme $x$, $S(K)(K) (x)$ se réduit en $x$. Une suite de réductions en est donnée par 

$S(K)(K)(x), K(x)(K(x)), x$ par 2° (ii) puis 2° (i).

6.2) étant donné deux termes $t,u$ et une chaîne de caractères $x$, on désignera par $u[x:=t]$ le terme obtenu en remplaçant dans $u$ toutes les occurrences de $x$ par $t$.

6.3) On introduit l'algorithme suivant: si $t$ est un terme et $x$ une chaîne de caractères, on pose $\lambda x(t):=$

-$K(t)$ si $x$ n'apparaît pas dans $t$

-$S(K) (K)$ si $t$ est identique à $x$.

-$p$ si $p$ est un terme dans lequel $x$ ne figure pas et tel que $t = p(x)$

-$S(\lambda x(a))(\lambda x (b))$ dans les autres cas.

Il est immédiat de voir que cette définition (inductive) couvre tous les cas. D'autre part, par induction immédiate sur la longueur des termes on voit que:

Pour tous termes $t,u$ et pour toute chaîne de caractères $x$, $\lambda x(u) (t)$ se réduit en $u[x:=t]$.

Avec ça on peut implémenter tous les termes du lambda-calcul et montrer la Turing-complétude de ce langage.

Quentino37

dp a dit :

Que veux-tu dire par « le faire avec un bit par case » ?

Ce que je voulais dire était que une case peut soit prendre zéro ou 1

Homo Topi a dit :

2) que la physique du jeu vidéo en question permette la dynamique nécessaire au fonctionnement d'un circuit logique. 

Je connais malheureusement très mal la physique de Minecraft !

@Foys merci beaucoup pour pour ton explication ! Je n'ai pas trop le temps de tout lire ce matin mais je regarderait ton explication cette après midi !

Homo Topi

Je ne m'y connais que très peu en programmation, mais puisque les mods existent, le code du jeu doit bien être lisible quelque part. Apprendre à comprendre la physique interne d'un jeu vidéo requiert de se plonger dans le code, et ça garantit d'être compliqué, mais quand je pense à tout le bazar que les gens savent faire aujourd'hui, les connaissances et les gens qui les ont sont là.

Quentino37

Bonjour ! Est-ce que ce système est Turing complet ?
On a une liste finie de n nombre entre 0 et 3, 
On regarde le premier nombre :
Si c'est un 0 ou un 2 on ne fait RIEN

Si c'est un 1 on change TOUT les nombres de la liste en leur ajoutant 1(on met modulo 4)
Si c'est un 3 on change TOUT les nombres SAUF lui même de la même façon qu'avec le 1
Puis on regarde le nombre suivant, ect

Quand on arrive a la fin de la liste on revient au début 

Pourquoi ce système ? 
- Il est très facile je pense à ajouter à Minecraft
- Il peut avoir des entrés et des sortie et le programme peut s'arrêter ou faire des boucles, donc je pense qu'on peut faire un peu ce qu'on veut mais je suis pas sur des limites de ce système...
- Rapide en temps de calcul 
Inconvénients : Humainement presque inutilisable...
Mais si c'est Turing complet on peut considérer ça comme un ordinateur ?