4 ms·

I suspect someone could write a book (or an HN comment at least) about the popular confusion about Godel's 1st incompleteness theorem. :-) In fact we (my broth

I suspect someone could write a book (or an HN comment at least) about the popular confusion about Godel's 1st incompleteness theorem. :-) In fact we (my brother and I) agreed that it bears a striking resemblance to Turing's halting problem: They both seem to show what computers or math can't do, but in fact both theorems only reveal limitations of certain models of computers and/or math. We both have undergrad degrees in math fwiw. Both theorems use a clever logical trick. For Godel's theorem, it is an encoding of "This sentence is false". For the halting problem proof, Turing first fixes the algorithm, asks the algorithm what its result will be, then switches the correct answer, forcing the algorithm to produce the incorrect answer. Would the proof completely fall apart if the algorithm could update itself to handle the new information? The only thing stopping it is that in the formulation of the problem, the algorithm is assumed to not be able to change with new information (ie it's not an "online" algorithm). Similarly, what if the model of math had mechanisms for recognizing paradoxes, or circular logical requirements, etc. I don't think either of those theorems would work anymore. Anyway, I'm not saying the Halting problem would be easy to compute with the right model. If we had an efficient algorithm to solve the halting problem, we could solve tons of math problems easily. We could write some code to enumerate any countably infinite sequence, checking for the presence of some condition, and make inferences based on if it halts or not. For example, we could solve the Collatz conjecture by just writing code to halt if any number's sequence doesn't eventually go to one, and checking whether that loop ever halts. My punchline is, I think it's beautiful that even the undecidable, uncomputable problems are only that way because we are lacking a better model. Or at least that's my current understanding of the situation :-)

thethirdone 5y ago
> Would the proof completely fall apart if the algorithm could update itself to handle the new information? The only thing stopping it is that in the formulation of the problem, the algorithm is assumed to not be able to change with new information (ie it's not an "online" algorithm). Simple put the halting problem means that you cannot make a program (a static piece of code) that can determine in a finite amount of time if another program halts operating on some input. I.E. program P takes program H and input I and answers if H run with I halts. I honestly don't know what part of the computational model could be changed to make that not true (besides Oracles or Church-Turing thesis being wrong). Also, I don't think "online algorithm" means what you think it means. Online algorithms have no more computational power than offline ones; they just can get started with only partial information. > Similarly, what if the model of math had mechanisms for recognizing paradoxes, or circular logical requirements, etc. I don't think either of those theorems would work anymore. I don't know what a model of recognizing paradoxes would look like. The 1st incompleteness theorem is based on only a few simple axioms and reasonable rules of deduction. There isn't much wiggle room to make a mathematical model that isn't bound by it, but is useful.
- srcreigh 5y ago
  > The halting problem means that you cannot make a program (a static piece of code) that can determine in a finite amount of time if another program halts operating on some input. Interesting. My first thought was, couldn't we just create programs that are designed to keep growing? Isn't that both completely possible and more powerful than the model of computing where programs are static? I realized it may not be entirely possible to build an actual machine which hosts endlessly growing code. There are probably laws of physics which put some type of limit on how big things we build can get.
  - thethirdone 5y ago
    > Interesting. My first thought was, couldn't we just create programs that are designed to keep growing? Isn't that both completely possible and more powerful than the model of computing where programs are static? What does it mean to "create programs that are designed to keep growing"? If they keep going by executing a finite program (if modified by a non-static program, what created that program?) on their code and resuming, that would not be more powerful (Turing machines can do that). > I realized it may not be entirely possible to build an actual machine which hosts endlessly growing code. There are probably laws of physics which put some type of limit on how big things we build can get. So long as you have enough memory, even an Intel 8086 would be able to compute arbitrarily large programs. It could just emulate a universal Turing machine.
    - srcreigh 5y ago
      > What does it mean to "create programs that are designed to keep growing"? If they keep going by executing a finite program (if modified by a non-static program, what created that program?) on their code and resuming, that would not be more powerful (Turing machines can do that). To me, your question is like asking this: Do all the programs that we humans ask computers to compute come from a finite program? Is life itself powered by a finite program? A program which keeps growing can make use of all the code it has seen before, all the results it has seen from running code previously. Although any of its inputs are finite strings, there are no theoretical limitations regarding the source of the inputs it can receive. They come from outside. The core idea of the undecidability of the halting problem is that we can construct a machine M that can ask the halting machine for a bit, flip the bit, give it back to the same static halting machine code, thus forcing it to produce the wrong bit. Any human in that situation would change their understanding of the situation, and we would tend to afford them a chance to change their answer based on their new understanding. Being able to adjust execution strategy after seeing new information is core to human life. Why do we neglect to provide computers opportunities which are available to all humans? A somewhat trivial reply to Turing's original negator machine M would be to emit a new version of the halting code which checks for the exact code given by M and then returns the opposite of what was returned when M calls out to H. Then, in the argument, we would need to address the possibility that the H machine called out in M to may provide a different answer when we pass it all back through H again. The argument wouldn't work as-is if we afforded H the ability to respond to the situation. What would the statement be? "It is not possible, given the information the halting code just received, it could change its answer response to the contradiction of its previous answer." A child can figure out this simple trick - we all understand why it's a trick - why do we not let a computer the same opportunity in our theory? > So long as you have enough memory, ... True enough. My point was in fact that if the inputs our machine receives are all needed, we would run out of memory eventually.
EamonnMR 5y ago
I like to think of the halting problem as similar to the inability to predict the future. In order to predict the future you'd need a model of the whole universe, including the model. Once you think of it like that you realize that you can't beat halting in the classical universe.
- hansvm 5y ago
  The halting problem has that same style of thinking, but the universe doesn't necessarily play by such rules. For one, it's still an open question whether the universe could properly contain a model of itself (hence, needing a model of the universe plus the model isn't a guaranteed absurdity).
  - EamonnMR 5y ago
    It is an absurdity though. You would need a material that can encode more information than it takes to physically represent it.
geofft 5y ago
Suppose the algorithm could update itself with new information. Then you can formulate it in one of two ways: 1. The process of updating the algorithm can, itself, be described by a Turing machine. Think of it like an emulator / debugger (since a universal Turing machine exists, i.e., you can write an evaluator for a Turing machine as a Turing machine). The outer Turing machine can run the inner one partially, realize it needs changes, update it, and then continue running it and return its output. But then the outer Turing machine, which is self-contained, is itself subject to the halting problem, and you can construct the counterexample based on it. You've just made the machine bigger. 2. The process of updating the algorithm cannot be described by a Turing machine. Perhaps it involves some sort of higher form of intelligence which itself cannot be represented as a Turing machine (so, if you want to say "a human updates it," you're working on the assumption that the human brain cannot be implemented/emulated - however slowly - on a Turing machine, and the decisions of how to update the algorithm require this supra-Turing computational power). But then, as before, the actual machine is this combination of the extra intelligence and the Turing machine. You've made some stronger non-Turing machine to solve the problem, and the statement "No Turing machine can determine whether any arbitrary Turing machine halts" still holds true. You've introduced a new class of machines with additional power over Turing machines. And the halting problem now applies to these machines when evaluating whether a machine of their own class halts, even though they can determine whether simpler machines halt. Your human-Turing mechas can solve the halting problem for Turing machines, but they cannot solve it for other human-Turing mechas. See https://en.wikipedia.org/wiki/Turing_jump https://en.wikipedia.org/wiki/Turing_jump In fact, this model, applied to Gödel's theorem, was explored in Turing's own Ph.D. thesis: https://en.wikipedia.org/wiki/Systems_of_Logic_Based_on_Ordinals https://en.wikipedia.org/wiki/Systems_of_Logic_Based_on_Ordi...
- srcreigh 5y ago
  Thanks for response! I will definitely read about Turing jumps :) I'm not sure I understand your 1. Reading the Halting problem undecidability proof, it goes like this: Suppose machine H can solve the halting problem. We construct special machine M which calls H(M), and negates the output. Then when we run H(M), it halts if M doesn't halt, and doesn't halt if M halts, hence M doesn't exist. On the other hand, if H could self-modify, we would have a sequence H_0,H_1,... of machines based on its modifications. Ie, M is written with H_i, but later we're calling H_j(M). No guarantee that our negation still works.
jcranmer 5y ago
Gödel's Incompleteness Theorem and the undecidability of the halting problem can in fact be proved using each other, so there is good reason to think that there is a deeper connection. What you suggest isn't actually possible, and to explain why, it's worth stepping back a little bit. Originally, there was a program to formalize mathematics that came to be known as naïve set theory. This theory ran into a major roadblock when Russell proposed a paradox: does the set of all sets that do not contain themselves contain itself? The solution to this, as found in modern set theory, is to very carefully construct sets in such a way that no set can contain itself in the first place, and so the very question isn't expressible in the logic of modern set theory. The underlying point of both Gödel and Turing is, as you say, constructing a similar statement akin to "this statement is false." But more specifically, what they actually did was to show that, once you meet some relatively low barriers, it is impossible to make a system that omits that construct. In effect, what is done is to encode (respectively) proofs and programs into integers, and then using this encoding, shows that you can always create a self-reference that blows up. Yes, if you change the encoding, it requires a potentially different number to create the self-reference, but the point is that so long as there is a bijection to the natural numbers, then the problematic self-reference must exist. And, as you may be able to reflect upon, everything we as humans can write or speak can be reduced to a finite-length string of a finite-symbol alphabet, so everything we create must be bijectable with the natural numbers if infinite.
- srcreigh 5y ago
  I am honoured to have nerd-sniped you, jcranmer. I won't respond at length as I have in some of the child threads here. As far as I can tell in my other expositions, apparently I object to the very fact that mathematicians like to fix things and make inferences about them! I think some things, such as computation, humans, animals, etc, should be allowed to be sensitive to time and prior inputs.. and the very act of fixing now and inferencing later seems to infringe upon that right. That may be the lowest barrier of all of mathematics! Cheers my friend, thank you for engaging.
  - cryvate1284 5y ago
    "apparently I object to the very fact that mathematicians like to fix things and make inferences about them": that's not really what's going on: time can be present in mathematics (e.g. defining a sequence iteratively) and the like. What you do have to fix is the definition of things: your reasoning is very shaky, and once you would start formalizing things you will find you cannot "defeat" the Halting problem or incompleteness theorem.
galaxyLogic 5y ago
I found this nice presentation about Godel's theorems. https://youtu.be/HeQX2HjkcNo?t=895 https://youtu.be/HeQX2HjkcNo?t=895 "There is no proof for the statement with Godel-number g". What I'm struggling with is trying to understand if self-reference can be formally represented by some symbol. Can it? Godel's proof seems to rely on a trick that allows a formal system to talk about itself but is that possible? There would need to be a symbol for that and thus a symbol that refers to itself? A picture of a pipe is not a pipe. Similarly a representation of a proof is not a proof, is it?. Not saying I believe I'm right and Godel wrong, but it just feel strange to me that a formal system could ever "prove" anything about itself. What does it mean that something is "true"? That it can be proven?
- zuminator 5y ago
  Not every picture of a pipe is a pipe but it's at least conceivable that an actual working pipe can be constructed out of something which happens to be a picture of a pipe. Similarly Godel isn't proving that all statements in a system are paradoxically self-referential. Only that given any system of sufficient complexity, one can conceivably be constructed. In any event, all of our mathematical proofs are predicated upon the idea that the representation of a mathematical object can be treated in terms of proof as equivalent to the mathematical object. Is "2" the number 2 or is it just a glyph that non-representationally depicts the successor of the first counting number? And if you believe the latter, then how do you go about proving anything about the actual successor of the first counting number without resorting to glyphs?
  - galaxyLogic 5y ago
    > given any system of sufficient complexity, That's my question. It seems that adding "self reference" to the system makes it more complicated than it would be otherwise. So it's not just a system with enough complexity to let you do arithmetic. You need a system with enough complexity to also do self-reference. And I would say and think that self-reference is complicated. Do we need self-reference in any other areas of mathematics, than Godel's and related proofs?
throwaway81523 5y ago
> I suspect someone could write a book (or an HN comment at least) about the popular confusion about Godel's 1st incompleteness theorem. :-) That book has already been written: https://www.ams.org/notices/200703/rev-raatikainen.pdf https://www.ams.org/notices/200703/rev-raatikainen.pdf
eynsham 5y ago
> reveal limitations of certain models of computers Modulo weird stuff with black holes or whatever (not that I am qualified to understand whether they count), there are no known counterexamples to the Church-Turing thesis.
hvidgaard 5y ago
> Would the proof completely fall apart if the algorithm could update itself to handle the new information? The only thing stopping it is that in the formulation of the problem, the algorithm is assumed to not be able to change with new information (ie it's not an "online" algorithm). First an online algorithm is an algorithm that process a stream instead of the full input. It's not because it changes. Regarding the halting problem, lets assume that you give me a program can change itself and you claim solves the halting problem. Use Turings proof on that and it proves that you have not solved the halting problem for all inputs, because it just gave you one that it produced the wrong answer for.
yayachiken 5y ago
Your comment made me break down and finally make an HN account. I think I may have the perfect answer for you. Your comments remind me so much of myself, when I was in 7th grade and we just learned that 0.999... would exactly equal 1. Not almost, but exactly. I know that I asked my math teacher tricky questions, and left really unsatisfied, because "obviously it's not true", probably my teacher does not understand infinity. I kind of forgot about it, and it only really clicked a couple years later once I learned about series and limits, because I finally gained an intuition for working with infinity. A very important notion about infinity that the terms "For any arbitrary large N" and "For Infinity" are not the same thing. I actually think that the cause of the confusion is similar. Maybe your mental model of computation includes an "arbitrarily large N" where you actually need an "infinitely large N". Note that the halting problem (and a whole bunch of other interesting undecidable problems) is actually "semi-decidable". This means we are guaranteed to get an answer to the question, but only if the answer is actually "yes". (Before you ask: Taking the inverse of a problem does not preserve semi-decidability, so no trickiness here.) We need some intermediate results here. I am not going to prove them for brevity (and because I will probably be unable to produce them right now), so you'll have to trust me for them. Sorry! A Turing machine P which gets input i produces output P(i). We can construct a machine P_i which ignores its input, but instead always produces P(i) for any i. We can also construct for any P an encoding Enc(P) (the "source code" so to say, actually a Gödel numbering) which encodes the turing machine. We can also show that there is a universal turing machine U which for any Enc(P) will produce the same outputs as P for all possible inputs i. We can also construct a special limited universal turing machine U_j which halts after at most j steps. So how does semi-decidability work in practice: Let us simulate a turing machine P on U_1. If it halts, we return 1, if it does not halt after 1 step, we return 0. This turing machine will solve the halting problem for all turing machines that halt after 1 step. We can then look at U_2, U_3 and so on, and those machines will always solve the halting problem for a strict superset of the others. So we know that the number of turing machines which do not have a solution by our ever increasing set of halting problem deciders will get smaller and smaller. The halting problem now says: Even if all machines of {U_j : j is natural number} run in parallel, we will always have Turing machines P for which we will not get an answer. The halting problem also tells us that there will never be a U_infinity, which would then give us the answer. If you don't like the self-referential proof, you can check out the diagonalization proof, which is more rigorous. Now you have given examples of for example humans adapting to additional input. We know for a fact that humans in their lifetime can only perform a finite number of computational operations, and parse a finite number of input arguments. If I was a physicist I could probably cite some theorem of thermodynamics to give you an upper bound on that number, which is probably astronomically huge but finite. The same applies for the computing power of the universe. Huge, but finite. This is all the halting problem says: We can solve a lot of problems by brute force, but never all of them. We can also solve all problems approximately by just giving an arbitrary (but fixed) answer after we get bored with our long-running turing machine. The halting problem is important because for all we know and care, and infinite computer cannot physically exist, as the universe itself is finite. For example, the halting problem can be solved by a theoretical computer which speeds up by factor 2 on every step. And probably also something like a machine which has an exact encoding for every real number, which cannot exist in the universe as we currently understand it, for similar reasons. https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation It's not that we cannot think of those models, it is just that they are completely useless and uninteresting as they get too powerful, but also impossible to build. You could approximate them, but the approximation is useless, as the approximation will again be a convoluted turing machine.

thethirdone 5y ago

> Would the proof completely fall apart if the algorithm could update itself to handle the new information? The only thing stopping it is that in the formulation of the problem, the algorithm is assumed to not be able to change with new information (ie it's not an "online" algorithm). Simple put the halting problem means that you cannot make a program (a static piece of code) that can determine in a finite amount of time if another program halts operating on some input. I.E. program P takes program H and input I and answers if H run with I halts. I honestly don't know what part of the computational model could be changed to make that not true (besides Oracles or Church-Turing thesis being wrong). Also, I don't think "online algorithm" means what you think it means. Online algorithms have no more computational power than offline ones; they just can get started with only partial information. > Similarly, what if the model of math had mechanisms for recognizing paradoxes, or circular logical requirements, etc. I don't think either of those theorems would work anymore. I don't know what a model of recognizing paradoxes would look like. The 1st incompleteness theorem is based on only a few simple axioms and reasonable rules of deduction. There isn't much wiggle room to make a mathematical model that isn't bound by it, but is useful.

srcreigh 5y ago
> The halting problem means that you cannot make a program (a static piece of code) that can determine in a finite amount of time if another program halts operating on some input. Interesting. My first thought was, couldn't we just create programs that are designed to keep growing? Isn't that both completely possible and more powerful than the model of computing where programs are static? I realized it may not be entirely possible to build an actual machine which hosts endlessly growing code. There are probably laws of physics which put some type of limit on how big things we build can get.
- thethirdone 5y ago
  > Interesting. My first thought was, couldn't we just create programs that are designed to keep growing? Isn't that both completely possible and more powerful than the model of computing where programs are static? What does it mean to "create programs that are designed to keep growing"? If they keep going by executing a finite program (if modified by a non-static program, what created that program?) on their code and resuming, that would not be more powerful (Turing machines can do that). > I realized it may not be entirely possible to build an actual machine which hosts endlessly growing code. There are probably laws of physics which put some type of limit on how big things we build can get. So long as you have enough memory, even an Intel 8086 would be able to compute arbitrarily large programs. It could just emulate a universal Turing machine.
  - srcreigh 5y ago
    > What does it mean to "create programs that are designed to keep growing"? If they keep going by executing a finite program (if modified by a non-static program, what created that program?) on their code and resuming, that would not be more powerful (Turing machines can do that). To me, your question is like asking this: Do all the programs that we humans ask computers to compute come from a finite program? Is life itself powered by a finite program? A program which keeps growing can make use of all the code it has seen before, all the results it has seen from running code previously. Although any of its inputs are finite strings, there are no theoretical limitations regarding the source of the inputs it can receive. They come from outside. The core idea of the undecidability of the halting problem is that we can construct a machine M that can ask the halting machine for a bit, flip the bit, give it back to the same static halting machine code, thus forcing it to produce the wrong bit. Any human in that situation would change their understanding of the situation, and we would tend to afford them a chance to change their answer based on their new understanding. Being able to adjust execution strategy after seeing new information is core to human life. Why do we neglect to provide computers opportunities which are available to all humans? A somewhat trivial reply to Turing's original negator machine M would be to emit a new version of the halting code which checks for the exact code given by M and then returns the opposite of what was returned when M calls out to H. Then, in the argument, we would need to address the possibility that the H machine called out in M to may provide a different answer when we pass it all back through H again. The argument wouldn't work as-is if we afforded H the ability to respond to the situation. What would the statement be? "It is not possible, given the information the halting code just received, it could change its answer response to the contradiction of its previous answer." A child can figure out this simple trick - we all understand why it's a trick - why do we not let a computer the same opportunity in our theory? > So long as you have enough memory, ... True enough. My point was in fact that if the inputs our machine receives are all needed, we would run out of memory eventually.

EamonnMR 5y ago

I like to think of the halting problem as similar to the inability to predict the future. In order to predict the future you'd need a model of the whole universe, including the model. Once you think of it like that you realize that you can't beat halting in the classical universe.

hansvm 5y ago
The halting problem has that same style of thinking, but the universe doesn't necessarily play by such rules. For one, it's still an open question whether the universe could properly contain a model of itself (hence, needing a model of the universe plus the model isn't a guaranteed absurdity).
- EamonnMR 5y ago
  It is an absurdity though. You would need a material that can encode more information than it takes to physically represent it.

geofft 5y ago

Suppose the algorithm could update itself with new information. Then you can formulate it in one of two ways: 1. The process of updating the algorithm can, itself, be described by a Turing machine. Think of it like an emulator / debugger (since a universal Turing machine exists, i.e., you can write an evaluator for a Turing machine as a Turing machine). The outer Turing machine can run the inner one partially, realize it needs changes, update it, and then continue running it and return its output. But then the outer Turing machine, which is self-contained, is itself subject to the halting problem, and you can construct the counterexample based on it. You've just made the machine bigger. 2. The process of updating the algorithm cannot be described by a Turing machine. Perhaps it involves some sort of higher form of intelligence which itself cannot be represented as a Turing machine (so, if you want to say "a human updates it," you're working on the assumption that the human brain cannot be implemented/emulated - however slowly - on a Turing machine, and the decisions of how to update the algorithm require this supra-Turing computational power). But then, as before, the actual machine is this combination of the extra intelligence and the Turing machine. You've made some stronger non-Turing machine to solve the problem, and the statement "No Turing machine can determine whether any arbitrary Turing machine halts" still holds true. You've introduced a new class of machines with additional power over Turing machines. And the halting problem now applies to these machines when evaluating whether a machine of their own class halts, even though they can determine whether simpler machines halt. Your human-Turing mechas can solve the halting problem for Turing machines, but they cannot solve it for other human-Turing mechas. See https://en.wikipedia.org/wiki/Turing_jump https://en.wikipedia.org/wiki/Turing_jump In fact, this model, applied to Gödel's theorem, was explored in Turing's own Ph.D. thesis: https://en.wikipedia.org/wiki/Systems_of_Logic_Based_on_Ordinals https://en.wikipedia.org/wiki/Systems_of_Logic_Based_on_Ordi...

srcreigh 5y ago
Thanks for response! I will definitely read about Turing jumps :) I'm not sure I understand your 1. Reading the Halting problem undecidability proof, it goes like this: Suppose machine H can solve the halting problem. We construct special machine M which calls H(M), and negates the output. Then when we run H(M), it halts if M doesn't halt, and doesn't halt if M halts, hence M doesn't exist. On the other hand, if H could self-modify, we would have a sequence H_0,H_1,... of machines based on its modifications. Ie, M is written with H_i, but later we're calling H_j(M). No guarantee that our negation still works.

jcranmer 5y ago

Gödel's Incompleteness Theorem and the undecidability of the halting problem can in fact be proved using each other, so there is good reason to think that there is a deeper connection. What you suggest isn't actually possible, and to explain why, it's worth stepping back a little bit. Originally, there was a program to formalize mathematics that came to be known as naïve set theory. This theory ran into a major roadblock when Russell proposed a paradox: does the set of all sets that do not contain themselves contain itself? The solution to this, as found in modern set theory, is to very carefully construct sets in such a way that no set can contain itself in the first place, and so the very question isn't expressible in the logic of modern set theory. The underlying point of both Gödel and Turing is, as you say, constructing a similar statement akin to "this statement is false." But more specifically, what they actually did was to show that, once you meet some relatively low barriers, it is impossible to make a system that omits that construct. In effect, what is done is to encode (respectively) proofs and programs into integers, and then using this encoding, shows that you can always create a self-reference that blows up. Yes, if you change the encoding, it requires a potentially different number to create the self-reference, but the point is that so long as there is a bijection to the natural numbers, then the problematic self-reference must exist. And, as you may be able to reflect upon, everything we as humans can write or speak can be reduced to a finite-length string of a finite-symbol alphabet, so everything we create must be bijectable with the natural numbers if infinite.

srcreigh 5y ago
I am honoured to have nerd-sniped you, jcranmer. I won't respond at length as I have in some of the child threads here. As far as I can tell in my other expositions, apparently I object to the very fact that mathematicians like to fix things and make inferences about them! I think some things, such as computation, humans, animals, etc, should be allowed to be sensitive to time and prior inputs.. and the very act of fixing now and inferencing later seems to infringe upon that right. That may be the lowest barrier of all of mathematics! Cheers my friend, thank you for engaging.
- cryvate1284 5y ago
  "apparently I object to the very fact that mathematicians like to fix things and make inferences about them": that's not really what's going on: time can be present in mathematics (e.g. defining a sequence iteratively) and the like. What you do have to fix is the definition of things: your reasoning is very shaky, and once you would start formalizing things you will find you cannot "defeat" the Halting problem or incompleteness theorem.

galaxyLogic 5y ago

I found this nice presentation about Godel's theorems. https://youtu.be/HeQX2HjkcNo?t=895 https://youtu.be/HeQX2HjkcNo?t=895 "There is no proof for the statement with Godel-number g". What I'm struggling with is trying to understand if self-reference can be formally represented by some symbol. Can it? Godel's proof seems to rely on a trick that allows a formal system to talk about itself but is that possible? There would need to be a symbol for that and thus a symbol that refers to itself? A picture of a pipe is not a pipe. Similarly a representation of a proof is not a proof, is it?. Not saying I believe I'm right and Godel wrong, but it just feel strange to me that a formal system could ever "prove" anything about itself. What does it mean that something is "true"? That it can be proven?

zuminator 5y ago
Not every picture of a pipe is a pipe but it's at least conceivable that an actual working pipe can be constructed out of something which happens to be a picture of a pipe. Similarly Godel isn't proving that all statements in a system are paradoxically self-referential. Only that given any system of sufficient complexity, one can conceivably be constructed. In any event, all of our mathematical proofs are predicated upon the idea that the representation of a mathematical object can be treated in terms of proof as equivalent to the mathematical object. Is "2" the number 2 or is it just a glyph that non-representationally depicts the successor of the first counting number? And if you believe the latter, then how do you go about proving anything about the actual successor of the first counting number without resorting to glyphs?
- galaxyLogic 5y ago
  > given any system of sufficient complexity, That's my question. It seems that adding "self reference" to the system makes it more complicated than it would be otherwise. So it's not just a system with enough complexity to let you do arithmetic. You need a system with enough complexity to also do self-reference. And I would say and think that self-reference is complicated. Do we need self-reference in any other areas of mathematics, than Godel's and related proofs?

throwaway81523 5y ago

> I suspect someone could write a book (or an HN comment at least) about the popular confusion about Godel's 1st incompleteness theorem. :-) That book has already been written: https://www.ams.org/notices/200703/rev-raatikainen.pdf https://www.ams.org/notices/200703/rev-raatikainen.pdf

eynsham 5y ago

> reveal limitations of certain models of computers Modulo weird stuff with black holes or whatever (not that I am qualified to understand whether they count), there are no known counterexamples to the Church-Turing thesis.

hvidgaard 5y ago

yayachiken 5y ago

Your comment made me break down and finally make an HN account. I think I may have the perfect answer for you. Your comments remind me so much of myself, when I was in 7th grade and we just learned that 0.999... would exactly equal 1. Not almost, but exactly. I know that I asked my math teacher tricky questions, and left really unsatisfied, because "obviously it's not true", probably my teacher does not understand infinity. I kind of forgot about it, and it only really clicked a couple years later once I learned about series and limits, because I finally gained an intuition for working with infinity. A very important notion about infinity that the terms "For any arbitrary large N" and "For Infinity" are not the same thing. I actually think that the cause of the confusion is similar. Maybe your mental model of computation includes an "arbitrarily large N" where you actually need an "infinitely large N". Note that the halting problem (and a whole bunch of other interesting undecidable problems) is actually "semi-decidable". This means we are guaranteed to get an answer to the question, but only if the answer is actually "yes". (Before you ask: Taking the inverse of a problem does not preserve semi-decidability, so no trickiness here.) We need some intermediate results here. I am not going to prove them for brevity (and because I will probably be unable to produce them right now), so you'll have to trust me for them. Sorry! A Turing machine P which gets input i produces output P(i). We can construct a machine P_i which ignores its input, but instead always produces P(i) for any i. We can also construct for any P an encoding Enc(P) (the "source code" so to say, actually a Gödel numbering) which encodes the turing machine. We can also show that there is a universal turing machine U which for any Enc(P) will produce the same outputs as P for all possible inputs i. We can also construct a special limited universal turing machine U_j which halts after at most j steps. So how does semi-decidability work in practice: Let us simulate a turing machine P on U_1. If it halts, we return 1, if it does not halt after 1 step, we return 0. This turing machine will solve the halting problem for all turing machines that halt after 1 step. We can then look at U_2, U_3 and so on, and those machines will always solve the halting problem for a strict superset of the others. So we know that the number of turing machines which do not have a solution by our ever increasing set of halting problem deciders will get smaller and smaller. The halting problem now says: Even if all machines of {U_j : j is natural number} run in parallel, we will always have Turing machines P for which we will not get an answer. The halting problem also tells us that there will never be a U_infinity, which would then give us the answer. If you don't like the self-referential proof, you can check out the diagonalization proof, which is more rigorous. Now you have given examples of for example humans adapting to additional input. We know for a fact that humans in their lifetime can only perform a finite number of computational operations, and parse a finite number of input arguments. If I was a physicist I could probably cite some theorem of thermodynamics to give you an upper bound on that number, which is probably astronomically huge but finite. The same applies for the computing power of the universe. Huge, but finite. This is all the halting problem says: We can solve a lot of problems by brute force, but never all of them. We can also solve all problems approximately by just giving an arbitrary (but fixed) answer after we get bored with our long-running turing machine. The halting problem is important because for all we know and care, and infinite computer cannot physically exist, as the universe itself is finite. For example, the halting problem can be solved by a theoretical computer which speeds up by factor 2 on every step. And probably also something like a machine which has an exact encoding for every real number, which cannot exist in the universe as we currently understand it, for similar reasons. https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation It's not that we cannot think of those models, it is just that they are completely useless and uninteresting as they get too powerful, but also impossible to build. You could approximate them, but the approximation is useless, as the approximation will again be a convoluted turing machine.