4 ms·
Okay but that example is just one conditional branching. Turing-completeness requires that you be able to e.g. keep looping back until some condition is met. I
by SilasX 6y ago
Okay but that example is just one conditional branching. Turing-completeness requires that you be able to e.g. keep looping back until some condition is met.
If you want to build arbitrary functions like you've described, it reduces to the question of whether you can "unroll" the function, given its inputs[1], into a (stateless) circuit. But that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop before it starts), not the general recursive functions you need for Turing-completeness.
Anyone know how you pull off general recursive functions from just addition and multiplication?
[1] and in FHE you don't know the inputs either, which is another kink.
- ogogmad 6y ago> that would still IIUIC just get you primitive recursive functions (i.e. those where you can know the upper bound on the number of loop iterations for any loop before it starts) The primitive recursive functions cannot be expressed using circuits. Circuits by definition can only express polynomials, which have a much smaller growth rate than what primitive recursive functions are capable of. [edit] Actually, probably a better reason is that in primitive recursion, the running time can depend on the input. For a circuit, the running time is independent of the input.
- extropy 6y agoThe circuit that repeatedly multiplies the previous result with itself has higher than exponential growth rate.
- ogogmad 6y agoNo, because you can only multiply a fixed number of times.
- lalaland1125 6y agoGood luck finding something that grows faster than https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function
- suyjuris 6y agoEasy, just square it. Also, the Ackermann function is not a primitive recursive function.
- R0b0t1 6y agoFHE is just a math equation. Can you accept the requirement that you process the state more than once? If so you could do something like encode the atomic state of a silicon circuit somehow and step it forward in time. That is probably what the researcher is referring to. You can encapsulate computation, but not in a single math equation.