You don’t specify the implementation of “proves(code, maxsteps)”.
Nothing depends on the details of proof verifier, since it completely covers all proofs up to some length, a set of proofs which is completely defined by the logical language. The arguments of proves(-,-) determine its value (and it’s even a primitive recursive function).
On the other hand, pathological formal language can be constructed, that makes proof of “main()==1” arbitrary large (e.g. where 1 is represented by 3^^^3 symbols). Thus it is better to be proven that formal language isn’t pathological, i.e there is no prover proves’ that satisfies condition
Enumeration order of proofs is not specified, so we can construct pathological prover, that reorders proofs such that all proofs of “main()==1” require more steps than maxsteps.
You can’t influence the length of a proof by placing it at a different position in some list of proofs. Parameter ‘maxsteps’ specifies the maximum length (or Gödel number) of the proofs that get checked, not the maximum number of steps performed by the proof checker algorithm.
Usually, when posing puzzles, it is best to try to minimise the number of unstated assumptions the solution depends upon—or there won’t be a unique answer.
Nothing depends on the details of proof verifier, since it completely covers all proofs up to some length, a set of proofs which is completely defined by the logical language. The arguments of proves(-,-) determine its value (and it’s even a primitive recursive function).
On the other hand, pathological formal language can be constructed, that makes proof of “main()==1” arbitrary large (e.g. where 1 is represented by 3^^^3 symbols). Thus it is better to be proven that formal language isn’t pathological, i.e there is no prover proves’ that satisfies condition
Enumeration order of proofs is not specified, so we can construct pathological prover, that reorders proofs such that all proofs of “main()==1” require more steps than maxsteps.
You can’t influence the length of a proof by placing it at a different position in some list of proofs. Parameter ‘maxsteps’ specifies the maximum length (or Gödel number) of the proofs that get checked, not the maximum number of steps performed by the proof checker algorithm.
Ouch. maxsteps means maxprooflenght. My inattention, sorry.
...but the the “logical language” is not specified! That is one of the implementation details that is missing in the problem specification.
You know, there are always unstated assumptions, like sanity of the reader.
Usually, when posing puzzles, it is best to try to minimise the number of unstated assumptions the solution depends upon—or there won’t be a unique answer.