You can't write every possible term of that type. However, you can write a program that performs the same computation as any expression of that type by explicit

You can't write every possible term of that type. However, you can write a program that performs the same computation as any expression of that type by explicitly breaking recursion out, e.g. via Free (() ->) Integer And then using corecursion to evaluate this step by step. The actual definition of Turing completeness is the ability to implement any program that a Turing machine can compute, which you can with corecursion.