4 ms·
After putting some thought into this during a deeper comment chain somewhere, I thought about it this way: FHE is equivalent to circuits, i.e., every circuit h
by ketzu 6y ago
After putting some thought into this during a deeper comment chain somewhere, I thought about it this way:
FHE is equivalent to circuits, i.e., every circuit has a representation as a FHE. I feel like the idea is: Circuits can perform arbitrary computations on a limited size input, but not on an arbitrary size inputs. Loops are not a problem, as they are an implementation detail. Unbounded output is not possible on a touring machine that halts for all inputs of size s limited by some constant. There exists a circuit that would compute the same thing, as you can take the (binary encoded) results of the touring machine and just create a truth table from that, which describes a circuit. Circuits are interesting because they are usually limited in size.
So you compile your program into a circuit of a fixed size and can then compute solutions of this size. If you are interested in larger problems, you compile your program into a larger circuit. E.g., a function returing an 32bit integer and taking 20 32bit integers as parameters can be represented this way (without infinite loops, but those aren't covered by turing machines either), no matter the computation within that function.
edit: correction, obviously a circuit can not represent all partial functions, only functions (i.e., all inputs have an output).
- giomasce 6y agoNo, you cannot convert an arbitrary Turing machine to a circuit. Not even if you assume a bounded input size. Not even if you assume just one single allowed input, because you might not be able to know if that Turing machine ever terminates on that input. And loops are not an implementation details. Bounded loop are, one might argue, an implementation detail, but unbounded loops are precisely _the_ problem: in general it is impossible, given an arbitrary Turing machine (or an arbitrary C, Python, whatever Turing-complete language program), to give an upper bound on the number of iterations its loops will require.
- ketzu 6y agoSeems like I didn't put enough thought into it and my computability class has been too long ago! In hindsight it's kind of obvious: All functions computed by circuits must be a function an can not be a partial function, because a circuit can't output nothing.
- jhanschoo 6y agoketzu isn't claiming that one can always describe a Turing machine using addition and multiplication only, only that one can describe a Turing machine's map on bounded inputs using addition and multiplication on the input only.
- giomasce 6y agoAnd that's precisely what I challenged. You can't even describe a Turing machine on one single input (using whatever operations you like) if you're not able to determine if that machine is going to terminate. And in general you are not (at least, I am not; if you are, I happen to have a few Turing machines for which I'd be happy to pay to know if they're going to terminate or not; good money, I promise).
- jhanschoo 6y agoYou hold a misconception. The task is not that; instead we assume that we already have a table that correctly describes the TM's maps from bounded input to output when they terminate. His claim is that this table can be expressed as a function in addition and multiplication with the input as operands. To be more precise, with the input and constant numbers (arbitrarily choosable while designing the description of the function) as operands. Incidentally, > You can't even describe a Turing machine on one single input (using whatever operations you like) is false, we can simply encode it as the encoded tuple of the TM and the input; this is a standard construct when we talk about simulating TMs with a UTM.
- giomasce 6y ago> The task is not that; instead we assume that we already have a table that correctly describes the TM's maps from bounded input to output when they terminate. His claim is that this table can be expressed as a function in addition and multiplication with the input as operands. Ok, if the task is this then everything is very easy, I agree. I was commenting on a much harder task, i.e., converting a generic TM to a function adding and multiplying the inputs. That is something you can't do. > is false, we can simply encode it as the encoded tuple of the TM and the input; this is a standard construct when we talk about simulating TMs with a UTM. I don't see how that disproves my assertion. I was saying something different, which has to do with your (correct) first assertion: a TM cannot establish if another TM is going to terminate on a certain input.
- deleted 6y ago[deleted]