How to prove (un)decidability Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time limit when a program is given no input.
In other words - is this problem decidable or undecidable?
I was thinking of reducing the Halt problem when it is given no input, but I'm a bit unsure of whether I should concider the byte size and time limit as input as well, or how I should conquer this problem.
Thank you.
The problem is decidable. You can enumerate the (finitely many) programs that use at most $b$ bytes.
For each such candidate program $P$, you can check whether $P$ is valid program (for any reasonable representation) and execute it for up to $t$ time steps. Eventually you either find a program that prints $s$ (and accept) or you run out of programs (and reject).