A virtual machine is a common example of simulation. It can take the
description of a (virtual) "computer" state and continue the execution
from that point on. You can simulate a huge computer given a computer
with more memory than the virtual machine, although it might be way
slower. However, such virtual machine does not answer the problem because it normally simulates a computer with less memory.
The question is, can a computer to simulate a virtual computer that has the same capabilities as itself? Before answering this, let's exclude some trivial (forbidden) cases of "simulations":
Normally you can simulate any system that has discrete states using a bigger computer. Discrete states means a finite number of logical states, as opposed to physical systems where you might not be able to describe the whole state (think quantum physics) or systems where the expected behavior depends on possible outside influences (think gravity). We don't want to simulate here any possible outside influences (cosmic rays), just the expected behavior according to that system's specifications.
The requirement here is that a separate "simulator" program, running on an identical computer, will receive the state of the "computer to be simulated" and it is able to simulate it from now on. This should be possible for any state that the simulated computer might have. The simulation should be distinct from the computer that is simulated. You should be able to tell that now the computer is simulating a certain program in a virtual computer, as distinct from just running that program. You cannot get extra memory when simulating, you have to store the whole state of the simulated computer inside this "simulation" computer. After the "simulated" computer state is read from an external support, this support must be removed and cannot be used during simulation.
We are not concerned about simulating what is happening in the actual hardware (transistors, electrons), but just the logical state that is observable by binary output devices. The speed is not of concern here.
Mathematically not...
Intuitively, you need more memory in order to accommodate the state of the computer that you want to simulate and the "simulator" program. However, this does not automatically exclude the possibility.
You can think about storing the simulated computer state on hard drive and load only parts when needed. This would not work however, as the simulated computer might also have the hard driver full of useful data that needs to be stored.
Actually, any computer can be simulated by a Turing machine, using a Universal Turing Machine. We use to consider computers as being "Turing complete", so they can theoretically simulate any other "Turing" machine, like another computer. However, there is one big difference: the computer does not have an infinite tape like the Turing machine does. The "Universal Turing Machine" benefits from an infinite tape, so it can always accommodate enough more memory to simulate an arbitrary big other Turing machine (like a computer). However, our simulating computer does not have more memory than ... itself.
Not having more memory than itself is not automatically a proof that a computer cannot simulate itself. For example you could receive the state of the simulated computer compressed, so you can decompress it on need. Or somehow the program can be hidden in the hardware specifications and always present in the state of the simulated computer... You can imagine various tricks, like the program that when executed is able to print it's own source code. We need to find a better argument than this intuitions.
A sketch of proof is this: if our computer can simulate any state of himself, he should be also able to simulate itself while he simulate itself, and so on. We can create an infinite series of distinct states that our computer should be able to be in: simulating the simulation of simulation of simulation ... *N ... of itself. Our computer has a limited number of states (even if they are many), so it cannot accommodate an infinite series of simulation of simulation... Therefore, a finite memory computer will not be able to simulate all the functionalities of... himself.
Practically, almost yes
If we just add a little more memory, just to store the simulation program it is, however, possible to simulate a computer, the same as we do with virtual machines. Similarly, you can simulate any computer functionality that will not use a small region of it's memory for the program. In this case the series of simulations will have bigger and bigger memory for the simulator, or smaller and smaller memory of the simulated computer.
Can a human simulate itself?
If we consider the mind of a human as the product of a biological computer that can have a finite representation, the same should also apply to humans. A human will not be able to fully simulate itself, however it is not impossible to simulate a subset of it's abilities, like: "if I would be put in this situation, I would do like this".
More interesting is the ability of a human to simulate another human mind process or feeling through empathy. A human can somehow deeply understand what another human is experiencing.
Actually, any communication act is an attempt to pass to another human a simulation of it's own thought of mind. The simulation is never identical, but the intent is to transmit the though as similar as possible.
Please share this article if you find it interesting. Thank you.
The question is, can a computer to simulate a virtual computer that has the same capabilities as itself? Before answering this, let's exclude some trivial (forbidden) cases of "simulations":
- A calculator will always do exactly what it does, it will be identical with itself, we will not call this a simulation of itself.
- Copying the exact state of another identical computer in a "twin brother" will not be considered simulation.
- Starting 2 identical computers with the same input will not be considered like one is simulating the other.
Normally you can simulate any system that has discrete states using a bigger computer. Discrete states means a finite number of logical states, as opposed to physical systems where you might not be able to describe the whole state (think quantum physics) or systems where the expected behavior depends on possible outside influences (think gravity). We don't want to simulate here any possible outside influences (cosmic rays), just the expected behavior according to that system's specifications.
The requirement here is that a separate "simulator" program, running on an identical computer, will receive the state of the "computer to be simulated" and it is able to simulate it from now on. This should be possible for any state that the simulated computer might have. The simulation should be distinct from the computer that is simulated. You should be able to tell that now the computer is simulating a certain program in a virtual computer, as distinct from just running that program. You cannot get extra memory when simulating, you have to store the whole state of the simulated computer inside this "simulation" computer. After the "simulated" computer state is read from an external support, this support must be removed and cannot be used during simulation.
We are not concerned about simulating what is happening in the actual hardware (transistors, electrons), but just the logical state that is observable by binary output devices. The speed is not of concern here.
Mathematically not...
Intuitively, you need more memory in order to accommodate the state of the computer that you want to simulate and the "simulator" program. However, this does not automatically exclude the possibility.
You can think about storing the simulated computer state on hard drive and load only parts when needed. This would not work however, as the simulated computer might also have the hard driver full of useful data that needs to be stored.
Actually, any computer can be simulated by a Turing machine, using a Universal Turing Machine. We use to consider computers as being "Turing complete", so they can theoretically simulate any other "Turing" machine, like another computer. However, there is one big difference: the computer does not have an infinite tape like the Turing machine does. The "Universal Turing Machine" benefits from an infinite tape, so it can always accommodate enough more memory to simulate an arbitrary big other Turing machine (like a computer). However, our simulating computer does not have more memory than ... itself.
Not having more memory than itself is not automatically a proof that a computer cannot simulate itself. For example you could receive the state of the simulated computer compressed, so you can decompress it on need. Or somehow the program can be hidden in the hardware specifications and always present in the state of the simulated computer... You can imagine various tricks, like the program that when executed is able to print it's own source code. We need to find a better argument than this intuitions.
A sketch of proof is this: if our computer can simulate any state of himself, he should be also able to simulate itself while he simulate itself, and so on. We can create an infinite series of distinct states that our computer should be able to be in: simulating the simulation of simulation of simulation ... *N ... of itself. Our computer has a limited number of states (even if they are many), so it cannot accommodate an infinite series of simulation of simulation... Therefore, a finite memory computer will not be able to simulate all the functionalities of... himself.
Practically, almost yes
If we just add a little more memory, just to store the simulation program it is, however, possible to simulate a computer, the same as we do with virtual machines. Similarly, you can simulate any computer functionality that will not use a small region of it's memory for the program. In this case the series of simulations will have bigger and bigger memory for the simulator, or smaller and smaller memory of the simulated computer.
Can a human simulate itself?
If we consider the mind of a human as the product of a biological computer that can have a finite representation, the same should also apply to humans. A human will not be able to fully simulate itself, however it is not impossible to simulate a subset of it's abilities, like: "if I would be put in this situation, I would do like this".
More interesting is the ability of a human to simulate another human mind process or feeling through empathy. A human can somehow deeply understand what another human is experiencing.
Actually, any communication act is an attempt to pass to another human a simulation of it's own thought of mind. The simulation is never identical, but the intent is to transmit the though as similar as possible.
Please share this article if you find it interesting. Thank you.
Comments