Even with finer program access controls, it would still be hard to protect as long as untrusted code was allowed to alter trusted.
Yes, that's what I said. :)
Bear in mind that this is already only a 16bit CPU with a restricted address space.
I suspect the interpreter could be made to fit, with limited space left for the untrusted (to-be-interpreted) code. As has been pointed out elsewhere, though, if there is a backing store (i.e., simulated hard drive), it's probably possible to have effectively unlimited "RAM" in the game in practice, unless Notch implements a slowdown for accessing the backing store.
In practice that might not matter for many applications if they do not have to use intensive algorithms etc.
I would still imagine that compilers would be used more than interpreters though which would mean that some security would need to be present at the "hardware" or "firmware" level.
Another interesting thing to think about regards backing stores:
I assume that the programs will be able to take input from the world around them, i.e other ships , objects in space etc.
So what's to stop you from using (perhaps) a tractor beam to re-organise the position of asteroids in space and then "read" that data back using ship instrumentation?
Potentially the entire universe becomes one big DB!