6 ms·

No, 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 inp

No, 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 ago
Seems 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 ago
ketzu 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 ago
  And 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 ago
    You 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.
      - jhanschoo 6y ago
        > I was saying something different It's important to be precise with language; said encoding is a description of a given TM on a particular input, since a map exists from it to the space of outputs union DOESNOTTERMINATE. Now, whether or not this map is a computable function is a different question.
- zenexer 6y ago
  Alan Turing proved that a solution to the halting problem cannot exist. Per Wikipedia:[0] > A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It cannot be possible to “map” a Turing machine with a finite number of operations. Without true decision trees and loops, FHE isn’t Turing complete. At minimum, there needs to be a concept of a conditional jump—if X, jump to instruction Y. You can unravel some programs into a finite set of instructions, but that doesn’t make FHE Turing complete. Take the following code, for example: function f(x): while x == 1: do nothing return x For a machine to be Turing complete, it must be able to run that function. FHE can’t do that, by definition; it would reveal information about the input. [0]: https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
  - heavenlyblue 6y ago
    You can simulate that program you gave on a finite circuit because you can simulate it on your computer which is a finite circuit.
    - zenexer 6y ago
      Your computer has circuitry that is capable of being reused. It isn’t a simulator; it could, in theory, run that loop ad infinitum. FHE can’t reuse circuitry. There’s no concept of, “based on the output, we now need to plug it back in and repeat.” Instead, it has to literally repeat that circuitry for every possible loop.
      - heavenlyblue 6y ago
        You could re-run FHE until some condition fails. This is what your CPU does BTW. Again - the only reason you shouldn’t do that in homomorphic encryption is because this way you will leak run duration information.
        zenexer 6y ago
deleted 6y ago
[deleted]

ketzu 6y ago

Seems 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 ago

ketzu 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 ago
And 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 ago
  You 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.
    - jhanschoo 6y ago
      > I was saying something different It's important to be precise with language; said encoding is a description of a given TM on a particular input, since a map exists from it to the space of outputs union DOESNOTTERMINATE. Now, whether or not this map is a computable function is a different question.
zenexer 6y ago
Alan Turing proved that a solution to the halting problem cannot exist. Per Wikipedia:[0] > A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It cannot be possible to “map” a Turing machine with a finite number of operations. Without true decision trees and loops, FHE isn’t Turing complete. At minimum, there needs to be a concept of a conditional jump—if X, jump to instruction Y. You can unravel some programs into a finite set of instructions, but that doesn’t make FHE Turing complete. Take the following code, for example: function f(x): while x == 1: do nothing return x For a machine to be Turing complete, it must be able to run that function. FHE can’t do that, by definition; it would reveal information about the input. [0]: https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- heavenlyblue 6y ago
  You can simulate that program you gave on a finite circuit because you can simulate it on your computer which is a finite circuit.
  - zenexer 6y ago
    Your computer has circuitry that is capable of being reused. It isn’t a simulator; it could, in theory, run that loop ad infinitum. FHE can’t reuse circuitry. There’s no concept of, “based on the output, we now need to plug it back in and repeat.” Instead, it has to literally repeat that circuitry for every possible loop.
    - heavenlyblue 6y ago
      You could re-run FHE until some condition fails. This is what your CPU does BTW. Again - the only reason you shouldn’t do that in homomorphic encryption is because this way you will leak run duration information.
      - zenexer 6y ago

deleted 6y ago

[deleted]