mdxn

Your definitions of Turing-Complete and Turing Equivalent, as phrased, are incorrect or perhaps mistaken to some extent. I don't want to

Arbitrarily scalable memory is just one necessary component for Turing-equivalence to a Turing Machine. Two machines are Turing Equivalent when they can simulate each other. Not that this does not necessarily extend to general computation and can actually be a limited for of such.

Countably unbounded memory is not necessarily a requirement (ex. some symbolic systems), but might as well be for the class of machines that you are thinking of. A lot of models of computation become Turing-complete when they receive this benefit. You also need to keep in mind that some automata can have infinite memory, but don't have the ability to take advantage of it. Straightforward examples include pushdown automata and time bounded machines. Machines that do not have a logically complete algebra will also have this problem.

I complete agree with you about the "finite memory" objection people like to use. I find it incredibly annoying and not very productive. It is almost ignorant to discussion going on as they are completely missing the point. It's insulting that they think others don't realize this. I'm glad someone else (you) here shares this feeling. :)

I believe you meant that problems can be R.E.-complete (semidecidable in a complete way; ex. Halting problem). The term, Turing Complete, is inapplicable in this situation. It describes properties of a formal system and/or model of computation (which I'm certain you knew).

I think it would be possible given new cards, but I imagine it would be incredibly difficult (not to mention game breaking). It would basically require cards that would handle arbitrary branching (algorithmically determined). A set of cards would have to contain effects that form a general template for doing this based on cards in a implementation of memory. I personally think it is unlikely and would be tricky to pull off. I admittedly don't have a very concrete reason for this.

What I find really cool is that, while they might not add a set of cards allowing for arbitrary branching, they could introduce cards that allow for some bounded branching. This could add limitations of resource bounds that are still scalable: polynomial time, space, exponential time, primitive recursion. There seems to be a lot more flexibility here than with some other mentioned "Turing-Complete" systems.

Someone else, here, commented that you would also need to implement infinite loops. Assuming you don't have to fuel the machine with cards, this method could be used to stall a real game indefinitely! Apparently this is possible. O_O

I have, but thank you for bringing up something incredibly obvious and well known. Honestly, perhaps I shouldn't have feigned confusion in my reply. I just felt that it was courteous to have them reframe their question again before I concluded that they really did miss the point completely.

My point was that pen and paper, itself, is not a sufficient model of computation (it is not capable of any computation). Pen + paper + human is. The fact you mention is precisely why I chose to bring this situation up. If we throw in humans to the mix, our candidate "model of computation" can become heavily reliant on the capabilities of humans. At this point, we need to explicitly say that we include human interaction in this model. Based on my standards, this is not a really fruitful statement, since humans are almost capable of general computation alone. They just need the memory. Analogously, pen and paper is just a work tape. a work tape is not a system or automaton at all. I find it mind boggling that I have to explain this to people, especially those who appear so confident that they understand theory of computation.

I believe you have misunderstood what I have said. My issue with Magic was not with the logic specifically. It is with the fact that it requires the player to initiate state transition by specifically selecting actions. It would be permissible if the player simply functioned as a clock, but some of the state transition logic is actually shifted over to the player. It certainly is better than the pen and paper scenario, but the rule system is incomplete. It still requires a couple of rules for the player to follow (just as pen/paper or an abacus does).

The author mentions this problem explicitly on the "Difficulties" section of the site. It is very important to note this. The hope is for the effects of some cards to allow for the necessary computational depth to capture all of computation without additional human action (besides, lets say, initialization). People often look at Turing Machines and their components. They forget to think about state transitions and the recursion involved (recursion really is the "meat" of computation).

Can you elaborate on this? I'm not sure what your point is or how it relates to my comment.

When we talk about models of computation, we typically look at ones where some sort of resource is unbounded. In the case with generalized Minecraft, both time and block space are unbounded. The hope is to translate that block space resource and use it as memory. I was bringing up the point that this may be not possible since the mechanics do not allow enough access. This is interesting because a first approach to constructing scalable computer memory in Minecraft is to encode things with infinitely generable blocks. We have infinite sources of necessary components used for memory, but run into the barrier of operating things over arbitrary distances (communication). Even the case where you tile redstone based memory cells is just as difficult for the same reason. This is different than the case with a "normal computer" since there's no unbounded/scalable resource to consider.

I would advise that everyone take more care when assessing the Turing Completeness various models of computation. Many analyses that I have seen do a check for logical completeness, but forget to rigorously check that you have scalable and fully accessible memory, even in the most generalized cases. Even if you assume that some resource is unbounded, your other mechanics might not actually allow you to interface with it, even if they do work on a constant/small scale (locality of computation does not necessarily imply this). You could take a turing machine its infinite tape, but forget to show that you can move it left or right an arbitrary number of times. On the flip side, another ridiculous assumption involves including the power of human operation. Yes, an abacus is "Turing Complete" if it is infinitely large and you, as a human being, do the logic in your head. Pen and paper is Turing Complete by the same reasoning (this is ridiculous). Yes, we know that humans are capable of computation. I might grant that you have scalable memory in these situations, but where's the automation of your logic?

Here's an example of the first: I suspect that the in-game mechanics of a generalized version of Minecraft to not be Turing Complete. By generalized, I mean that you remove the chunk loading and update limitations, giving you a countably large playing field. I, of course, am not considering limitations (or benefits) of Java, the machine running it, or unintended behavior (bizarre bugs). Forgo things like command blocks and bizarre uses of spawn eggs/entities, just consider legitimately obtainable resources (we can assess TC with these later).

To briefly sketch the idea, when you have a constant sized machine (accessing arbitrarily sized input), the selected mechanics are too limited by construction to "grow" the equivalent to a Turing Machine's work tape. A superficial reason for this is because the mechanics are coded to only extend locally (note that this is distinct from the "computation is local" result). For example, using pistons to push only goes out 11 blocks before it fails. You can chain multiple of these together, but only a constant number. You also need controllable Redstone signal to extend far enough to change their states. With a bit more work, you can show that mechanical self propulsion using pistons is not possible (there's a giant thread on Minecraft Forums concerning this), even in one direction. Three simple reasons for this: 1. You cannot push extended pistons, 2. you cannot push/pull/power your back most piston without "leaking" blocks, and 3. you cannot make a pushable clock. Your ability to shift around and access your tape/memory or move your Turing "head"/logic in this approach goes out the window.

For block based memory (to make use of infinite "block space") in general, you not only have to move a number of blocks of an arbitrary number to locations an arbitrary distance away, but you have to autonomously generate and destroy an arbitrary number of blocks, too. Cobblestone, Ice, Pumpkins, and Melons all do this and are thankfully Redstone distinguishable, so we at least have our endless supply of symbols for such a tape. There are additional requirements and engineering challenges, but they fall outside the purpose of this post.

Issues like these are not considered in almost all the claims Minecraft's Turing Completeness that I have seen. They absolutely should be. Obviously there may be ways around this, but I hope my point is clear. Make sure the application of your "proofs" or constructions actually make sense. Make sure they demonstrate how to handle the memory and the logic (algebra) necessary. And for god's sake, make sure that your model is actually an automaton (I'm looking at you Magic and LBP).

On a side note, I did start compiling a paper on the computational complexity of Minecraft a while ago, but left it unfinished. It goes through various generalizations, starting from some most basic (just blocks, redstone, etc.), adding some components like randomness, commandblocks, entities. Even some structural assumptions such as superflat worlds and tiled machines (works for Conways game of life). I lost some motivation because I did not believe people would care enough to be worth my time. Even if I were to pick it up again, the game has changed quite a bit since 1.7 came out. My results might be outdated (new commandblock functionality changes things greatly). However, if others show interest, I could perhaps start working on it again.

I know a couple of CS security students at my university (myself included) that would LOVE to look into those if what you say is true.

There are dozens of Greasemonkey scripts on userscripts.org dating back to 2005 that do exactly this and more (On Chrome, you can use the Tampermonkey extension; On Firefox, it's just called Greasemonkey). No to belittle your work or anything, but why is this interesting or newsworthy?

Also, I suspect that some of the comments here are either fake or staged. However, I'll give them the benefit of the doubt. If my skepticism and critique here are based on misunderstandings, I apologize.

There are things mentioned in this article that are completely wrong. There are also comments here that show a complete misunderstanding of the P vs. NP question in general, but I won't address these.

The constraint problem here with only pairs of incompatible students is a instance of 2SAT, which is solvable in quadratic time (i.e. in P; note: the complexity here is the possible number of pairs, not just students). To make it reside in NP, it has to be at least 3SAT. Essentially, this is equivalent to also indicating triples of students that are incompatible (while the pairs of any of the students in the triple may or may not be compatible). Since the dean explicitly does not provide this information, we are all good and are in the position of solving this problem efficiently.

Also, Cook did not invent the P vs. NP problem. He is often credited as the person who first formalized it and studied it to a sufficient degree. The first mention of the P vs. NP problem I know of is in a letter from Godel to Von Neumann (http://rjlipton.wordpress.com/about/).

This witch hunt is incredibly disturbing. Not only do these petitions blatantly exclude some fundamental principles of government and society, but they distracts greatly from where our focus should lie.

I can't edit to clarify now, but that statement is meant to be an assumption rather than of fact for use as a toy example for a line of reasoning.

If I could edit again, I'd make it read as "For instance, let P <= BPP <= NP".

If you don't mind me asking, how and when did you find his blog post?

No, he is claiming that l-CLIQUE requires exponential circuit size (this is the reason that most of the proof talks about circuit complexity and not time bounded Turing Machines). This is not necessarily the same thing as exponential time.

We do have to worry about it. If it is the case that NP <= P/poly, then PH collapses to sigma P 2. Unless there have been recent results that show otherwise, P/poly might even contain NEXPTIME.

Regardless, the connection to P in this paper is not immediately obvious to me. It certainly is not explicitedly stated in a form that I even partially recognize.

Because of these reasons, I am deeply skeptical of the leap directly to P != NP. A lot of incorrect papers do something similar: They show a lot of very complicated constructions then, BAM, Collorary. P != NP. It kind of hand waves the most important step.

1. BPP <= P/poly was proven by L. Adleman.

2. I never said that P = BPP was hard to prove. I only brought up BPP because its derandomization, despite being limited to subexponential nondeterministic time, would still imply a lower bound of super polynomial circuit size (which could be the exponential lower bound presented by the author). The author is using this exponential lower bound (circuits) to immediately conclude that P != NP:

"The proof of Theorem 6.1 is now complete. We have: Corollary 6.5 P 6= NP"

Note: Theorem 6.1 is the lower bound

I was clearly referring to exponential circuit sizes (note the sentence before it), not exponential time.

By the way, you can edit your original reply to contain more information rather than just making a bunch of new ones.

The depth vs. size characterization was a legitimate mistake of mine (got distracted by the authors use of depth). I am aware of the distinction. Though in writing my post, I did actually have size in mind. I'll edit to reflect this.

As for (P/poly != NP) => (P != NP), I have never heard of this. I have, however, seen that if NP is not a subset of P/poly then P != NP (which was not claimed here). Perhaps I am missing a stronger result? If so, please link me to a source for such a result.

Note: For the moment, I will assume that the NP != NC and above results are correct enough to consider the validity of the latter portion of the paper.

As far as I can tell (from my initial reading), the author (and many many commenters here) seem(s) to be confusing polynomial time (P) with polynomial circuit size (P/poly). These are completely different complexity classes in style and probably in power, too. Last time I checked, there was not a good characterization of P in terms of circuit complexity (the attempt at doing so is P/poly). So, logically, comparing P and NP is not even possible without additional knowledge about P. The exception to this being showing that X != NP where P <= X <= NP.

For reference: P <= BPP <= NP

We know that BPP (a randomized version of P) is (non-strictly) contained in P/poly. We also know that proving P = BPP (which is conjectured to be true by most) requires these classes require superpolynomial lower bounds for Boolean|Arithmetic circuit size. As far as I know, proving an exponential lower bound for an NP-complete problem doesn't immediately rule that P != NP since P !=> only polynomial size circuit size (the circuit size only relates to the size of the advice function). P might not contain problems that require exponential circuit size, but this fact is not stated, proven, nor reference by the author here.

Simply put: The author assumes that P != NP follows immediately from Theorem 6.1. This is not as obvious as they might think it is; many additional details are needed.

Admittedly, I have not rigorously studied or concluded anything from the flattening process the author proposes. I honestly don't believe I have to. Skimming over it, I don't see any way that P is characterized in terms of polynomial circuit sizes (which probably is an assumption as powerful as P!=NP) here. I also do not see any mention of P/poly, which I believe the author is attempting to use.

For a paper approaching the P vs NP issue using circuit complexity, I would expect this much. Because of the lack of even a mention of BPP, P/poly, and others, I would be highly surprised if many of these results in the paper hold at all. Though, hopefully, I might be wrong.

EDIT: Accidentally used circuit depth when I was really thinking of size.