Domanda:
Minecraft Turing è completo?
Oak
2011-04-17 05:34:09 UTC
view on stackexchange narkive permalink

Minecraft ha il meccanismo dei fili di pietra rossa che può essere utilizzato per costruire circuiti. Minecraft Turing-Complete, ovvero può essere utilizzato per simulare una Turing Machine (se ignoriamo il problema della memoria infinita)?

C'è anche il problema di non avere spazio infinito: allontanati di più di pochi pezzi e parti della tua cosa verranno scaricate
Riferimento xkcd obbligatorio: http://xkcd.com/505/
Dipende da ciò che capisci sotto Turing completo. Con la definizione formale Minecraft non è completo di Turing. Ma nemmeno il tuo computer o qualsiasi altro dispositivo reale perché hai bisogno di memoria infinita per questo. Nel senso più comune che viene utilizzato Turing completo, il che significa che è un computer universale, quindi sì, Minecraft è Turing completo.
@Phoshi fortunatamente non è più così!
@Agos Un altro XKCD rilevante: https://xkcd.com/1636/
@FabianRöling E un altro, anche se solo nel testo del titolo: xkcd.com/1223
Cinque risposte:
#1
+91
Nick T
2011-04-17 05:59:43 UTC
view on stackexchange narkive permalink

Lo stesso Notch in un'intervista ha affermato che sì, i blocchi di Redstone in Minecraft consentono la costruzione di macchine complete di Turing.

Un paio di persone hanno persino costruito ALU e CPU, ad esempio il seguente. Il creatore aveva in programma di aggiungere un array di memoria per consentirne la programmazione.

Eccezionale. Incredibilmente triste, ma fantastico.
Qual è la velocità della CPU? 0,5 Hz?
@WTP, che sembrava circa la velocità a cui poteva sincronizzarlo, ma in base al ritardo su alcune modifiche al registro sono sicuro che in quel caso avrebbe condizioni di gara e probabilmente ha bisogno di una velocità molto più lenta o di una pipeline.
Immagina se un enderman prendesse uno di quei blocchi d'erba. Voglio vederti eseguire il debug.
#2
+20
Daniel Wagner
2015-02-16 07:04:44 UTC
view on stackexchange narkive permalink

So che questa domanda è un po 'vecchia, ma tutte le altre risposte mi sembrano piuttosto complesse, mentre la risposta stessa può essere abbastanza semplice: né i cancelli sono universali, le torce di pietra rossa lo sono né porte e tutti i grafici possono essere incorporati in 3 spazi; quindi sì, Minecraft è Turing completo!

Minecraft non è esattamente tridimensionale però.C'è un limite di altezza.Ciò limita la sua completezza di rotazione?
@XeroOl Buon punto.Tuttavia, penso che vada bene: usando l'analogia del collegamento, non è importante che le pagine del libro siano in grado di andare in * qualsiasi * direzione, ma solo che ci siano infinite direzioni in cui andare.In Minecraft (ignorando la restrizione "solo blocchi caricati", come penso che alla fine anche la maggior parte delle altre risposte stiano facendo) hai ancora questo, almeno.
Pensi che sarebbe possibile utilizzare un mondo piatto come un nastro di memoria infinita e costruire una macchina a blocchi di melma che si comporti come una macchina turing?
@XeroOl Guarderei quel tutorial.=)
@XeroOl So di essere in ritardo di 3 anni;ma nel senso più stretto, nessun sistema finito può essere Turing completo.
L'incorporamento di grafici richiede solo la sovrapposizione per superare la restrizione dei grafici planari, giusto?C'è la stretta necessità di avere altezze infinite quando possiamo compensarle distribuendo i collegamenti su altri assi?
#3
+10
Ekuurh
2012-07-03 22:37:57 UTC
view on stackexchange narkive permalink

Temo che qualsiasi edificio in pietra rossa di dimensioni finite (anche in un mondo infinito) possa memorizzare solo tanti bit di dati quanto la quantità di pietra rossa inserita, quindi non è Turing Complete.

Se stai parlando di edifici in pietra rossa di dimensioni infinite, beh, puoi costruire abbastanza facilmente il gioco della vita di Conway in Minecraft, che sta tornando completo. "Abbastanza facilmente" non funzionerà se fossimo in uno spazio Minecraft 2D, e lì, beh, questa è una domanda interessante :)

Ecco un chiaro esempio di implementazione:

È vero che qualsiasi sistema finito non è turing completo, ma questo di solito viene ignorato quando si parla di turing completezza. Ad esempio, qualsiasi computer moderno con una quantità limitata di spazio di archiviazione non è completo.
Se il gioco della vita di Conway fosse completo e funzionasse in Minecraft, questo non completerebbe automaticamente Minecraft Turing?
Secondo questa logica, neanche i computer sono Turing Complete.
-1;la pietra rossa è assolutamente completa.Come ha detto BlueRaja, se Minecraft non è considerato TC a causa della finitezza, allora tutti i computer non sono TC
#4
+2
Timothy Swan
2014-01-27 10:07:03 UTC
view on stackexchange narkive permalink

Vanilla Minecraft è molto probabilmente Turing Complete a causa della combinazione di clonazione del blocco di comando (per la memoria illimitata), teletrasporto (per il caricamento di blocchi) e rilevamento dell'aggiornamento dei blocchi (un componente per i dispositivi di clonazione autoidentificativi).

Il resdstone di Minecraft non è una macchina turing completa, e da solo non può costruire una macchina turing completa - come spiegato nel video - ma redstone è un turing comple * linguaggio *, come in: può essere usato per scrivere programmi di lunghezza arbitraria che possonofare tutto ciò che una macchina turing può fare con un programma di lunghezza arbitraria.E quando dico lunghezza arbitraria, intendo in particolare che è finita.Questo è il modo in cui la completezza del turing viene intesa per i linguaggi di programmazione.Altrimenti dovremmo dire che non esiste un linguaggio completo perché il linguaggio non può creare memoria.
#5
-1
l4m2
2018-05-10 17:22:36 UTC
view on stackexchange narkive permalink

Sì con spawner / end portal (per duplicare l'elemento) per una memoria infinita.Qui non parlo del blocco dei comandi perché se si considerano i comandi possono esserci solo entità finite (UUID 128 bit)



Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 3.0 con cui è distribuito.
Loading...