[0] https://en.m.wikipedia.org/wiki/Combinatory_logic [1] https://en.m.wikipedia.org/wiki/Combinational_logic
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.