Pytanie:
Czy Minecraft Turing jest kompletny?
Oak
2011-04-17 05:34:09 UTC
view on stackexchange narkive permalink

Minecraft ma mechanizm przewodów z czerwonego kamienia, który można wykorzystać do budowy obwodów. Czy Minecraft Turing-Complete, tj. Czy można go używać do symulacji Maszyny Turinga (jeśli zignorujemy problem nieskończonej pamięci)?

Istnieje również problem braku nieskończonej przestrzeni - odejdź więcej niż kilka kawałków, a kawałki twojej rzeczy zostaną rozładowane
Obowiązkowe odniesienie do xkcd: http://xkcd.com/505/
To zależy od tego, co zrozumiesz pod Turingiem. Z formalną definicją Minecraft nie jest kompletny. Ale nie jest to również twój komputer ani żadne inne prawdziwe urządzenie, ponieważ potrzebujesz do tego nieskończonej pamięci. W bardziej powszechnym sensie używany jest Turing Complete, co oznacza, że ​​jest to uniwersalny komputer, a następnie tak, Minecraft jest kompletny.
@Phoshi na szczęście już tak nie jest!
@Agos Kolejny odpowiedni XKCD: https://xkcd.com/1636/
@FabianRöling I jeszcze jeden, choć tylko w tekście tytułowym: xkcd.com/1223
Pięć odpowiedzi:
Nick T
2011-04-17 05:59:43 UTC
view on stackexchange narkive permalink

Sam Notch powiedział w wywiadzie, że tak, bloki Redstone w Minecrafcie pozwalają na budowę maszyn Turinga kompletnych.

Kilka osób zbudowało nawet jednostki ALU i procesory, na przykład poniższy. Twórca planował dodanie tablicy pamięci, aby umożliwić jej programowanie.

Niesamowite. Niesamowicie smutny, ale niesamowity.
Jaka jest prędkość procesora? 0,5 Hz?
@WTP, wydawało się, że jest to prędkość, z jaką może taktować, ale w oparciu o opóźnienie niektórych zmian rejestrów jestem pewien, że w tym przypadku miałby warunki wyścigu i prawdopodobnie potrzebuje znacznie wolniejszej prędkości lub rurociągu.
Wyobraź sobie, że enderman bierze jeden z tych bloków trawy. Chcę zobaczyć, jak to debugujesz.
Daniel Wagner
2015-02-16 07:04:44 UTC
view on stackexchange narkive permalink

Wiem, że to pytanie jest trochę stare, ale wszystkie inne odpowiedzi wydają mi się dość złożone, podczas gdy sama odpowiedź może być dość prosta: ani bramy nie są uniwersalne, pochodnie z czerwonego kamienia są ani bramek, a wszystkie wykresy mogą być osadzone w trzech odstępach; więc tak, Minecraft jest kompletny!

Minecraft nie jest jednak dokładnie 3-przestrzennym.Istnieje limit wysokości.Czy to ogranicza jego kompletność?
@XeroOl Słuszna uwaga.Mimo wszystko myślę, że jest w porządku: używając analogii z linku, nie jest ważne, aby strony książki mogły iść w * dowolnym * kierunku, tylko, że istnieje nieskończenie wiele kierunków, w których mogą iść.W Minecrafcie (ignorując ograniczenie „tylko załadowane fragmenty”, ponieważ myślę, że większość innych odpowiedzi też ostatecznie robi), przynajmniej to masz.
Czy myślisz, że byłoby możliwe użycie płaskiego świata jako nieskończonej taśmy pamięci i zbudowanie maszyny blokującej szlam, która działa jak maszyna turinga?
@XeroOl Obejrzałbym ten samouczek.=)
@XeroOl Wiem, że jestem o 3 lata za późno;ale w najściślejszym sensie żaden skończony system nie może być kompletny Turinga.
Osadzanie grafów wymaga tylko nakładania się, aby przezwyciężyć ograniczenie grafów planarnych, prawda?Czy istnieje ścisła potrzeba posiadania nieskończonej wysokości, kiedy możemy to skompensować poprzez rozłożenie połączeń w innych osiach?
Ekuurh
2012-07-03 22:37:57 UTC
view on stackexchange narkive permalink

Obawiam się, że każdy budynek z czerwonego kamienia o skończonych rozmiarach (nawet w nieskończonym świecie) może przechowywać tylko tyle bitów danych, ile włożono w niego czerwonego kamienia, dlatego nie jest to ukończone Turing.

Jeśli mówisz o budynkach z czerwonego kamienia o nieskończonej wielkości, cóż, możesz dość łatwo zbudować grę życia Conwaya w Minecrafcie, która jest prawie ukończona. „Całkiem łatwo” nie zadziała, jeśli będziemy w przestrzeni 2D Minecraft, i no cóż, to interesujące pytanie :)

Oto fajny przykład implementacji:

Prawdą jest, że żaden skończony system nie jest kompletny, ale jest to zwykle ignorowane, gdy mówimy o kompletności. Na przykład żaden nowoczesny komputer z ograniczoną ilością pamięci nie jest kompletny.
Jeśli Gra życia Conwaya jest ukończona i działa w grze Minecraft, czy to nie sprawi, że Minecraft Turing zostanie automatycznie ukończony?
Zgodnie z tą logiką komputery również nie są kompletne.
-1;Redstone jest absolutnie kompletny.Jak powiedział BlueRaja, jeśli Minecraft nie jest uważany za TC ze względu na skończoność, to wszystkie komputery nie są TC
Timothy Swan
2014-01-27 10:07:03 UTC
view on stackexchange narkive permalink

Vanilla Minecraft to najprawdopodobniej Turing Complete ze względu na kombinację klonowania bloków poleceń (dla nieograniczonej pamięci), teleportacji (w przypadku ładowania fragmentów) i wykrywania aktualizacji bloków (komponent do samoidentyfikujących się urządzeń klonujących).

Resdstone Minecrafta nie jest kompletną maszyną Turing i sam w sobie nie może skonstruować kompletnej maszyny Turinga - jak wyjaśniono w filmie - ale Redstone jest kompletnym * językiem * Turinga, na przykład: może być używany do pisania programów o dowolnej długości, które mogązrobić wszystko, co maszyna Turinga może zrobić z programem o dowolnej długości.A kiedy mówię o dowolnej długości, mam na myśli zwłaszcza to, że jest skończona.Tak rozumiana jest kompletność turinga w językach programowania.W przeciwnym razie musielibyśmy powiedzieć, że nie ma czegoś takiego jak kompletny język, ponieważ język nie może tworzyć pamięci.
l4m2
2018-05-10 17:22:36 UTC
view on stackexchange narkive permalink

Tak, z portalem spawner / end (do zduplikowania przedmiotu) dla nieskończonej pamięci.Nie mówię tutaj o bloku poleceń, ponieważ jeśli rozważane są polecenia, mogą istnieć tylko jednostki skończone (UUID 128 bitów)



ⓘ
To pytanie i odpowiedź zostało automatycznie przetłumaczone z języka angielskiego.Oryginalna treść jest dostępna na stackexchange, za co dziękujemy za licencję cc by-sa 3.0, w ramach której jest rozpowszechniana.
Loading...