Could anyone confirm if for every algorithm running on some architecture M, there is an equivalent boolean function, and that the length of this boolean function is proportional to the runtime of the algorithm? Meaning that if A is a polynomial algorithm, then the corresponding boolean function f is also polynomial in length (has a polynomial number of boolean operations).

And wouldn't it be interesting if there was a computer program where we could plugin an algorithm and obtain the corresponding boolean function? The input variables of f would be the bits corresponding to the input to A... sounds possible?

0