Don’t make the mistake of confusing a Turning machine with all Turing machines. Turing machines as a group can indeed handle any input (I think… I could be mistaken). For any particular Turing machine, there will be patterns of input that it can’t handle: it will either fail or enter an infinite loop. The Halting problem is one example of this; no matter what specific configuration we consider, no Turing machine can ever solve it. The important thing to realize is that the actual configuration of input that represents this problem varies from machine to machine.
First off, entering into an infinite loop is not the same as crashing. You want the SDMB server to be in an inifinite loop, otherwise you can’t post.
Secondly, I was not aware that any particular instance of the halting problem is undecidable. The machine that echoes its input will halt when given a finite length input. It is true that the halting problem can’t be decided in general, but that doesn’t mean that we can never solve any instance.
**
The grammar of formal theories is independent of the meanings of the symbols. Any logic textbook worth its salt will tell you this.
**
The circuit is not addition. The circuit takes input and produces output that we interpret as the sum of addends. Addition is an abstract concept. No physical entity can be equal to an abstract concept.
** Infinite loops in programs are quite unpleasant. If the algorithm for a problem enters an infinite loop, it can never reach a conclusion/result/meaningful output.
C’mon, you already knew that. Even if my language is insufficient, you are aware of what I mean.
Yes. So, give the Turing machine the problem of finding a general solution. There isn’t one – and we’ve just broken the system.
**
But not independent of the concepts those symbols represent. The grammar is part of what the symbols represent – without the grammar, no relationships are possible between the symbols, and hence there’s no meaning.
**
No, not in general. Something can always come along and screw it up. Similarly, the system in your brain responsible for “addition” can err. However, the circuit is indeed the manifestation for the concept of addition for that particular notation of numbers. If the circuit is changed so that its behavior no longer matches addition, it’s simply stopped being addition.
Not every program needs to terminate to give meaningful output. Did you miss the example of the SDMB server? Let me give you a rough outline of how it works:[ol][li]Wait for a page request.[]Pull all necessary info from the DB to make the page, and serve it.[]If a database write is necessary, do it.Go back to step 1.[/ol] Are you telling me that that infinite loop is undesirable?[/li]
**
That’s not a well-defined input. I don’t mean that the TM can’t handle it, I mean that you can’t express it in the language of TMs. If you think you can, please explain precisely how you would do so.
**
The grammar is independent of the meaning of the symbols. It describes how they relate to each other, but nothing about what they mean. Like I said before, this is a demonstrable fact. If you don’t believe me, check Mendelson’s Introduction to Mathematical Logic.
Perhaps we also, then, do not understand what you mean by “infinite loop.” If you mean something silly like an expanded version of
10 Goto 20
20 Goto 10
then that is rather unpleasant. If you mean “this program will run and run, there is no natural exit from function F once entered” in the more general case then there is nothing unpleasant about it at all. Your calculator likely has nothing but an infinite loop waiting for input. There is no escape from its functions, you can only remove the power. And yet you might notice that calculators are useful, and these infinite loops are not unpleasant. They are necessary.
And you’re missing my point. I agree with what you just said above. But my point is that this is not a statement about the pencil and paper. It’s a statement about the rules, or more accurately how we interpret the rules.
Again you’re missing the point. How does GIT imply that there will always be inputs that cause the system to crash, no matter what the system?
That is what you’ve been asserting, and that is what you’ve failed to prove.
It is true that no computer can be programmed to derive a proof of an unproveable proposition. There is also no way for a TCP/IP server, or a pocket calculator, or an abacus, or the game of life, or a Street Fighter VII arcade cabinet to prove an unproveable proposition. So what? How does that imply that there is some input which will cause the TCP/IP server or the calculator or the abacus or the game of life or the arcade cabinet to crash?
It is true that no computer can be programmed to solve the halting problem. Again, so what? How does this imply that there is some input which will cause my TCP/IP server or my calculator to crash? And even if that implication does exist, what in the bloody blue blazes does that have to do with GIT?
Oh, for the love of Ned.
Mathematics is a language which describes the world around us. Mathematics is fundamentally no more equivalent to reality than a declaration of war is equivalent to a punch in the nose. Yes, mathematics is an exceptionally precise language with a remarkably record for accurately describing reality. That does not give mathematics a free pass. A mathematic statement may or may not accurately describe reality, and thus suggest physical consequences, but to assume without evidence that a mathematical statement does accurately describe reality is a fallacy.
And that is what you are doing when you suggest that GIT somehow describes the behaviour of arbitrary physical computing systems. The question of whether GIT describes the behaviour of abstract models of computing is another question, but one for which you have also provided no support.
TVAA
You have passed over my request to dot some “i’s” and cross some “t’s” rather than simply engaging in broad statements about the nature of abstraction, reality, etc. So, I am afraid at this point I am going to have to go into a loop of my own until we can get some very basic ideas nailed down. Here’s the first one:
Assume that I know a Godel number of the Godel statement for natural number (including 0, for those of us who care) arithemetic. We’ll call this number G.
[ul][li]Will my calculator malfunction if I type in the number G?[/li][li]Will my calculator malfunction if I add 1 to G?[/li][li]Will my calculator malfunction if I multiple (1+G) * 2?[/ul][/li]
Can you generalize the answers to the above question to some statement about what GIT implies for machines that use arithmetic?
Invalid questions. Calculators’ circuitry does not include the algorithms for evaluating Godel numbers any more than it includes French grammatical rules. The number will be treated as any other number; possibly the operations you describe will go beyond the available memory of the calculator, resulting in a general error.
You know perfectly well (or at least you should know) that Godel’s system for representing the component elements of logic with prime numbers is arbitrary. This is irrelevant; will you next complain that Godel’s paper wasn’t written in English?
In brief: Probably not. Probably not. Probably not.
I think you’re very, very confused about what you’re talking about. Turing Machines do not take “problems” as input.
A problem is a language: a set of strings over some alphabet.
A Turing Machine is able to simulate an algorithm: an effective procedure for deciding membership of a string in a language.
The input to a Turing Machine is an instance of a problem: a string which the machine will endeavor to determine is in the language or not.
It does not make sense to talk of giving a problem as input to a Turing Machine.
Perhaps you mean to give some arbitrary TM an instance of the halting problem (that would be a description of a machine and an input to that machine). There are a whole lot of TMs that halt on all instances of the halting problem. It’s just that none of them give the right answer on all instances.
Your statements are much closer to the terms I suspect should be formally used, Newton meter; as a merely informal reasoner, I appreciate your attempt to clarify/criticize my position.
In brief: then where is it exactly that you imagine that GIT places some restriction on the behavior of calculators?
I do.
It is to me. You are the one who has made the claim that GIT poses some restriction upon calculators. You are also the one who has claimed that GIT applies to models.
So, what exactly do you mean by “GIT applies to calculators”, since you acknowledge that there is nothing at all special about the numerical representation of G?
will you next complain that Godel’s paper wasn’t written in English?
No. Will you next explain how a consequence specifically tied to the evaluation of Godel statements restricts a calculator when, "Calculators’ circuitry does not include the algorithms for evaluating Godel numbers?"
I haven’t even followed this discussion, but, at the risk of sounding stupid, I’m going to toss in my uninformed two cents…
GIT can be used to give an alternative proof of the impossibility of an algorithm to solve the Halting Problem. Turing machines can be easily modelled in a powerful enough formal axiomatic system, and such a system will, naturally, be able to handle integer addition and multiplication, bringing upon it the wrath of Godel. Using this modelling, if a particular Turing machine given a particular input ever halts with a particular output, that will be provable within the system.
Let’s assume the Halting Problem is algorithmically decidable. Now, given that the Halting Problem is decidable, you design a program which, given any theorem T, would run until it found a proof of that theorem. Such a program would halt iff that theorem was provable. You cleverly apply your magic halting-problem-solver (HPS) to that program and, poof (look at the last sentence of the above paragraph), you can either prove that HPS spits out “Yes” or prove that it spits out “No”. Either way, you’ll be able to prove whether or not T is provable. Now, add to your system the axiom ~Provable(~T)->T. This can’t cause contradictions, as it only adds the theorem T if “it knows” that ~T will never be proven.
Uh-oh. What’s that? Our system’s complete now? No, wait… GIT says that can’t be. I guess our assumption was wrong. The Halting Problem is not algorithmically decidable. GIT->Halting Problem is not decidable.
And, you know, the Halting Problem not being decidable… that imposes restrictions on all computing devices. Including calculators.
So, GIT imposes restrictions on calculators. In a sloppy, informal, probably terribly worded way, this has been proven. Q.E.D.
You lost me there. What if “it knows” that ~T will never be proven, and “it” likewise “knows” that T will never be proven? Are you assuming completeness…?
…and also incompleteness? No wonder you were able to reach a contradiction :).
One commonly sees the converse, see for example, Papadimitriou, Computational Complexity.
What about the TM that accepts every string? The TM that rejects every string? The TM that accepts strings beginning with zero? The halting problem doesn’t impose any restrictions on those machines.
The halting problem gives us an undecidable problem; a language that is recursively enumerable but not recursive. It does not mean that there are no recursive languages.
chinju
Had you followed this discussion, you might have realized that the “calculators” being discussed were not Turing Machines (much less Universal Turing Machines) but simply every day pocket number crunchers.
Beyond that, as Newton meter correctly called to your attention, the axiom ~Provable(~T)->T is false unless one assumes completeness, which is obviously inappropriate since you invoke GIT immediately thereafter.
In simple terms, when your magic HPS spits out “no” in response to input (~T) and algorithm (Peano arithmetic) it means that (~T) is not decidable.
It does not mean that (T) is either true or decidable. Undecidable (~T) has no implication for the truth value of (T).
As a point of interest, the halting problem can be used to demonstrate a weaker form of GIT (one that includes soundness among its conditions), and it certainly might be the case that such a proof could be reversed.
After I saw Chinju’s post, I started working on going from GIT to the undecidability of the halting problem. Ignoring the fact that I’d have to prove the theory of TMs consistent (yech!), I’d also have to show that it models first-order arithmetic. No thanks.
This is simply wrong. The halting problem is undecideable in the generic. It does not follow that whether any particular TM will halt is an undecideable question.
The physical laws governing the behavior of those circuits is more than sufficiently complicated for the Theorem to apply.
I am more than willing to accept that pocket calculators can be made essentially failure-proof for a limited set of possible inputs, but there are many more possible interactions with the material making up the device than any designer could anticipate.
Perhaps it would be simple enough if you modelled arithmetic, formed a Godel numbered statement, and used that number in a physical theory which is “more than sufficiently complicated” and see what happens.