> The program must fit in a genome-sized instruction set of about 1 gigabyte

True but this can be a lot larger, maybe even a 1 exabyte instruction size since it depends on he programming language used to express the program. And even accounting for the invariance of runtimes at scale*, the constant factor might be gigantic since we have to build up a lot of cellular machinery first. Reminds me of the Carl Sagan quote: To make a sandwich,you must first construct the universe!

* For example, to translate a program from language A to language B, you can dedicate a constant size to write a language A to B translator. Thus at large program sizes , the kolmogorov complexity (i.e instruction set size) is fairly similar between programs since the size of the program dominates the size of the translator program which is constant. But the constant factor for cellular machinery might be gigantic**

** Or not if we only need a rough simulation

It's "to make an apple pie from scratch".

You can make a sandwich with two slices of bread and whatever filling.