Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Infinities, impossibilities, and the man in the white linen suit

iain.so

Post reply on HN
Print view View original

41–50 of 65 posts

Re: Infinities, impossibilities, and the man in the white linen suit

#41

Post by tsimionescu »

cyberax wrote: post #39
hardbass wrote: post #38

Earlier quoted context omitted.

As of yet we have no such evidence of physical systems that are more powerful than Turing machines. We will consider if ever such evidence arises.

Turing machines can't operate on arbitrary real-numbered values because they require infinite precision. If the universe indeed uses real values, it's possible that it's more powerful than Turing machines.

The problem with arbitrary real numbers is not precision, it is computability. Most real numbers we actually work with in the sciences are computable - pi, e, 2, 0.(2), and so on - they are all computable by Turing Machines. However, Turing himself showed that not all real numbers are - you can construct real numbers like Chaitin's constant that are not actually computable by a TM. In fact, almost all real numbers are non-computable (the set of computable numbers is countable, so it has the same "size" as the Naturals, while the Reals are not countable - so they are much larger).

However, this doesn't mean that TMs can't operate on such numbers. You can compute the fact that pi + pi = 2 * pi even if you can't enumerate all of pi's decimals.

Re: Infinities, impossibilities, and the man in the white linen suit

#42

Post by Animats »

c2c2c wrote: post #11
skippyfish wrote: post #5

Aside from seemingly being 100% AI-generated, this article makes a really spurious use of Godel's argument, which I think is best exemplified by the following passage near the end: "These four threads share a common ancestor in what Gödel proved in 1931, and Turing sharpened in 1936. Rule-based systems cannot fully account for themselves. A system cannot certify its own trustworthiness. A learning framework cannot de…

I think this is selling Gödel a little bit short. He proved for the first time that in any system of mathematics with enough complexity to be interesting, there are statements that cannot be proven true or false. The Gödel sentence might seem like a trivial example, but other examples of such things have been discovered since, such as the continuum hypothesis which the article mentions.

> enough complexity to be interesting

That's the loophole. There is mathematics without infinity.[1] Until recently, it was considered somewhat fringe. But there's been enough development that it's now clear you can do mathematics without infinity. In that view, infinities are a labor-saving device to get rid of special cases. They're not essential. Mathematicians used to hate special cases, but now that the active ones all grew up with computers, they're not so scared of IF statements.

You can have "arbitrarily large" but not "infinite". Boyer-Moore theory is like that. It starts out like Peano arithmetic. There is (ZERO) and (ADD1 (ZERO)) and (EQUALP A B) and (LESSP A B) as predicates. That's the axiomatic basis. Numbers are (ADD1 (ADD1 (ADD1 (ZERO)))), etc.

You can have recursive functions, but they must terminate. They must have a value which, for each recursion, is LESSP than the previous iteration. That's how you prove termination.

You can do most of mathematics that way. But not infinitesimals. You never can get to

    1 + 1/2 + 1/4 + 1/8 ... = 2
in that kind of constructive mathematics. That requires an infinite recursion, which is not allowed.

[1] https://engtechnica.com/rethinking-mathematics-without-infin...

Re: Infinities, impossibilities, and the man in the white linen suit

#43

Post by mwkaufma »

cubefox wrote: post #17

> The greatest logician since Aristotle Not to diminish Gödel's work, but the greatest logician since Aristotle was clearly Gottlob Frege, the inventor of modern predicate logic.

One might gently recommend reading the "Political and social views" section on Frege's wikipedia entry before hitching your hot-take wagon to that particular horse.

Re: Infinities, impossibilities, and the man in the white linen suit

#44

Post by Diogenesian »

hardbass wrote: post #21
skippyfish wrote: post #5

Aside from seemingly being 100% AI-generated, this article makes a really spurious use of Godel's argument, which I think is best exemplified by the following passage near the end: "These four threads share a common ancestor in what Gödel proved in 1931, and Turing sharpened in 1936. Rule-based systems cannot fully account for themselves. A system cannot certify its own trustworthiness. A learning framework cannot de…

The worse confusion they seem to have is they think mathematical theorems are only applicable to "computers". Mathematical theorems have no escape, they apply just as much to human brains as to computers. If these theorems were a blocker for developing general intelligence then how do humans exist.

Gödel believed the human brain used non-mathematical reasoning (i.e. inexpressible with a Turing machine) to derive the axioms and thus could "see outside" of any particular axiom schema.

The Church-Turing thesis throws cold water on this: since the human body (including brain) is describable by a finite system of Schrödinger equations, and these equations can be solved numerically by a Turing machine, the human process of creating an axiom scheme should be Turing-computable. But some recent results on very large finite numbers (busy beaver) suggest there may be a subtlety here, e.g. complexity blows up to the point that it takes far more energy than the sun to simulate one human.

The more interesting subtlety: for a physically meaningful result you would need to define configuration space very carefully, e.g. not screwing up the boundary consitions or causal order of subsystems. Perhaps defining this is actually not computable, and after every delta(t) in a computer simulation, a human has to check the physics and redefine certain parameters of the system. Solving the Schrodinger equation numerically is certainly Turing-computable, but the process of ensuring that solution is physically meaningful isn't even slightly formalized. It may be unformalizable.

Re: Infinities, impossibilities, and the man in the white linen suit

#45

Post by cyberax »

tsimionescu wrote: post #41
cyberax wrote: post #39

Earlier quoted context omitted.

Turing machines can't operate on arbitrary real-numbered values because they require infinite precision. If the universe indeed uses real values, it's possible that it's more powerful than Turing machines.

The problem with arbitrary real numbers is not precision, it is computability. Most real numbers we actually work with in the sciences are computable - pi, e, 2, 0.(2), and so on - they are all computable by Turing Machines. However, Turing himself showed that not all real numbers are - you can construct real numbers like Chaitin's constant that are not actually computable by a TM. In fact, almost all real numbers ar…

That's why I added the word "arbitrary" :)

> However, this doesn't mean that TMs can't operate on such numbers.

Well, it kinda does. For example, you can't compute the sum of two arbitrary real values in a finite number of steps.

That being said, it's possible that the universe actually is not "running" on real numbers. This would also mean that our physics built on top of calculus is just an approximation.

This has always fascinated me. You can't really construct a meaningful amount of calculus without having real-valued variables. The intermediate value theorem depends on it, and it's one of the foundational parts.

I tried to construct something like "bounded error rational calculus", by trying to use rational ranges instead of real values and then constraining the range size. I was able to recover _some_ calculus, but I really have not studied it in enough details.

Re: Infinities, impossibilities, and the man in the white linen suit

#46

Post by nabbed »

cubefox wrote: post #18

Is it just me or does this article have a lot of LLM-isms?

I didn't pick up on it. I see this often: comments on HN remarking that something is AI generated, yet it's not obvious to me. Makes me worry that I am an LLM myself[1].

I've seen lot of bizarre, hard to understand or weirdly formulaic writing pre-2023, so I guess that's why I don't assume anything is AI generated.

[1] BTW, I am not.

Re: Infinities, impossibilities, and the man in the white linen suit

#47

Post by silver_sun »

moi2388 wrote: post #26
hardbass wrote: post #20

Earlier quoted context omitted.

I don't understand the point at all. Mathematical theorems like godel's incompleteness theorem or the halting problem are applicable to everything including the human brain. If they were a limitation to developing general intelligence then human beings wouldn't have existed.

Are they? Are there any actual Turing machines? Doesn’t that require infinite memory? I don’t know of a single thing which actually has that, nor one that comes close.

Not infinite memory, a Turing machine only requires "unbounded" memory, which is a way of saying that it will not run out of memory while running its program with the given input. In other words it just needs to have enough memory to run the program with whatever inputs it was given, which is much less than infinity. And this situation is quite common in the real world -- the programs I use on a daily basis have all the memory / RAM they need to do what I want (almost by definition). So in practice I might as well view them as Turing machines.

Re: Infinities, impossibilities, and the man in the white linen suit

#48

Post by stavros »

mwkaufma wrote: post #43
cubefox wrote: post #17

> The greatest logician since Aristotle Not to diminish Gödel's work, but the greatest logician since Aristotle was clearly Gottlob Frege, the inventor of modern predicate logic.

One might gently recommend reading the "Political and social views" section on Frege's wikipedia entry before hitching your hot-take wagon to that particular horse.

Why does him being a raging racist preclude him from being the greatest logician?

Re: Infinities, impossibilities, and the man in the white linen suit

#49

Post by tsimionescu »

cyberax wrote: post #45
tsimionescu wrote: post #41

Earlier quoted context omitted.

The problem with arbitrary real numbers is not precision, it is computability. Most real numbers we actually work with in the sciences are computable - pi, e, 2, 0.(2), and so on - they are all computable by Turing Machines. However, Turing himself showed that not all real numbers are - you can construct real numbers like Chaitin's constant that are not actually computable by a TM. In fact, almost all real numbers ar…

That's why I added the word "arbitrary" :) > However, this doesn't mean that TMs can't operate on such numbers. Well, it kinda does. For example, you can't compute the sum of two arbitrary real values in a finite number of steps. That being said, it's possible that the universe actually is not "running" on real numbers. This would also mean that our physics built on top of calculus is just an approximation. This has…

I find this topic of precision and of the computation that happens in the universe to be pretty interesting, but also very hard to pin down.

For example, let's take two arbitrary real numbers, call them x and y. They're almost certainly irrational uncomputable numbers, of course. Now, what is their sum? It's x + y, of course - I can tell you that without doing an infinity of computational work. Now, is this a useful representation? It very much depends on the use you have for it. For two unrelated uncomputable numbers, their sum is almost certainly uncomputable anyway, so there's not going to be any meaningful representation of it either. However, we can still derive useful properties about it, and use it in physical simulations as we need. For example, if both x and y are positive, I can tell you that x+y is greater than either of them, so I can also tell you that the electromagnetic force between two particles that are at distance x+y will be weaker than the force between two particles at distances of just x or just y.

So, what would it mean for the universe to "compute the exact value" of these two, or of their sum? What can physics do, assuming that some aspects are indeed continuous, that a simulation running on a TM actually can't?

Re: Infinities, impossibilities, and the man in the white linen suit

#50

Post by silver_sun »

Swizec wrote: post #15
azakai wrote: post #9

The overall point feels strained to me. Yes, formal mathematics has such limits. We can't expect machines to be perfect and provably perfect. But the industry isn't assuming that. Why would it? Natural intelligence is not perfect or provably perfect, either. Rather than certainty, measurement is often enough. We can't prove a program will always halt, but we can check it halts in a specific execution. Approximation i…

> We can't prove a program will always halt, but we can check it halts in a specific execution. The computer scientist says “The halting problem cannot be solved, I have proven it” and the software engineer goes “30 second timeout, if the answer’s not ready by then we don’t need it”

I think this comparison is interesting because it shows the difference between theory & practice, but it's a little inaccurate. The halting problem being undecidable just implies there is no single universal algorithm that can tell you whether any program at all will halt. In practice we are working in specific domains and can come up with heuristics which are "good enough" for a specific codebase / module, like the timeouts you mention. So the halting problem can be solved for some subsets of programs but not all of them, and the computer scientist would hopefully have realized this instead of treating the codebase generically as "any program".
Post reply on HN