3 ms·
> Yes it is, it's Turing-completeness. While this may be a sensible interpretation, and I am willing to believe it's used in that interpretation in some fields
by ketzu 6y ago
> Yes it is, it's Turing-completeness.
While this may be a sensible interpretation, and I am willing to believe it's used in that interpretation in some fields, I have a hard time actually finding a definition of that form.
I also have a problem with using it in this way: In circuits the size of the circuit limits your input size. But given a maximum size of the input, and no size limitations on the circuit, you can construct a circuit that produces the same result as a turing machine that halts. So you can compute whatever you want (i.e. arbitrary) but you are limited by the size of your current circuit.
(Completely unhelpful but always fun to look at for words: https://books.google.com/ngrams/graph?content=arbitrary+computation%2Cturing+complete&corpus=26&year_start=1800&year_end=2019&smoothing=3&direct_url=t1%3B%2Carbitrary%20computation%3B%2Cc0%3B.t1%3B%2Cturing%20complete%3B%2Cc0#t1%3B%2Carbitrary%20computation%3B%2Cc0%3B.t1%3B%2Cturing%20complete%3B%2Cc0 https://books.google.com/ngrams/graph?content=arbitrary+comp... )
- SilasX 6y agoAs gone over in the discussion above [1], you can only compute those TMs that you can unroll into a fixed size circuit, which means (at most) only the subset of TMs that halt; doing this in the general case requires a halting oracle, which is not possible. That's not arbitrary computation by any reasonable definition. Furthermore, it adds a huge constraint to programming: you can only implement loops with iterations bounded by a constant known at compile time. (And if you derive any of those constants from the inputs at the time you're compiling it for the FHE machine to execute, you've leaked information about said inputs.) [1] https://news.ycombinator.com/item?id=24019212 https://news.ycombinator.com/item?id=24019212