We already know that physics is sufficiently complex to model arithmetic because we’ve built physical systems capable of doing so!
You’re not looking for proof, you’re looking for a long series of known mathematical symbols. Logical arguments do not need to be presented in a specific notation to be either valid or correct.
**
Yes it does.
If we build a little robot that examines marks on paper and makes additional marks according to certain rules, we’ve developed a system. GIT shows us that there are certain configurations of marks on paper that this system will never generate.
Making marks on paper with a soft graphite rod stuck in a hollow wooden shaft can also be considered to be a system – the laws that govern the behavior of the materials are subject to GIT too. The interactions of their component parts follow certain laws, and the Theorem guarantees that there are possible configurations that these laws cannot generate on their own – a larger system is necessary.
** Incorrect. There are always ways to make the computation more complex – if complexity were merely the resources required to solve a problem, it would be undefined, as any solution implies the existence of a more complex solution with unnecessary steps.
Complexity theory concerns itself with the minimum required resources to solve a problem, and this is directly concerned with the amount of information contained within the system. A “perfect” model of a system requires that the system be reproduced perfectly.
Running an L-glider in a life grid takes fewer resources than running it in a life meta-grid. This is trivially obvious: merely representing the five on-units of the glider in the meta-grid requires representing thousands of squares, while representing the five on-units of the glider takes only five grid squares.
It’s not a question of notation as much as it is a question of rigour, as I see it. GIT is a statement originally expressed in mathematical notation. As such, it is a very precise, abstract statement. Attempting to argue from GIT in English rather than in mathematical notation (unless you go into an obscene amount of detail) introduces imprecision. It does so by taking mathematical symbols with well-defined abstract meanings and attempting to make them correspond with real-world phenomena. It is essentially no different from an analogy. These analogies are often very good, just as the analogy between observed planetary motion and F = GmM/R^2 is very good. But such analogies are not automatically justified. They require corroborating observational data that shows the physical phenomenon accurately mimics the behaviour of the abstract system. The only observational data of this type that you’ve presented so far that is not speculative effectively boils down to the observation that computers can be crashed by extreme physical stimulus, for example a hammer. This does not mimic the behaviour of formal arithmetic systems described by GIT, in the opinion of myself and other posters in this thread.
In short you haven’t convinced us. But I imagine you guessed that.
In the robot scenario, the question merely shifts from the meaning of the marks to the meaning of the robot’s internal states. If I constrain myself to only put marks on the paper according to certain rules then the question shifts from the meaning of the marks to the meaning of the rules, i.e. the meaning of my internal state. GIT says nothing until the meaning of the marks or the states or the rules comes into the picture.
My source (Cohen, “Automata Theory”) presents these matters in such a way as to emphasize that the concepts form part of a continuum, to the point of suggesting a concurrent timeline involving Goedel and Turing. I claim to be no expert in the historyof mathematical study, so I will concede the historical point. However, as TMs can be used to generate statements of number theory, they do relate strongly to Goedel’s work.
My source uses the terms interchangeably. You can construct a TM that has a specific REJECT state, or you can simply let it die in a non-accepting state, which my source refers to as crashing.
You are correct. I did not mean to state my case in such a way as to imply that this could be done. Hey, it was 1:00AM. The point is, the undecidability of the halting problem says there is not way to know ahead of time how a given string will cause a given TM to behave. Some earlier posts seemed to me (again, it was 1 AM) to be trying to suggest that you could construct a physical machine that would accept every string, and only crash due a hardware failure. The undecidability of the Halting Problem says to me that you could never prove that such a machine performs in such a way.
True. BUT! Calculating sums, is in essence simply a matter of substitution of symbols: If I have “3 + 5” in front of me, I can substitute “8”, and mathematics says I am correct in doing this.
TMs accept languages called recursively enumerable (r.e.)languages. Let’s say I’ve built a UTM, “M”, that reads a certain set of symbols (its alphabet), and I wish to create TMs to run on M. I develop a Code Word Language (CWL), a consistent set of algorithms that takes definitions of TMs and their inputs and turns them into sets of symbols in M’s alphabet. So if I want to run string “a” through TM “T”, I create CWL(T) and CWL(a) and put them one after the other into M. CWL(T) sets up M in such a way that when I give it CWL(a), the resultant behavior of M EXACTLY simluates the behavior "T "would exhibit if it were fed “a”.
NOW: As long as it is a string of symbols in M’s alphabet, I can feed any old string into M’s simulation of T. Well, CWL(T) is a string in M’s alphabet, so what happens if I feed T to its own simulation? It will either accept the string or not (loop or crash). It turns out that the set of strings that are CWL translations of TMs that accept their own CWL translations as input form an r.e. language. That means you can build a TM that will accept this language.
What about the strings of CWL translations that represent TMs that can NOT accept their own CWL translations as input? It has been proven mathematically that the collection (language) of such strings is NOT r.e. It has also been shown that this language is NOT empty. Therefore, there is a class of languages that you CAN NOT build a TM (or by extension a UTM/computer) to accept. Because our brains CAN accept these languages, this seems to place an upper limit on the processing power of computers that will always be less than that of the brain.
Each string in one of these languages essentially states:
“I am a TM that can not accept myself as input”
My inderstanding of GIT is that Goedel’s statement was of the nature of Zeno’s paradox, essentially saying:
“I am a statement of number theory that is unprovable within the axiomatic system of mathematics”.
If proveable, it’s a false statement generated by the system, but if it’s not proveable, it’s true.
There is a certain shared nature about these two quoted statements, that leads to the thinking mentioned in the OP (and other places where I have seen similar assertions.
Whether or not someone has ever proven a connection, I’m afriad I do not know.
One more time, these types of models are not the types of models that are discussed in GIT. If you think they are, you must demonstrate so. Please use the statement of GIT that I posted on page 2.
**
No, but it does need to start with the correct definitions. You’re defining a sheep’s tail to be a leg and claiming its got five legs.
**
A “perfect” model in this sense may be less complex than the system it models. Are you familiar with Kolmogorov’s work?
Also, when you jump from discussing problems to systems, what systems are you talking about?
**
However, relative to the models of computation, the complexity is the same. The grid and the meta-grid are isomorphic.
OK, I’ve seen something like that before. Calling it crashing is unusual, though–everything I’ve seen refers to that kind of behavior as rejecting. In this discussion, the sense of crashing is that we have a machine with two final states, q[sub]accept[/sub] and q[sub]reject[/sub]. An input crashes a TM if it causes it to halt in some non-final state. That’s not possible with a properly designed TM.
**
I have a TM with two states, q[sub]0[/sub] and q[sub]accept[/sub]. On running, it examines the first cell of the input tape, writes the same character, transitions to q[sub]accept[/sub], and moves the head one cell right. This machines halts in an accepting state on every input, and it’s rather easy to prove that.
**
That’s still not connected to proving statements about number theory. I don’t think it’s the important part of your argument, though.
**
I discussed the connection earlier in this thread, I believe. If I haven’t, let me know, and I’ll describe it.
The modeling convention is arbitrary. For example, there are other ways to represent numbers that binary electric pulses. However, once we’ve established that convention, the configuration of the system is non-arbitrary.
For a specific convention, a set of logic gates is addition: it does everything addition does. The behavior of the gates is consistent with the concept of addition.
Symbols can be empty only if they’re used as memory for a system in which they’re actually significant.
What about the situation where the input tape contains the empty string (i.e., there is no input?)? If you tell me that this input, too, causes the transition, then the input is irrelevant, and your case is a trivial one. You have shown nothing but that I should have restricted my discussion to non-trivial cases.
**
Your trying to tell me that proving mathematical theorems never involves symbol manipulation. You’ll have to back that one up for me.
What about any TM that visits each state exactly once? Or a machine that never writes to the input tape and only moves its head to the right? There are many special cases for which the halting problem is decidable. If you ignore those, then yes, the halting problem describes all instances, but that doesn’t seem like much of a victory for you.
**
No, actually I’m claiming that being able to perform calculations is never important for theorem-proving.
I don’t understand your little robot very well, so I’m going to go back to Turing Machines. Are you saying the there are certain strings that cannot ever be found on a Turing Machine’s tape, and that this is required by GIT?
That is wrong. A TM can be built that accepts every string (remember that the string on the tape when the machine starts is finitely long). A TM can be built that enumerates all finite strings.
I imagine you could suggest that a lot of people doing work in this field in the '30s and '40s were on a “concurrent timeline involving Goedel”.
I think that is sloppy, and unfortunate, too. A TM can halt or not. It does not “crash”. If it hasn’t halted yet, it just hasn’t halted (shades of the halting problem, here). If it never halts, it does not halt. If it halts and it’s not in an accept state, it rejected the input. It did not crash.
Neither of the only two references I have on hand, Papadimitriou’s Computational Complexity nor Hopcroft and Ullman’s Introduction to Automata Theory, Languages, and Computation use “crash” to describe failure to halt on an input or rejecting an input.
More pedantry from me. If you are talking about a given string and a given TM, then you have a single instance of the halting problem. It is trivial to build a TM to decide that instance:
There is a TM, call it M1, that rejects every string. There is a TM, M2, that accepts every string. For a given Turing Machine and a given string, the machine will either halt or not halt on that string as input. One of the machines M1 or M2 decides this problem correctly.
This is because, as Spiritus has said (three times? four?) decidability and completeness are not the same thing! That is, we might have some statement of number theory that cannot be proven, and whose negation cannot be proven, and there still exists a TM that “decides” it.
Sure you can. It’s easy. Read to the end of the tape. Accept. If you don’t require me to read all the tape, I’ll just enter an accept state from the start state.
I don’t know how that machine will fail, other than some “hardware failure”.
Nothing says that it is necessarily hard for a particular machine to prove that it halts for a particular input, or even all inputs. Your challenge is to construct such a machine, that’s easy.
True. They can also decide recursive languages, and compute primitive recursive functions…
Yes, there are languages that are not recursively enumerable. If a language and its complement are both r.e., then the language is recursive. The existence of a language that is r.e. but not recursive implies the existence of a language that is not r.e. (namely, its complement).
But I’m puzzled how you think that your brain is able to “accept” a language that is not r.e.–take the complement of H (the language whose strings are descriptions of TM’s M and inputs x such that M halts on x)?
I’m serious. It would be a cool party trick, and a real boon for my work. When posed with an undecidable problem I could just pop up a GUI window and ask the user to tell me the answer.
Well, the tape is infinite to the right. And there is a distinguished blank symbol, call it B. “The input tape contains the empty string” means that the first (and indeed, all) symbol is B.
ultrafilter’s machine works just fine in that case.
It computes the identity function. You might call that trivial, but I call it fundamental.
TVAA
I have already said that I see no point in repeating an endless process of “No, it doesn’t” “Yes it does” statements with you. You are making statements in this htread that are factually incorrect. You are using terminology in a manner that is inconsistent with standard usage in the fields of computer science and mathematics.
That depends upon what you mean by “model”, which is the question I have been asking you to answer.
Apparently, you mean “can be described by the same mathematical equations”. Is that accurate?
This is an unspported assertion on your part. Actually, it is two unsupported assertiond.
IN EXACTLY WHAT MANNER DO YOU MEAN “electrons contain arithmetic” TO BE INTERPRETED?[
Really. It is very important for you to answer specific questions if you expect anybody who understands GIT to think that your position is anything other than a SWAG without the S.
You have provided no reasonable suport for that assertion.
Element: a member of a set. In this case, an irreducible component part of a system. (What is irereducibvle, of course, alters with the level of analysis.)
See, it isn’t so hard. Now please define “model” and “complexity” as you use the terms.
No, it is not. In mathematics, as in computer science, complexity has a specific meaning. You are using the term improperly. Did you even bother to follow the link I provided? An order N algorithm with 2 pieces of input has exactly the same complexity as an order N algorithm with 2 million pieces of input.
It serves no useful purpose for you to misuse terminology and then make pronouncements of fact based upon your variant meanings for words.
Yes, but that is because of the rules we have encoded in the robot, not some fantasy that there is a limitation on what marks can ever be placed on a piece of paper because of GIT.
The only thing GIT tells us about marks on a paper is that there is no way to ever interpret marks on paper to be a proof of certain valid number theoretic statements because no such proofs can exist. This is a limitation of math, not a limitation of pencil and paper.
What you are saying is analagous to: It’s impossible to write down the method for squaring a circle using geometric construction because the electrons are can’t move in a certain way.
No, the statement was correct. Your statement is confused.
Perhaps this is because you are using terms in a non-standard manner. Perhaps it is because you do not understand the concepts. I cannot tell which. In computational theory, a problem is simply a set of strings representing input and a set of strings representing output. An algorithm is a method for mapping input strings to output strings. Complexity is a measure of algorithms, (the things that “solve” problems). Sometimes a problem is discussed as including both the sets of strings and a mapping algorithm. In such contexts, you might see the unrigorous phrase “complexity of the problem”, but the meaning is always “complexity of the algorithm included in the problem definition”. Changing the algorithm can certainly result in a new algorithm with different complexity, and it is certainly correct that problems can be solved by more than one algorithm. Saying that this changes the complexity of a problem, though, betrays a deep misunderstanding of the standard terminology. Complexity is a measure of algorithms.
By the way, “minimum” adds no meaning to the statement “resources required”. Anything that could be removed to “minimize” the set was obviously not required. N’est ce pas?
That is what I said, though I did not include superfluous modifiers.
This statement is simply and unambiguously false.
Complexity is not a measure of information within a system. Outputing an input string is an algorithm of order N, no matter how many characters are in the string. Complexity is expressed as a function of the size of input. Please pay attention to the bolded part of that statemnet. Complexity==the function, not some value for the function given a specified input string.
scotandrsn
Only in the very specific manner that I explained above. A TM that is generating statements of number theory is constrained by GIT so that it may not generate all true statements. GIT has no general implication for TMs that are not generating statements of number theory.
Really, this should not be that ahrd a concept to grasp.
This is incorrect. The halting problem unsolveable for every specific case. The halting problem is a statemeng about generic halting algorithms.
This is correct. It is simple to conceive such a machine.
[ul][li]Given any input: output 0 and halt[/ul][/li]
You are not hearing what the halting problem is actually saying.
Well, it is a side issue, but one would first have to prove that human brains can “accept” these languages in a manner that is sufficiently similar to the CLW translation before that statement could be taken as correct. Then, of course, there are the implications of the fact that each language can, in fact, be accepted as input by “M” so merely showing that a human brain can acept the language does not actually provide a hard distinction form the class of UTMs.
It is an interesting side discussion, though.
Similarity in method does not imply logical equivalence. The same is true of GIT and the halting problem.
newton meter
I compose replies as I read, so I just got to your post and see you have said everything that I am about to with far less “tape”. (Actually, ultrafilter covered many of the high points already, too.)
Oh well. My algorithm says I should hit “submit” now regardless of input.
** You’re not pointing out what statements you think are wrong and then demonstrating that they are wrong – you’re simply denying my argument over and over again. My position is wrong because the statements I use to describe it are wrong, and the statements are wrong because my position is wrong.
For example, you claim that the meta-grid that can be constructed with the standard grid of Life is as complex as the grid itself. This is not only incorrect, it’s stupid. However many resources are necessary to simulate a basic square, the resources for a meta-square are necessarily greater. I don’t know what the simplest possible pattern that emulates the unit square is, but at an absolute minimum, it cannot be less than two. Therefore the meta-grid takes at least twice as much memory to implement as the grid itself.
The words I’m using all have well-defined meanings in standard English. If you can’t handle that, get off the boards. I’m quite serious – if you can’t rationally consider arguments made in everyday language, you have no place on boards where the arguments are presented in that format.
A model is a system – a set of interactions – that manifests properties similar to those of another system. This is inherent in the dictionary definition of the word.
I’m saying that, although the two systems exist on different level of implementation, their high-level behavior is the same. They do the same things.
It is not an assertion. It’s a consequence.
If I say “A equals B, B equals C, so A equals C”, this is not an assertion either. It’s a consequence of the definition of equality; verifying this requires only substituting across equivalencies.
The behavior of electrons is such that they can be used as the foundation of a system, on a higher level of implementation, that can perform arithmetic. Therefore their behavior necessarily can demonstrate statements about arithmetic.
I have shown you the dots. You should be sufficiently intelligent to be able to connect them yourself.
Element: a basic component of a system.
Complexity: the amount of data required to perfectly define a system. This is a greatly condensed version of the general language definition of “complex”.
** The implementation of the algorithm is not equally complex in both cases!
** I informed you quite a while ago that I’m communicating in the standard language. You’re the one that applies field-specific terminology inappropriately.
** *The interaction between the writing implement and the piece of paper can be described by a system of basic rules. There will always be statements allowed by the grammar of the components of those rules that the rule system cannot reach. As a result, there will necessarily be possibilities that the implement-paper system cannot manifest on its own.
No system designed to generate “new” statements according to a finite set of axioms will ever produce Godel’s famous statement. If it could do so, that set of steps would be a proof of the statement.
The workings of the universe generate configurations according to basic axioms.
Connect the dots.
** The pencil and paper are being emulated by a deeper level of reality in the same way that a meta-grid is emulated by a grid in Life. They are necessarily limited!
No.
**
[sigh] The resources required to represent a specific pattern with the meta-grid are necessarily greater than the resources needed to represent that pattern with the basic grid. By the (inappropriate) definitions you’ve already offered, I conclude that you’re mistaken.
** For the last time, I AM NOT USING COMPUTER SCIENCE TERMINIOLOGY!
** I’m saying that if the Turing Machine operates according to set rules, and those rules are sufficiently complex, there will be possible symbol configurations that the TM will never be able to reach. Different notations will result in different configurations of symbols, but the relationship between the notation and the configurations will be constant.
