3 ms·

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

• gizmo686 5y ago
  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.
  • cybernautique 5y ago
    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)?