I really like this explanation! It's definitely helpful to see this sort of abstract math idea brought down to super concrete terms. Although I did have a bit of confusion around the "./behave_differently.sh ./my_program.sh ./my_input.txt" part - I expected another layer of concreteness so I was looking for actual outputs (which I realize isn't the point - my_program.sh is supposed to be anything/everything).
Other than that though this is a great piece! Short, decently written, and with a good focus but a lot of hints at further things to explore.
I guess I'm also not sure about the conclusion - feels a bit like the author's pet issue on how we should teach things, and I feel like that sort of discussion is separate from the article's main focus. I'm more a fan of "here's A different pov on this topic" than "here's THE pov we should teach for this topic"
> When Turing proved the halting problem was undecidable - that there is no program that can decide whether another program will ever finish
Turing didn't prove the halting problem was undecidable. The halting problem was defined after Turing's death by Martin Davis. It's a common misunderstanding people have. Turing's definition of Turing Machines classified machines that halted as circular/unsatisfactory. Turing wanted his machine to run forever ( circle-free/satisfactory ).
> Personally, I think we should set aside Gödel’s original number-theory-based proof as an artifact of history, the way we no longer use Isaac Newton’s original notation for calculus.
We also don't teach Turing's version either. No computer science class teaches real Turing. It's been reformulated to a point Turing would barely recognize it. Also, you can't understand the halting problem or Turing without "number-theory-based proof" as "number based proof" and godel numbering is at the heart of turing machines ( look up what descriptive numbers ) are.
> We should accept that the concepts of mathematical proof and computer algorithms are intertwined at their heart
Computer algorithms are mathematical algorithms. Mathematicians have been using computers/algorithms to derive theorems from axioms since at least the 1950s. You are saying we should accept what everyone already accepts and have accepted for decades.
> We also don't teach Turing's version either. No computer science class teaches real Turing. It's been reformulated to a point Turing would barely recognize it.
I think that this is true of most long-lived subjects taught in a modern science course. Imagine Euclid's puzzlement at all the things that are now called Euclidean!
> Also, you can't understand the halting problem or Turing without "number-theory-based proof" as "number based proof" and godel numbering is at the heart of turing machines ( look up what descriptive numbers ) are.
Since you say most of what one learns in a CS course isn't directly about Turing's original work, I don't want to speak to that, but I think that it is possible to understand the halting problem, and even its undecidability, without number theory. It arguably isn't possible to understand the halting problem without some notion of encoding (of the data that constitute a Turing machine in a form that can itself be processed by a Turing machine), but there's no reason that encoding has to be number-theoretic. (I speak here as a number theorist—it's a neat application, just much more important for incompleteness than for halting.)
> It arguably isn't possible to understand the halting problem without some notion of encoding (of the data that constitute a Turing machine in a form that can itself be processed by a Turing machine)
You can understand the halting problem without math. You can explain it logically. But the halting problem has nothing to do with Turing. As I stated, the halting problem was invented/discovered by someone else years after Turing's death. We don't need Turing or the Turing machine to understand undecidability since Alonzo Church already proved undecidability before Turing.
> but there's no reason that encoding has to be number-theoretic
Sure. Turing encoded to the standard description ( letters ) and to description numbers. But number theory is necessary if you want to follow Turing's approach since you need to show for starters that turing machines and computable numbers are enumerable.
The Wikipedia article is sound and it also documents that Martin Davis came up with the term "halting problem" for a lecture he gave in 1952. He used Turing machines in his 1958 book. Turing machines are still a commonly used formalism in some areas of theoretical computer science.
>His proof is fairly difficult to understand - it involves prime numbers, factorization, all this number theory.
Actually, the textbook proof itself is not very different from the presentation in this article, so not hard at all.
The difficult part is in formalizing that you can write "a program that proves a program halts".
To do so you have to encode it into the language of mathematics, and that is the painful part.
To be clear: you have the paradox of the set that contains all sets that don't contain themselves.
In naïve set theory, it is trivial to write down formally.
However the Berry paradox is not a real paradox because there is no way to encode "The smallest positive integer not definable in under sixty letters".
So the whole point of going through the encoding is to show that yes, we can encode what a provable statement, and thus the first 'paradox' is actually a crucial flaw in the mathematical theory, whereas the second is a flaw/paradox in human language, but does not mean anything.
The computer world is not as strict, it's more squishy (human?) than mathematics.
>>His proof is fairly difficult to understand - it involves prime numbers, factorization, all this number theory.
>Actually, the textbook proof itself is not very different from the presentation in this article, so not hard at all. The difficult part is in formalizing that you can write "a program that proves a program halts". To do so you have to encode it into the language of mathematics, and that is the painful part.
I think the difficulty of understanding Gödel's proof has changed with the rise of computers. For him the difficult part of the proof was showing that you can represent text as numbers and manipulate it using arithmetic operations. These days we all do that for our day jobs. So you can skip over the part that Gödel thought was difficult in one line, and focus your attention on the clever use of self-reference.
Also these days we would probably use a binary encoding instead of Gödel's encoding via prime factorisation, so even if you did want to explain the details of the encoding the amount of number theory would be reduced.
Gödel's method starting with encoding parentheses, and bound variables, i.e. purely syntactical artifacts.
It's a good example where you could do away with this, using e.g. de Bruijn indices -- exactly as you'd suggest switching encoding to binary.
It is another layer of (mostly incidental) complexity yet in the end this complexity has to be addressed -- one choice of base does not change the number.
When you write programs, you don't prove them correct, and you go down to assembly instructions, which is essentially what Gödel did.
For him the difficult part of the proof was showing that you can represent text as numbers and manipulate it using arithmetic operations. These days we all do that for our day jobs.
Typically either with length prefixing (what binary protocols do) or with escaping/quoting (what text protocols do). For example, JSON assigns a unique bit sequence to every possible list of strings by using '"' and ',' as separators and '\' as an escape signal to disable the special meaning of the next character.
> However the Berry paradox is not a real paradox because there is no way to encode "The smallest positive integer not definable in under sixty letters".
Why is a “way to encode” necessary for a paradox to be “real”?
> So the whole point of going through the encoding is to show that yes, we can encode what a provable statement, and thus the first 'paradox' is actually a crucial flaw in the mathematical theory, whereas the second is a flaw/paradox in human language, but does not mean anything.
How can you say something “does not mean anything” simply because it cannot be formalised? Since when is formalisability a prerequisite for meaningfulness?
The basic constraint is that if you want to prove something based on purely logical statements, you need to express the problem precisely enough for pure logic, that is without any wiggle room open to vauge human interpretation, and the notions you use have precise meaning. If not, your problem can't be solved by pure logic, but only by more wishy washy handwavy arguments, from which you can't derive any insights with logical certainty.
You might be able to derive philosophical or empirical meaning from an interpretation of some non-precise statement, but you shouldn't hope that such an interpretation is a valid mathematical theorem.
> The basic constraint is that if you want to prove something based on purely logical statements, you need to express the problem precisely enough for pure logic, that is without any wiggle room open to vauge human interpretation, and the notions you use have precise meaning. If not, your problem can't be solved by pure logic, but only by more wishy washy handwavy arguments, from which you can't derive any insights with logical certainty.
I think when you say "pure", you actually mean "formal" or "symbolic" or "mathematical". Many believe that there is much more to logic than a mere formalism – although that itself is a major point of contention in the philosophy of logic.
> You might be able to derive philosophical or empirical meaning from an interpretation of some non-precise statement, but you shouldn't hope that such an interpretation is a valid mathematical theorem.
Berry's paradox may not be a mathematical paradox – but that doesn't show it is not a paradox. And, even if it is not a mathematical paradox, it nonetheless made a valuable contribution to mathematics, by inspiring the construction of formal analogues, some of which turned out not to be paradoxical (but nonetheless interesting). However, I don't think it necessarily follows, that just because those formal analogues turned out not to be actual paradoxes, that its natural language version cannot be a real paradox. And, some argue there are formal analogues which are genuine paradoxes – see for example https://ojs.victoria.ac.nz/ajl/article/download/4972/4634/73...
> some argue there are formal analogues which are genuine paradoxes...
Isn't this getting a bit circular, as it seems to be using the presumed existence of a formal analogue to justify the informal Berry's paradox? If it has a paradoxical formal analogue, then it does not stand as an example of a useful yet unavoidably informal paradox.
Also, given that there seem to be more than one plausible formal analogue, not all of which are paradoxes, does the dispute not just re-form around which is the real formal analogue? That's what seems to be happening in the exchange of papers from which your example was taken.
>How can you say something “does not mean anything” simply because it cannot be formalised? Since when is formalisability a prerequisite for meaningfulness?
I'm wondering then, what you think is the interest of this theorem?
The goal of Gödel was to create a metamathematics. You need to know what is a paradox of the theory or a paradox or not to know if it is correct.
If you have a contradiction, you cannot believe anything that the theory proves.
So the whole thing is ultimately about separating mathematical paradox from "other types" of paradoxes.
> I'm wondering then, what you think is the interest of this theorem?
Well, it was a profound discovery about the limits of consistent formal systems, and of course it is interesting in that light. But, viewing that as profoundly interesting does not require one to adopt your apparent position that only the formalisable is "real".
> If you have a contradiction, you cannot believe anything that the theory proves.
Only with classical logic. With paraconsistent logic, you can believe things proven from inconsistent axioms. Classical logic includes the principle of explosion (ex contradictione quodlibet, from a contradiction anything follows); so inconsistent theories immediately collapse into trivial ones, and trivial theories are of course utterly useless. But since paraconsistent logic rejects the principle of explosion, inconsistent theories do not collapse into triviality, and thus may be useful in spite of their inconsistency.
Classical logic is a poor model of natural language and informal human reasoning. Paraconsistent logics are much more accurate formal models of informal human reasoning and natural language, and much closer to them in power.
One argument for this: material implication is a poor model of how implication works in natural language, as the well-known paradoxes of material implication show. With modal logic, we can introduce strict implication, which performs better, but still falls short as an accurate model of natural language implication, as shown by the paradoxes of strict implication. Relevant logics (aka relevance logics) avoid the paradoxes of strict implication as well. But relevant logics are also paraconsistent.
Using an appropriate paraconsistent logic, Berry's paradox can be turned into a formal paradox, and such a formal paradox can be viewed as a straight-forward formalisation of the informal Berry's paradox.
Attempts to formalise Berry's paradox using classical logic fail to produce a paradox, because classical logic lacks sufficient self-referential power – classical logic cannot cope with inconsistency, so classical formal systems must have their powers of self-reference neutered – compared to natural language – to prevent self-referential paradoxes – and those restrictions also prevent a formal Berry's paradox from existing. Paraconsistent logic is far better at handling inconsistency, so it does not have to restrict self-reference, and becomes much closer to natural language in power – and Berry's paradox becomes a formal paradox as well as an informal one.
So, given the above – in what sense is Berry's paradox not "real"?
There is a fallacy in constructing "paradox.sh" problem.
"behave_differently.sh" requires an argument, a program to be run and produce some output.
If "behave_differently.sh" is run without any argument, then there is no specified correct behavior.
Thus, "paradox.sh" also requires "$1" to be non-empty, otherwise it's result is undefined.
When invoking "./paradox.sh ./paradox.sh", the inner "paradox.sh" will be launched without any arguments, running "behave_differently.sh" also without arguments.
There is no logical impossibility, just constructed way to trigger unspecified behavior in "behave_differently.sh".
Note that behave_differently.sh takes two inputs, both a program and the input for that program. Also note that paradox.sh gives both these inputs by using $1 twice.
And behave_differently.sh is supposed to be an arbitrary program. It can run the input program but it doesn't have to, it can analyse it in any way it wishes.
It is a good point that behave_differently.sh does not necessary run its argument program, but can analyze it in another way. (The context of Bash scripts suggests execution but that is a misleading hint.)
In the broader formulation behave_differently.sh tells that its argument program terminates and produces finite input, which is a halting problem.
Unfortunately while valid logical formulas have finite deductions, proving that a formula is not valid (or equivalently that some formula is satisfiable) is Turing complete and thus impossible. So the set of valid first order formulae is recursively enumerable.
However, if you limit your scope to finite sets bounded by some size, the problem is merely NP-complete. Given a program, you can construct a formula which is satisfiable iff the program halts (with said formula being polynomial in size with respect to the size of the program).
It's more or less the same argument. They key additional ingredient in Godel's proof (besides some slight technicality on soundness vs. omega-consistency) is the encoding of an arithmetic interpreter inside of arithmetic itself. That a bash script can run and capture the output of another bash script is pretty obvious, but the first order logic analogue is not nearly as neat and easy.
The argument given here is a modern translation of Turing's work in his original paper introducing Turing Machines and the Halting problem, in which he devotes an entire section to the connection between his proof and that of Godel.
They are definitely distinct. The key insight of Godel's incompleteness theorem is that there is a statement that can't be proved as true but is indeed true and can be perceived as true by an observer outside of the mechanical-logical realm inside of which that statement lives.
It says there are something non-mechanical about intelligence.
Apparently people think it is just a paradox or some other boring idea.
> It says there are something non-mechanical about intelligence.
I don't think Gödel drew that conclusion; that's Roger Penrose's reasoning. He uses Gödel's Theorem as an example of correct reasoning that can't be algorithmic (i.e. Gödel's mind cannot be replaced by an algorithm). It's not a proof, and it's controversial. I find it convincing; but then I'm biased - I'm predisposed to the view that the mind is not algorithmic.
Yes, I just used this opportunity to raise this point. I don't know what Gödel himself thought of it.
But I find it very disheartening when such an interesting find is presented as simply "a paradox" akin to the phrase "this is a lie". That would be the most uninteresting thing ever.
Many articles on the internet thus describe Gödel's theorem, and also that famous book from Douglas Hofstadter.
It's showing that the halting problem is unsolvable, using an infinite recursive loop as an example. The halting problem is related to the incompleteness theorem.
I wonder if it could be solvable by an algorithm that was capable of operating at a higher level.
Mayhaps the issue is approaching the problem at the same dimensional level that the problem originated from. After all, humans can come at the problem from a higher cognitive level and, given enough time, resolve that an infinite loop is taking place, so the problem is not fundamentally unsolvable.
Einstein said, "No Problem Can Be Solved From The Same Level Of Consciousness That Created It", so it is feasible to assume that, say, a quantum computer running every possible iteration of an algorithm could easily identify which iterations of the algorithm's parameters would induce infinite loops by simple attrition.
Yes, definitely. But then the next task is just to solve the incompleteness problem on the level of the higher algorithm, because there must always be incompleteness.
Hofstaedter discusses this at length in his book Gödel, Escher, Bach if you are interested in this topic.
i found this explanation to be easier to grasp `truth alone does not exist or is not valuable without the steps to deduction to that truth (contrary to what mathematician traditionally believed`.
This is a mischaracterisation of gödels incompleteness theorem.
The set of axioms the theorem is about isn't even mentioned in the article. This is very important. If you pick the empty set as your axioms, most statements will be independent of them.
The important insight is different. One can simulate a computer in the peano axioms.
If you could prove or disprove (starting from a computable set of axioms) every statement about simulated computers you could also solve the halting problem.
Kleenes (the kleene star guy) proof goes that way.
Not always. ;)
Specifically, if my_program.sh outputs some 1024 lines then it is still nonzero probability that your behave_differently.sh does not in fact behave differently.
but the intended requirement of behave_differently is that it produces
different output when run on a computer in exactly the same state. Or equivalently, that the program doesn't depend on the computer state, which is true in the more formal setting of universal Turing machines that start from a fixed state.
This does not solve the issue. behave_different.sh has to behave different *all* the time *on every input*. Not just 99.999999% of the time.
Imagine my_program.sh says:
echo "2022-02-26 10:30:00" and you run your version of behave_differently.sh at 10:29:59 on the 26/2. Then the output is the same.
If you want something that always behaves differently, why not just concatenating something to whatever the output of the other script would be? I'm familiar with the halting problem, but considering the quick description inside this post I don't see which part of it would forbid this
No, there's a 0% chance my implementation outputs 1 as that is only 1 byte long. If you outputted 1023 0s and then a 1 there would be a 2^-1024 chance. That probability is too small to practically happen. The heat death of the universe will happen first.
You're right that my example was flawed. I've updated it. There is however still nonzero probability that ./behave_differently.sh some_peogram.sh behaves the same as ./some_program.sh
Also remember that we are considering a bash interpreter which implies we at least have access to $RANDOM. The section behave_differently.sh comes from is only focusing on bash. It does not mention Turing machines.
The thing is, the two instances do not "behave" differently. They only output different values based on the same process. Behaviorally they are identical.
That book is where I first learned about Gödel's incompleteness theorem. Definitely a good book!
I spent a while when I first read it trying to understand Gödel numbering, all the stuff where you multiply prime numbers together, 11 stands for (, that sort of thing. It wasn't until far later that I realized all of that was just a mathematician in the 1930's trying to explain how a string of characters could be encoded as a binary number, something that modern computer programmers more or less take for granted.
Here is a hypothetical bash script that neatly characterizes the the impossibility of solving the halting problem: "loop_iff_halts_on_self.sh". What does
Maybe a company could decide that developing a tool that, given two programs as imput, tells if those two programs are equivalent would be a great tool to help teams migrate their code to a different programming language (or equivalently migrate to a new version of the same language, like it happened from Python 2.x to Python 3.x). But you can reduce this problem to the halting problem and show that this is not possible. More generally, the halting problem is a great tool to prove that other more practical things are unfortunately impossible to achieve, at least in the general case. But as another commenter pointed out, given a specific problem you could come up with heuristics that work most of the times (but sometimes would not be able to give a conclusive answer)
Only preventative measures! One would know enough, for example, not to try to construct a static analysis tool to helpfully tell the user if their code will inadvertently loop infinitely. Imagine running the tool on itself.
But this is bash, which runs on Unixy systems, which have exec. behave_differently is trivial:
echo foo
exec “$@“
This little hack will carry over to some, but possibly not all [0], models of computation. Fixing this would involve cleaning up some definitions in the proof.
[0] Specifically, it does carry over to any model of a program that outputs a stream of symbols one at a time. A single-tape Turing machine that computes a function doesn’t work like that.
Other than that though this is a great piece! Short, decently written, and with a good focus but a lot of hints at further things to explore.
I guess I'm also not sure about the conclusion - feels a bit like the author's pet issue on how we should teach things, and I feel like that sort of discussion is separate from the article's main focus. I'm more a fan of "here's A different pov on this topic" than "here's THE pov we should teach for this topic"