I think that it’s a 15 minute problem for someone who knows theoretical CS well
Question 1 certainly relates to well-known theory, e.g. Chomsky’s hierarchy of formal languages. The exact answer to the question really depends on what you want from your list. Do you just want a list of theorems in any order? Do you want a list of all theorems from simplest to most complex? Do you care about how long it takes to generate each item on the list? Formal systems vary widely as to whether their theorems can be enumerated efficiently, in order, or at all.
Questions 2-4 are getting pretty esoteric. This is the realm of “halting probabilities” and algorithmic information theory. There seems to be a big gap between general theory and the study of specific formal systems. If I google “statistics of formal systems”, I find exactly one match, a 2008 paper that leads nowhere… I feel like the study of primes by probabilistic number theory might qualify, as you can definitely define a formal system whose “theorems” are the primes. But I just don’t see any work out there, proving theorems about statistical learning of formal systems. Maybe I’ve overlooked it.
Question 1 certainly relates to well-known theory, e.g. Chomsky’s hierarchy of formal languages. The exact answer to the question really depends on what you want from your list. Do you just want a list of theorems in any order? Do you want a list of all theorems from simplest to most complex? Do you care about how long it takes to generate each item on the list? Formal systems vary widely as to whether their theorems can be enumerated efficiently, in order, or at all.
Questions 2-4 are getting pretty esoteric. This is the realm of “halting probabilities” and algorithmic information theory. There seems to be a big gap between general theory and the study of specific formal systems. If I google “statistics of formal systems”, I find exactly one match, a 2008 paper that leads nowhere… I feel like the study of primes by probabilistic number theory might qualify, as you can definitely define a formal system whose “theorems” are the primes. But I just don’t see any work out there, proving theorems about statistical learning of formal systems. Maybe I’ve overlooked it.