Others have already mentioned halting problem and fun maths kind of related to it and I have not spent enough time pulling apart GB/GBC roms to see it but I would also have to wonder if the GBC ever did any in game opcode modification (I do not want to use the term dynamic recompilation but I will at least say it)- if there is one thing I have learned about 16 bit and old consoles is that memory is tight as you like but if there is two it is that games on these systems do love there little tricks.
Back on topic so to speak though what I would instead point you at is one of the things we saw on the DS via tools like no$gba and crystaltile2 (although it stems from the nitroSDK itself) was a kind of IO abstraction/commenting and function mapping tool (NEF files would be a fair starting point for a search term although
http://gbatemp.net/topic/73394-gbatemp-rom-hacking-documentation-project-wip/page__view__findpost__p__2782288 has something)- learning ASM both in general programming and for rom hacking, seeing the better guides to it (got to love HLA /
http://homepage.mac.com/randyhyde/webster.cs.ucr.edu/index.html ) and watching others do the same it is usually not very hard to teach them basics of opcode construction and if you were to say find the subtract lives routine and say I am going to change this into an add lives routine that would be absolutely fine too. Going for another example consider say the GBA where the first line of the rom is a jump to the binary but after that we look for the first reference back to the rom location (usually 08XXXXXX) as that marks the end of the IO, stack pointer setup and what have you.
I also want to link
http://www.youtube.com/watch?v=_MBWTqfCFd0 as it might well be relevant to what you are trying to do.
For my money this would be nearly as useful and spares you running up against the likes of the halting problem.
Romhacking.net
Author