4 ms·

Apologies if this is a dumb question, but aren't all computations inherently serial? In that a Turing machine performs operations serially?

by glial 2y ago

ninetyninenine 2y ago
Yeah it's talking about a new feature for LLMs where the output of an LLM is fed back in as input and done again and again and again and this produces way more accurate output.
ants_everywhere 2y ago
You can model parallel computation by an arbitrary finite product of Turing machines. And then, yes, you can simulate that product on a single Turing machine. I think that's the sort of thing you have in mind? But I'm not aware of what "inherently serial" means. The right idea likely involves talking about complexity classes. E.g. how efficiently does a single Turing machine simulate a product of Turing machines? An inherently serial computation would then be something like a problem where the simulation is significantly slower than running the machines in parallel.
joe_the_user 2y ago
Aren't all computations inherently serial? No. "inherently serial" refers to problems that are specified serially and can't be spend up by parallel processing. The sum of a set of N numbers is an example of a problem that is not inherently serial. You can use parallel reduction to perform the computation in O(log(N)) time on an idealized parallel computer but it takes O(N) time on an idealized serial computer. And, it turns, exactly which problems are really are inherently serial is somewhat challenging problem.
- visarga 2y ago
  > The sum of a set of N numbers is an example of a problem that is not inherently serial. But addition with floats (not reals) is non associative.
  - immibis 2y ago
    They didn't say floats, and the sum of a set of floats is not uniquely defined as a float for the rain you stated, at least not without specifying a rounding mode. Most people use "round to whatever my naïve code happens to do" which has many correct answers. To add up a set of floats with only the usual 0.5ULP imprecision, yes, isn't trivial.
  - rand_r 2y ago
    Using hardware floating point types is not suitable if mathematical correctness matters, and is largely a deprecated practice. Check out Python’s fraction module for example, for exact arithmetic[0]. [0]: https://www.geeksforgeeks.org/fraction-module-python/ https://www.geeksforgeeks.org/fraction-module-python/
tromp 2y ago
Turing Machines are just one of many computational models. Others offer more parallelism. Two examples: In lambda calculus, disjoint redexes can be reduced in parallel. And in interaction nets, all active pairs can be reduced in parallel [1]. []1 https://en.wikipedia.org/wiki/Interaction_nets https://en.wikipedia.org/wiki/Interaction_nets

Apologies if this is a dumb question, but aren't all computations inherently serial? In that a Turing machine performs operations serially?

by glial 2y ago

Apologies if this is a dumb question, but aren't all computations inherently serial? In that a Turing machine performs operations serially?

ninetyninenine 2y ago

Yeah it's talking about a new feature for LLMs where the output of an LLM is fed back in as input and done again and again and again and this produces way more accurate output.

ants_everywhere 2y ago

You can model parallel computation by an arbitrary finite product of Turing machines. And then, yes, you can simulate that product on a single Turing machine. I think that's the sort of thing you have in mind? But I'm not aware of what "inherently serial" means. The right idea likely involves talking about complexity classes. E.g. how efficiently does a single Turing machine simulate a product of Turing machines? An inherently serial computation would then be something like a problem where the simulation is significantly slower than running the machines in parallel.

joe_the_user 2y ago

Aren't all computations inherently serial? No. "inherently serial" refers to problems that are specified serially and can't be spend up by parallel processing. The sum of a set of N numbers is an example of a problem that is not inherently serial. You can use parallel reduction to perform the computation in O(log(N)) time on an idealized parallel computer but it takes O(N) time on an idealized serial computer. And, it turns, exactly which problems are really are inherently serial is somewhat challenging problem.

visarga 2y ago
> The sum of a set of N numbers is an example of a problem that is not inherently serial. But addition with floats (not reals) is non associative.
- immibis 2y ago
  They didn't say floats, and the sum of a set of floats is not uniquely defined as a float for the rain you stated, at least not without specifying a rounding mode. Most people use "round to whatever my naïve code happens to do" which has many correct answers. To add up a set of floats with only the usual 0.5ULP imprecision, yes, isn't trivial.
- rand_r 2y ago
  Using hardware floating point types is not suitable if mathematical correctness matters, and is largely a deprecated practice. Check out Python’s fraction module for example, for exact arithmetic[0]. [0]: https://www.geeksforgeeks.org/fraction-module-python/ https://www.geeksforgeeks.org/fraction-module-python/

tromp 2y ago

Turing Machines are just one of many computational models. Others offer more parallelism. Two examples: In lambda calculus, disjoint redexes can be reduced in parallel. And in interaction nets, all active pairs can be reduced in parallel [1]. []1 https://en.wikipedia.org/wiki/Interaction_nets https://en.wikipedia.org/wiki/Interaction_nets