4 ms·
You can't unroll an unbounded loop, you don't know how many times to unroll. To have Turing machine you need to need to know from your program state if you reac
by giomasce 6y ago
You can't unroll an unbounded loop, you don't know how many times to unroll. To have Turing machine you need to need to know from your program state if you reached the end of your loop or not (i.e., you need to evaluate the "while" condition), and by definition FHE shouldn't allow you to extract information from your program state.
- IshKebab 6y agoYou can unroll a sufficient number of times. There would be an upper limit on iterations and it would presumably be horrible inefficient, but I can't see why it wouldn't work.
- layer8 6y agoIf you know how many iterations are sufficient, the unbounded loop could have been written as a bounded loop in the first place. For truly unbounded loops, you’re still stuck.
- IshKebab 6y agoI mean, that's the same as saying no computer is Turing complete because it doesn't have infinite memory. I'm not saying it is a practical solution to unroll a loop that might run a billion times.
- giomasce 6y agoI am not saying there are not practical ways to do useful computation with this stuff. I am commenting on the theoretical remark that any algorithm (as in any Turing machine) can be executed with FHE, which is false, as it can be proved that it is impossible to compute, given an abstract Turing machine, an upper bound on the length of its execution.