Question:
Minecraft Turing est-il complet?
Oak
2011-04-17 05:34:09 UTC
view on stackexchange narkive permalink

Minecraft a le mécanisme des fils de redstone qui peut être utilisé pour construire des circuits. Est-ce que Minecraft Turing est complet, c'est-à-dire peut-il être utilisé pour simuler une Machine de Turing (si nous ignorons le problème de la mémoire infinie)?

Il y a aussi le problème de ne pas avoir d'espace infini - éloignez-vous de plus de quelques morceaux et des morceaux de votre chose seront déchargés
Référence xkcd obligatoire: http://xkcd.com/505/
Cela dépend de ce que vous comprenez sous Turing complet. Avec la définition formelle, Minecraft n'est pas Turing complet. Mais votre ordinateur ou tout autre appareil réel non plus, car vous avez besoin d'une mémoire infinie pour cela. Dans le sens plus commun que Turing complet est utilisé, ce qui signifie qu'il s'agit d'un ordinateur universel, alors oui, Minecraft est Turing complet.
@Phoshi heureusement ce n'est plus le cas!
@Agos Un autre XKCD pertinent: https://xkcd.com/1636/
@FabianRöling Et un autre, mais uniquement dans le texte du titre: xkcd.com/1223
Cinq réponses:
Nick T
2011-04-17 05:59:43 UTC
view on stackexchange narkive permalink

Notch lui-même a déclaré dans une interview que oui, les blocs Redstone de Minecraft permettent la construction de machines complètes de Turing.

Quelques personnes ont même construit des ALU et des processeurs, par exemple le suivant. Le créateur prévoyait d'ajouter un tableau mémoire pour permettre sa programmation.

Impressionnant. Incroyablement triste, mais génial.
Quelle est la vitesse du processeur? 0,5 Hz?
@WTP, qui semblait à propos de la vitesse à laquelle il pouvait le cadencer, mais sur la base du retard sur certains des changements de registre, je suis sûr qu'il aurait des conditions de course dans ce cas et a probablement besoin d'une vitesse beaucoup plus lente ou d'un pipeline.
Imaginez si un enderman prend un de ces blocs d'herbe. Je veux te voir le déboguer.
Daniel Wagner
2015-02-16 07:04:44 UTC
view on stackexchange narkive permalink

Je sais que cette question est un peu ancienne, mais toutes les autres réponses me semblent assez complexes, alors que la réponse elle-même peut être assez simple: ni les portes ne sont universelles, les torches redstone le sont ni portes, et tous les graphiques peuvent être incorporés dans 3 espaces; alors oui, Minecraft est Turing terminé!

Minecraft n'est cependant pas exactement 3 espaces.Il y a une limite de hauteur.Cela limite-t-il son exhaustivité?
@XeroOl Bon point.Pourtant, je pense que ce n'est pas grave: en utilisant l'analogie du lien, il n'est pas important que les pages du livre puissent aller dans * n'importe quelle * direction, juste qu'il y ait une infinité de directions pour elles.Dans Minecraft (en ignorant la restriction "uniquement les morceaux chargés", comme je pense que la plupart des autres réponses le font aussi), vous avez toujours cela, au moins.
Pensez-vous qu'il serait possible d'utiliser un flatworld comme une bande de mémoire infinie et de construire une machine à blocs visqueux qui agit comme une machine à turing?
@XeroOl Je regarderais ce tutoriel.=)
@XeroOl Je sais que j'ai 3 ans trop tard;mais au sens le plus strict, aucun système fini ne peut être Turing complet.
L'intégration de graphiques nécessite juste un chevauchement pour surmonter la restriction des graphiques planaires, n'est-ce pas?Y a-t-il un besoin strict d'avoir une hauteur infinie quand on peut compenser celles-ci en étalant les connexions dans d'autres axes?
Ekuurh
2012-07-03 22:37:57 UTC
view on stackexchange narkive permalink

J'ai peur que tout bâtiment de redstone de taille finie (même dans un monde infini) ne puisse stocker autant de bits de données que la quantité de redstone qu'il contient, donc ce n'est pas Turing Complete.

Si vous parlez de bâtiments en redstone de taille infinie, eh bien, vous pouvez assez facilement créer le jeu de la vie de conway dans Minecraft, qui est en train de s'achever. "Assez facilement" ne fonctionnera pas si nous étions dans un espace Minecraft 2D et là, eh bien, c'est une question intéressante :)

Voici un bel exemple d'implémentation:

Il est vrai que tout système fini n'est pas complet, mais cela est généralement ignoré quand on parle de complétude. Par exemple, tout ordinateur moderne avec une quantité limitée de stockage n'est pas terminé.
Si le jeu de la vie de Conway est terminé et qu'il fonctionne dans Minecraft, cela ne rendrait-il pas automatiquement Minecraft Turing complet?
Selon cette logique, les ordinateurs ne sont pas non plus complets.
-1;redstone est absolument complet.Comme l'a dit BlueRaja, si Minecraft n'est pas considéré comme TC en raison de sa finitude, alors tous les ordinateurs ne sont pas TC
Timothy Swan
2014-01-27 10:07:03 UTC
view on stackexchange narkive permalink

Vanilla Minecraft est probablement Turing Complete en raison de la combinaison du clonage de bloc de commande (pour une mémoire illimitée), de la téléportation (pour le chargement de bloc) et de la détection de mise à jour de bloc (un composant pour les dispositifs de clonage auto-identifiables).

Le resdstone de Minecraft n'est pas une machine complète de turing, et ne peut pas à lui seul construire une machine complète de turing - comme expliqué dans la vidéo - mais redstone est un * langage * complet de turing, comme dans: il peut être utilisé pour écrire des programmes de longueur arbitraire qui peuventfaire tout ce qu'une machine de turing peut faire avec un programme de longueur arbitraire.Et quand je dis longueur arbitraire, je veux dire en particulier qu'elle est finie.C'est ainsi que la complétude est comprise pour les langages de programmation.Sinon, il faudrait dire qu'il n'existe pas de langage complet car le langage ne peut pas créer de mémoire.
l4m2
2018-05-10 17:22:36 UTC
view on stackexchange narkive permalink

Oui avec le portail spawner / end (pour dupliquer l'élément) pour une mémoire infinie.Ici, je ne parle pas de bloc de commandes car si les commandes sont considérées, il ne peut y avoir que des entités finies (UUID 128 bits)



ⓘ
Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...