First, I don’t understand this domain well enough to pinpoint why that doesn’t work, but I trust in the math enough to believe the result regardless.
That said, I don’t think that you can write a program which searches through programs until it finds one which outputs a specific string, that also halts. It seems like it could always get stuck on some program that doesn’t halt, and it can’t figure out if a given program will halt or not.
You could have it do a few steps of each program at a time. Then it doesn’t get stuck on the non-halting programs, they just eat up more and more of its resources.
First, I don’t understand this domain well enough to pinpoint why that doesn’t work, but I trust in the math enough to believe the result regardless.
That said, I don’t think that you can write a program which searches through programs until it finds one which outputs a specific string, that also halts. It seems like it could always get stuck on some program that doesn’t halt, and it can’t figure out if a given program will halt or not.
You could have it do a few steps of each program at a time. Then it doesn’t get stuck on the non-halting programs, they just eat up more and more of its resources.