News for hackers. Stuff that matters.
Re:Apollo 11 vs. USB-C Chargers (2020) by progval on Wednesday December 27, 2023 @02:37AM (#38779881)
Re:Apollo 11 vs. USB-C Chargers (2020) by kragen on Wednesday December 27, 2023 @02:50AM (#38779936)
a universal turing machine is a particular machine which can simulate all other turing machines. the gpac, by contrast, is a family of machines: all machines built out of such-and-such a set of parts

you can't simulate an 11-integrator general-purpose analog computer or other differential analyzer with a 10-integrator differential analyzer, and you can't simulate a differential analyzer with 0.1% error on a (more typical) differential analyzer with 1% error, unless it's 100× as large (assuming the error is gaussian)

the ongoing research in the area is of course very interesting but a lot of it relies on an abstraction of the actual differential-analyzer problem in which precision is infinite and error is zero

Re:Apollo 11 vs. USB-C Chargers (2020) by thriftwy on Wednesday December 27, 2023 @03:01AM (#38779990)
Sure, you cannot easily simulate another analog computer, but this is not the requirement. The requirement is turing completeness, which can be done.
Re:Apollo 11 vs. USB-C Chargers (2020) by lisper on Wednesday December 27, 2023 @03:05AM (#38780011)
It can? How?
Re:Apollo 11 vs. USB-C Chargers (2020) by kragen on Wednesday December 27, 2023 @03:13AM (#38780058)
as i understand it, with infinite precision; the real numbers within some range, say -15 volts to +15 volts, have a bijection to infinite strings of bits (some infinitesimally small fraction of which are all zeroes after a finite count). with things like the logistic map you can amplify arbitrarily small differences into totally different system trajectories; usually when we plot bifurcation diagrams from the logistic map we do it in discrete time, but that is not necessary if you have enough continuous state variables (three is obviously sufficient but i think you can do it with two)

given these hypothetical abilities, you can of course simulate a two-counter machine, but a bigger question is whether you can compute anything a turing machine cannot; after all, in a sense you are doing an infinite amount of computation in every finite interval of time, so maybe you could do things like compute whether a turing machine will halt in finite time. so far the results seem to support the contrary hypothesis, that extending computation into continuous time and continuously variable quantities in this way does not actually grant you any additional computational power!

this is all very interesting but obviously not a useful description of analog computation devices that are actually physically realizable by any technology we can now imagine

Re:Apollo 11 vs. USB-C Chargers (2020) by fanf2 on Wednesday December 27, 2023 @06:09AM (#38780896)
Except that infinite precision requires infinite settling time. (Which I guess is the analogue computing version of arithmetic not being O(1) even though it is usually modelled that way.)
Re:Apollo 11 vs. USB-C Chargers (2020) by couchand on Wednesday December 27, 2023 @09:03AM (#38781979)
Infinite precision is just analog's version of an infinitely-long tape.
Re:Apollo 11 vs. USB-C Chargers (2020) by fanf2 on Wednesday December 27, 2023 @12:03PM (#38783953)
Right :-) I prefer to say a Turing machine’s tape is “unbounded” rather than “infinite” because it supports calculations of arbitrarily large but finite size. So in the analogue case, I would say unbounded precision and unbounded waiting time.
Re:Apollo 11 vs. USB-C Chargers (2020) by lisper on Wednesday December 27, 2023 @10:47AM (#38783106)
But even with infinite precision, how do you build a universal analog computer? And how do you program it?
Re:Apollo 11 vs. USB-C Chargers (2020) by progval on Wednesday December 27, 2023 @06:22PM (#38788097)
Any Turing machine is a (computable) function; and https://www.sciencedirect.com/science/article/pii/S0885064X0... shows any computable function can be computed by a GPAC. Therefore, if you take any universal Turing machine, there exists a GPAC that computes that Turing machine; and it is programmable because you can change the input it would give to the emulated Turing machine. Sure it's inefficient due to the two layers of emulation, but it shows it's possible.
Re:Apollo 11 vs. USB-C Chargers (2020) by lisper on Wednesday December 27, 2023 @07:04PM (#38788415)
Ah. TIL. Thanks!
Re:Apollo 11 vs. USB-C Chargers (2020) by Dylan16807 on Wednesday December 27, 2023 @12:31PM (#38784255)
Infinite precision is exponentially more difficult. It's very easy to have unbounded tape, with a big buffer of tape and some kind of "factory" that makes more tape when you get near the edge. Unbounded precision? Not going to happen in a real machine. You get to have several digits and no more.
Re:Apollo 11 vs. USB-C Chargers (2020) by lisper on Wednesday December 27, 2023 @10:49AM (#38783124)
It's much worse than that. There is this little thing called Planck's constant, and there's this other little thing called the second law of thermodynamics. So even if you allow yourself arbitrarily advanced technology I don't see how you're doing to make it work without new physics.
Re:Apollo 11 vs. USB-C Chargers (2020) by thriftwy on Wednesday December 27, 2023 @03:17AM (#38780077)
It would not be very interesting. You will lose all the interesting properties of analog computer and it would be a poorly performing turing machine. Still it would have those loops and branches necessary, since you can always build digital on top of analog with some additional harness.