9 ms·

The Infinity Machine

69 points by Smaug123 2y ago

Demonoculus 2y ago
While I am not an expert, but won't it run into Xeno's like paradox? But makes for interesting reading.
- teraflop 2y ago
  What do you mean by "run into"? Zeno's paradoxes are thought experiments. The original paradox of Achilles and the tortoise purported to show that Achilles would never be able to overtake the tortoise. But of course, in a real race Achilles would encounter no difficulty whatsoever in doing that. The Infinity Machine almost certainly isn't physically possible, but that's because of the laws of physics, not because of Zeno.
- astrodust 2y ago
  Unless there's an infinite number of programs of finite size, which sounds impossible, then no.
Schiphol 2y ago
There's work on so-called "hypercomputation" that might relevant to the author's project: https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation
- ryankrage77 2y ago
  Also see Supertasks, https://en.wikipedia.org/wiki/Supertask https://en.wikipedia.org/wiki/Supertask
  - its_ethan 2y ago
    VSauce is a little silly, but genuinely does have great content packed in his videos, and he has one on Supertasks: https://youtu.be/ffUnNaQTfZE https://youtu.be/ffUnNaQTfZE
- jackofspades 2y ago
  This just came up on a separate recent HN thread... the fictional hypercomputer: "I Don't Know, Timmy, Being God Is a Big Responsibility" by qntm: https://qntm.org/responsibility https://qntm.org/responsibility
tlocke 2y ago
I know the light switch idea as Thomson's lamp: https://en.m.wikipedia.org/wiki/Thomson%27s_lamp https://en.m.wikipedia.org/wiki/Thomson%27s_lamp I used it as an interview question many years ago. I wasn't very rigorous about it, basically any plausible answer was good enough for me. Answers fell into two categories, the theorists (it's an infinite series that doesn't converge) and the pragmatists (you couldn't physically do it).
- taneq 2y ago
  As anyone who's played light switch disco will know, the light bulb will blow long before you reach the theoretical limit of the series. :D (Actually thinking about it, that's probably not true because the switching accelerates so fast... the limiting factor is probably actually friction from moving the switch, and/or the tensile strength of the switch housing. I wonder if it would just disintegrate or if it would build up enough heat to properly explode...?)
  - mitthrowaway2 2y ago
    I think the limiting factor will be the inductance of the wire and lightbulb filament, which sustains a current even when the switch attempts to break the circuit!
    - pixl97 2y ago
      You'll have to get a planck switch and a single electron bulb... problem is it may or may not exist at any given moment, especially where you want it.
    - taneq 2y ago
      Ooh good point! Whatever kind of light bulb it is, it will (through inductance, thermal mass or fluorescence) continue to glow (which I’m counting as being “on”) for at least 1/60th of a second after losing AC power. So I’d say it will be glowing quite a lot at the 2 minute mark even if the switch components are forming their own singularity right nearby.
- 2y ago
mistermann 2y ago
With the plunging cost/capability of AI compute, variations of this are becoming more plausible every day. Who will be the first mover?
- its_ethan 2y ago
  Even with plunging cost and increasing capability... this is talking about infinite compute, it's essentially impossible to achieve by definition. You could dedicate the worlds entire compute to the Goldbach's conjecture function he wrote up - it (would/might) never complete. You could 1000000x the worlds compute and it (would/might) never complete. It's not even a problem of compute speed, it's a problem with infinity.
  - mistermann 2y ago
    Agreed, but there is plenty of utility that can be harvested, if we can direct our attention adequately. Also: humans have the ability to arbitrarily redefine words, and believe those redefinitions! There is a surprising amount of leeway in this simulation.
    - ben_w 2y ago
      > Agreed, but there is plenty of utility that can be harvested, if we can direct our attention adequately. Only for problems no worse than O(n^m) where m is not much more than 1. Greenend (the domain name in the link) is, or so goes local legend, named after an actual street in Cambridge, quite close to where I was working a decade ago; one particular job, we'd just changed a file format for a mobile app, and the upgrade process was taking 20 minutes on test devices. The other engineer insisted it couldn't possibly be improved despite the two observations (1) it was fine before the upgrade, and (2) it was fine once the upgrade was complete. After a bit of digging, I found an O(n^2) operation we didn't need, and turned 20 minutes into 200 ms. Increase the available compute by a factor of 1024 in an O(n^2) task, only compensates for n growing by a factor of 32.
      - mistermann 2y ago
VikingCoder 2y ago
I'm once again reminded of the book Permutation City...
- nickcw 2y ago
  Yes, I was thinking this would make a good basis for a Greg Egan story too.
cvoss 2y ago
If such a machine existed in our universe, as it sped up its execution, its parts would approach the speed of light. To continue speeding up its execution, it necessarily must occupy a smaller and smaller volume, to keep the parts nearer and nearer to each other. Continue further, and you realize that the total information content of the machine can't be sustained at any amount without the thing collapsing itself into a black hole. So, even if the machine, in any sense, "finishes" the computation, the output will live inside a black hole and thus be physically unknowable to us. I find it so fascinating that fundamental properties about the laws of physics integrate so tightly with what is computable. The standard definition of compatibility involving Turing machines sounds kind of arbitrary, but those machines are representative a truly fundamental concept in our universe: that which is physically knowable, since you can build Turing machines out of the stuff in the universe. Almost. Turing machines have unbounded tape. But the universe does not contain an unbounded amount of information or space with which to work. Sufficiently large Turing computations, though theoretically finite, are not realizable in our universe. Should such computations be considered decidable or undecidable?
- sqeaky 2y ago
  I am not sure if such is decidable or not, but your conjecture is decidedly against the spirit of the post. :p
- waveBidder 2y ago
  You would probably enjoy Feynman's lectures on computation: https://www.goodreads.com/book/show/17274.Feynman_Lectures_On_Computation https://www.goodreads.com/book/show/17274.Feynman_Lectures_O...
- Quekid5 2y ago
  > Sufficiently large Turing computations, though theoretically finite, are not realizable in our universe. Should such computations be considered decidable or undecidable? In Practice, I think Undecidable is the only "correct" answer -- because our knowledge is still very incomplete. In Theory/Principle I think Decidable is the "correct" answer because there will very probably be limits that cannot be exceeded. ... but then, to reduce this to a simpler issue: The Halting Problem becomes trivial for any amount of finite state. It just takes a really, really long time (or a huge amount of space) to decide.
omoikane 2y ago
I thought it's interesting that the author went the way of add-more-via-subdivision. It feels very analog, kind of like how with old photos, the way you get more resolution is to just print them bigger (of course, what you actually get in reality is more grain). It's different from how we modeled things like Turing machines, where if we needed more memory, we would append more tape, as opposed to subdivide the existing tape further.
rahimnathwani 2y ago
Tangential: 1. Simon Tatham is the author of PuTTY 2. In the early days of the web, many people's personal sites were hosted on shared computers (e.g. my first was on my university's DEC Ultrix system). The URLs started with a reference to the user's home directory. This page is hosted on a machine that has a page to lists all the user's home pages: https://www.chiark.greenend.org.uk/users.html https://www.chiark.greenend.org.uk/users.html 3. The home page has this awesome spam detector: If you want not to be able to send mail here in future, please send mail to tabasco@chiark.greenend.org.uk.
- vermilingua 2y ago
  2a. The machine name (chiark) is a reference to The Player of Games, a fantastic book in the excellent Culture series by Iain M. Banks
  - ben_w 2y ago
    4. Domain created: 1985-07-24 It predates the web by about 4 years, the publication of the first HTML standard by about 6 years, and it just had its 39th birthday.
sqeaky 2y ago
Such a machine would be fun I would make a programming language where you couldn't write code, only detailed specifications and tests. In a VM Every possible permutation of bytes/opcodes/instructions/whatevers would be tests to produce the smallest and fastest (presuming the code is to run on other machines) possible binaries that pass your tests. Ideally this would produce a Pareto front of possible outputs and you could choose from among them. Another idea solving old problems the hard way. Since fermat's last theorom is countably infinitely problem and this computer is uncountably infinite in performance it should be able to knock it instantly by simply enumerating all integers and trying them.
sqeaky 2y ago
If we used such a machine to to enumerate Pi what would happen? Is it proven that Pi infinitely long? If so that would be a countable infinite because it is digits of precision, right? Could we write algorithms that search all the digits of pi for patterns? Or mayb messages on speculation of creators or others who might be able to tamper with it? Could other math things be searched? Have we proven there is no upper limit to prime numbers? I know the largest known mersenne prime fills a novel sized book with just one number, but when does a number get too big to be prime if ever?
- TwentyPosts 2y ago
  Yes, pi has an infinitely long decimal expansion, and there are infinitely many prime numbers. No deep messages have been found in either yet, and I am sure some people tried, so it stands to reason that no such messages exist. Mathematical objects can be complicated and difficult to understand and go on for infinitely long without having secret messages hidden in them.
  - sqeaky 2y ago
    Of course they can, and with an infinitely powerful machine it would be cheap to check.
gwern 2y ago
The MAC part sounds a bit like https://en.wikipedia.org/wiki/Chaffing_and_winnowing https://en.wikipedia.org/wiki/Chaffing_and_winnowing

69 points by Smaug123 2y ago

Demonoculus 2y ago

While I am not an expert, but won't it run into Xeno's like paradox? But makes for interesting reading.

teraflop 2y ago
What do you mean by "run into"? Zeno's paradoxes are thought experiments. The original paradox of Achilles and the tortoise purported to show that Achilles would never be able to overtake the tortoise. But of course, in a real race Achilles would encounter no difficulty whatsoever in doing that. The Infinity Machine almost certainly isn't physically possible, but that's because of the laws of physics, not because of Zeno.
astrodust 2y ago
Unless there's an infinite number of programs of finite size, which sounds impossible, then no.

Schiphol 2y ago

There's work on so-called "hypercomputation" that might relevant to the author's project: https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation

ryankrage77 2y ago
Also see Supertasks, https://en.wikipedia.org/wiki/Supertask https://en.wikipedia.org/wiki/Supertask
- its_ethan 2y ago
  VSauce is a little silly, but genuinely does have great content packed in his videos, and he has one on Supertasks: https://youtu.be/ffUnNaQTfZE https://youtu.be/ffUnNaQTfZE
jackofspades 2y ago
This just came up on a separate recent HN thread... the fictional hypercomputer: "I Don't Know, Timmy, Being God Is a Big Responsibility" by qntm: https://qntm.org/responsibility https://qntm.org/responsibility

tlocke 2y ago

I know the light switch idea as Thomson's lamp: https://en.m.wikipedia.org/wiki/Thomson%27s_lamp https://en.m.wikipedia.org/wiki/Thomson%27s_lamp I used it as an interview question many years ago. I wasn't very rigorous about it, basically any plausible answer was good enough for me. Answers fell into two categories, the theorists (it's an infinite series that doesn't converge) and the pragmatists (you couldn't physically do it).

taneq 2y ago
As anyone who's played light switch disco will know, the light bulb will blow long before you reach the theoretical limit of the series. :D (Actually thinking about it, that's probably not true because the switching accelerates so fast... the limiting factor is probably actually friction from moving the switch, and/or the tensile strength of the switch housing. I wonder if it would just disintegrate or if it would build up enough heat to properly explode...?)
- mitthrowaway2 2y ago
  I think the limiting factor will be the inductance of the wire and lightbulb filament, which sustains a current even when the switch attempts to break the circuit!
  - pixl97 2y ago
    You'll have to get a planck switch and a single electron bulb... problem is it may or may not exist at any given moment, especially where you want it.
  - taneq 2y ago
    Ooh good point! Whatever kind of light bulb it is, it will (through inductance, thermal mass or fluorescence) continue to glow (which I’m counting as being “on”) for at least 1/60th of a second after losing AC power. So I’d say it will be glowing quite a lot at the 2 minute mark even if the switch components are forming their own singularity right nearby.
2y ago

mistermann 2y ago

With the plunging cost/capability of AI compute, variations of this are becoming more plausible every day. Who will be the first mover?

its_ethan 2y ago
Even with plunging cost and increasing capability... this is talking about infinite compute, it's essentially impossible to achieve by definition. You could dedicate the worlds entire compute to the Goldbach's conjecture function he wrote up - it (would/might) never complete. You could 1000000x the worlds compute and it (would/might) never complete. It's not even a problem of compute speed, it's a problem with infinity.
- mistermann 2y ago
  Agreed, but there is plenty of utility that can be harvested, if we can direct our attention adequately. Also: humans have the ability to arbitrarily redefine words, and believe those redefinitions! There is a surprising amount of leeway in this simulation.
  - ben_w 2y ago
    > Agreed, but there is plenty of utility that can be harvested, if we can direct our attention adequately. Only for problems no worse than O(n^m) where m is not much more than 1. Greenend (the domain name in the link) is, or so goes local legend, named after an actual street in Cambridge, quite close to where I was working a decade ago; one particular job, we'd just changed a file format for a mobile app, and the upgrade process was taking 20 minutes on test devices. The other engineer insisted it couldn't possibly be improved despite the two observations (1) it was fine before the upgrade, and (2) it was fine once the upgrade was complete. After a bit of digging, I found an O(n^2) operation we didn't need, and turned 20 minutes into 200 ms. Increase the available compute by a factor of 1024 in an O(n^2) task, only compensates for n growing by a factor of 32.
    - mistermann 2y ago

VikingCoder 2y ago

I'm once again reminded of the book Permutation City...

nickcw 2y ago
Yes, I was thinking this would make a good basis for a Greg Egan story too.

cvoss 2y ago

If such a machine existed in our universe, as it sped up its execution, its parts would approach the speed of light. To continue speeding up its execution, it necessarily must occupy a smaller and smaller volume, to keep the parts nearer and nearer to each other. Continue further, and you realize that the total information content of the machine can't be sustained at any amount without the thing collapsing itself into a black hole. So, even if the machine, in any sense, "finishes" the computation, the output will live inside a black hole and thus be physically unknowable to us. I find it so fascinating that fundamental properties about the laws of physics integrate so tightly with what is computable. The standard definition of compatibility involving Turing machines sounds kind of arbitrary, but those machines are representative a truly fundamental concept in our universe: that which is physically knowable, since you can build Turing machines out of the stuff in the universe. Almost. Turing machines have unbounded tape. But the universe does not contain an unbounded amount of information or space with which to work. Sufficiently large Turing computations, though theoretically finite, are not realizable in our universe. Should such computations be considered decidable or undecidable?

sqeaky 2y ago
I am not sure if such is decidable or not, but your conjecture is decidedly against the spirit of the post. :p
waveBidder 2y ago
You would probably enjoy Feynman's lectures on computation: https://www.goodreads.com/book/show/17274.Feynman_Lectures_On_Computation https://www.goodreads.com/book/show/17274.Feynman_Lectures_O...
Quekid5 2y ago
> Sufficiently large Turing computations, though theoretically finite, are not realizable in our universe. Should such computations be considered decidable or undecidable? In Practice, I think Undecidable is the only "correct" answer -- because our knowledge is still very incomplete. In Theory/Principle I think Decidable is the "correct" answer because there will very probably be limits that cannot be exceeded. ... but then, to reduce this to a simpler issue: The Halting Problem becomes trivial for any amount of finite state. It just takes a really, really long time (or a huge amount of space) to decide.

omoikane 2y ago

I thought it's interesting that the author went the way of add-more-via-subdivision. It feels very analog, kind of like how with old photos, the way you get more resolution is to just print them bigger (of course, what you actually get in reality is more grain). It's different from how we modeled things like Turing machines, where if we needed more memory, we would append more tape, as opposed to subdivide the existing tape further.

rahimnathwani 2y ago

Tangential: 1. Simon Tatham is the author of PuTTY 2. In the early days of the web, many people's personal sites were hosted on shared computers (e.g. my first was on my university's DEC Ultrix system). The URLs started with a reference to the user's home directory. This page is hosted on a machine that has a page to lists all the user's home pages: https://www.chiark.greenend.org.uk/users.html https://www.chiark.greenend.org.uk/users.html 3. The home page has this awesome spam detector: If you want not to be able to send mail here in future, please send mail to tabasco@chiark.greenend.org.uk.

vermilingua 2y ago
2a. The machine name (chiark) is a reference to The Player of Games, a fantastic book in the excellent Culture series by Iain M. Banks
- ben_w 2y ago
  4. Domain created: 1985-07-24 It predates the web by about 4 years, the publication of the first HTML standard by about 6 years, and it just had its 39th birthday.

sqeaky 2y ago

Such a machine would be fun I would make a programming language where you couldn't write code, only detailed specifications and tests. In a VM Every possible permutation of bytes/opcodes/instructions/whatevers would be tests to produce the smallest and fastest (presuming the code is to run on other machines) possible binaries that pass your tests. Ideally this would produce a Pareto front of possible outputs and you could choose from among them. Another idea solving old problems the hard way. Since fermat's last theorom is countably infinitely problem and this computer is uncountably infinite in performance it should be able to knock it instantly by simply enumerating all integers and trying them.

sqeaky 2y ago

If we used such a machine to to enumerate Pi what would happen? Is it proven that Pi infinitely long? If so that would be a countable infinite because it is digits of precision, right? Could we write algorithms that search all the digits of pi for patterns? Or mayb messages on speculation of creators or others who might be able to tamper with it? Could other math things be searched? Have we proven there is no upper limit to prime numbers? I know the largest known mersenne prime fills a novel sized book with just one number, but when does a number get too big to be prime if ever?

TwentyPosts 2y ago
Yes, pi has an infinitely long decimal expansion, and there are infinitely many prime numbers. No deep messages have been found in either yet, and I am sure some people tried, so it stands to reason that no such messages exist. Mathematical objects can be complicated and difficult to understand and go on for infinitely long without having secret messages hidden in them.
- sqeaky 2y ago
  Of course they can, and with an infinitely powerful machine it would be cheap to check.

gwern 2y ago

The MAC part sounds a bit like https://en.wikipedia.org/wiki/Chaffing_and_winnowing https://en.wikipedia.org/wiki/Chaffing_and_winnowing