Maybe someone here knows: is there a standard transformation from sequential logic to combinational logic? I'm thinking something like that immediately gives me the 3sat representation of an algorithm that has an iteration step.
3sat is not Turing-complete since every 3sat problem is finite but Turing machines have infinite tapes. Combinatory logic[0] is Turing-complete but combinational logic[1] is not for the same reason.
Ya you're right I've confused complexity with universality. But actually it's not there actually exist TMs with infinitely long tapes so actually my question still makes some kind of sense - how do I express a finite program (that I constrain to not loop infinitely) as a boolean or combinational circuit.
My understanding is that you don't get a choice. You either allow loops, and accept that they might go infinite, or you axe them altogether. I believe this is a direct corollary of the halting problem, but please correct me if I'm wrong.
The halting problem is solvable for turing machines with a finite tape. A simple encoding of a finite turing machine into SAT is as follows:
1) Let n be the size of the tape.
2) Consider all binary strings of length n
3) For each string {A_i} run the finite turing machine until it either terminates or repeats a state. Since this model has a finite tape, it is guaranteed to do one of these. If it terminates, consider its output to be 0, prepended to the final tape state: 0|{B_i}. If it loops, consider its output to be the n+1 length string containing all 1s.
In this way, the turing machine is defined exactly as a function f : {0,1}^n -> {0,1}^n+1
All such functions can be trivially encoded into a boolean circuit. And all such circuts can be reduced to an instance of 3SAT.
Granted, this encoding is exponentional with regards to n, so isn't useful if you want to reason about complexity, but it does show that it is not computationally impossible, as the general case of the halting problem is.
Thank you! That was really intuitive, it's nice to have a little midnight thought snack before bed. That mapping and description strike me as integral-like in their description. I,ll read into SATs, any resources you'd recommend for topics like this (or related)?
