Makes sense. I was thinking if there could be a bootable fuzzer of this kind, but you're right that it would be very difficult for it to be both usable and not crash very quickly.
I think once you found all possible instructions it shouldn't be too hard (for someone much smarter then me) to essentially generate a minimal OS that systematically tries out all found instructions from ring 0. That should dramatically reduce the amount of reboots necessary to actually try them all out compared to bruteforcing them from ring 3
Firstly, the paper clearly explains that a userland (ring 3) process can easily discriminate between instructions that do not exist and instructions that the process lacks the credentials to execute simply because the two cases give rise to different exceptions (undefined and general protection, respectively).
Secondly, one could trivially log "I am going to try this" to a file, go ahead and do it, and if the machine crashes you consult the log and read exactly what was about to be done and evidently caused a hang. You don't necessarily need to write a log entry after doing something, in this case you can deterministically log what you are about to do and make deductions therefrom.
It would also be fairly simple to build for any computer using just an arduino or a raspberry pi. The computer could send a periodic signal over the serial port, if the arduino doesn't receive a signal for some time it shorts the mainboard's reset pin, causing a reboot.