2 ms·
My computer is not Turing complete, yet it can do arbitrary computations. FHE is bounded-memory Turing complete, the same as every computer on the planet.
by rrobukef 6y ago
My computer is not Turing complete, yet it can do arbitrary computations.
FHE is bounded-memory Turing complete, the same as every computer on the planet.
- SilasX 6y agoSee my cousin comment [1]: your computer does not require that you be able to determine whether your programs halt and then unroll them into a fixed-size stateless circuit, so that's a big difference. [1] https://news.ycombinator.com/item?id=24022339 https://news.ycombinator.com/item?id=24022339
- rrobukef 6y agoThere are two solutions for this. 1) The halting problem is decidable (but untractable) for bounded machines. 2) Instead of deciding when to halt inside the machine, do it outside with continuations. Encrypted computing will always enforce time-limits thus this is not an issue.