In this thread, most of the way down the page, Spiritus Mundi and I have a variety of disagreements.
Spiritus is an idiot.
Spiritus claims that the Godel Incompleteness Theorem doesn’t place restrictions on physical computers, but merely on human theories or conceptualizations about computation. He claims that the physical embodiments of computers are fundamentally different from the programs they run.
It’s been proven that any Universal Turing Machine can run a program that emulates the behavior of another Turing Machine. This is well-known in mathematics and computer science; there can be no debate about this.
This necessarily means that any UTM can be viewed as a program being run by another UTM – there’s no difference between the program and the device the program simulates.
The workings of any UTM are equivalent to an accurate description of the operations it performs in response to input. That’s why programs can always be made to simulate them: the program reacts to virtual input in precisely the same way the UTM reacts to actual input. From the output alone, there’s absolutely no way to distinguish the “real” version and the “simulated” version: they’re identical. In fact, the distinction of “real vs. simulated” is arbitrary: we can always view the “real” system as being simulated by another, making it “virtual”.
More to the point, computers can be built precisely because a one-to-one correspondence can be made between the interactions within them and the operations of a logical system.
Godel’s Incompleteness Theorem says that for any sufficiently complex system (capable of generating arithmetic; in other words, capable of performing basic operations) there will always be statements that are true given the system’s axioms but for which there is no possible proof that can be derived from those axioms.
The workings of a computer are such a system. It’s trivially obvious that computers can carry out operations. Those operations are the manifestations of the relationships between configurations within the computer: given input, the computer generates the appropriate output.
Let’s say that we’re going to give a UTM several sequences of numbers that represent the axioms of a logical system. (It’s known that this is possible.) The program of the UTM includes the rules for taking the input and generating appropriate sequences of numbers from them. The results are necessarily consistent with those rules: the device is accepting a set of axioms and producing theorems.
GIT shows that there will be true statements that those axioms cannot be used to demonstrate. Demonstrating a theorem requires taking two axioms and applying operations on them, resulting in a new statement. This is the same as taking number sequences and applying operations on them.
This means that there will be sequences of numbers that this computer will not be able to produce, given specific input. The actual number sequences themselves will be different for different manifestations of operations, but there will be a constant relationship between the sequences and the way the computer represents the operations.
The operations the computer is performing are equivalent in their results to writing down mathematical symbols and mentally applying operations to them to produce theorems.
The behavior of the computer is limited by GIT.
On the fifth page of the linked thread, Spiritus says it’s not the case. He has no idea what he’s talking about.
