We want to show that given any daemon, there is a smaller circuit that solves the problem.
Given any random circuit, you can not, in general, show whether it is the smallest circuit that produces the output it does. That’s just Rice’s theorem, right? So why would it be possible for a daemon?
Given any random circuit, you can not, in general, show whether it is the smallest circuit that produces the output it does. That’s just Rice’s theorem, right? So why would it be possible for a daemon?
Rice’s theorem applies if you replace “circuit” with “Turing machine”. The circuit version can be resolved with a finite brute force search.