Logical Induction with incomputable sequences

In the defi­ni­tion of a log­i­cal in­duc­tor, the de­duc­tive pro­cess is re­quired to be com­putable. This, of course, does not al­low the log­i­cal in­duc­tor to use ran­dom­ness, or pre­dict un­com­putable se­quences. The way traders were defined in the log­i­cal in­duc­tion pa­per, this was nec­es­sary, be­cause the traders were not given ac­cess to the out­put of the de­duc­tive pro­cess.

To fix this, a trad­ing strat­egy for day should be re­defined as a func­tion that takes in the out­put of the de­duc­tive pro­cess on day as its in­put, and out­puts what the log­i­cal in­duc­tion pa­per defines as a trad­ing strat­egy for day ; that is, an af­fine com­bi­na­tion of the form , where are sen­tences, are ex­press­ible fea­tures of rank , and . A trader is a func­tion which takes in and out­puts a trad­ing strat­egy for day . By Cur­ry­ing, a trader can be seen as a func­tion that takes in a num­ber and a list of sen­tences given by the de­duc­tive pro­cess, and out­puts an ex­press­ible fea­ture com­bi­na­tion as above. We can say that a trader is effi­ciently com­putable if this func­tion is com­putable in time polyno­mial in plus the to­tal length of the sen­tences out­put by the de­duc­tive pro­cess. The defi­ni­tion of ex­ploita­tion would be mod­ified in the nat­u­ral way, and there is also a nat­u­ral way to mod­ify the log­i­cal in­duc­tion al­gorithm, which will satisfy the log­i­cal in­duc­tion crite­rion.

As an ex­am­ple, sup­pose a log­i­cal in­duc­tor is given ac­cess to a sen­sor that reg­u­larly pro­duces bits based on what it ob­serves in the en­vi­ron­ment. We can rep­re­sent the data from the sen­sor with an ad­di­tional unary pred­i­cate that we add to the lan­guage, such that is true iff the th bit pro­vided by the sen­sor is a (this as­sumes that we’re work­ing in a the­ory that can in­ter­pret ar­ith­metic, so that ``″ can be ex­pressed in the lan­guage). The de­duc­tive pro­cess should out­put or on day (and also can out­put con­se­quences that it can de­duce from the val­ues of the bits it has seen so far). Or, if the log­i­cal in­duc­tor gets ac­cess to more em­piri­cal in­for­ma­tion or ran­dom bits as time goes on, there could be an in­creas­ing func­tion such that the de­duc­tive pro­cess out­puts the truth val­ues of on day . Note that in this situ­a­tion, the de­duc­tive pro­cess is com­putable as a func­tion of the bit­stream given by the sen­sor, so the traders may as well take in as in­put only the bits from the sen­sor that the de­duc­tive pro­cess has seen by day , rather than ev­ery sen­tence pro­duced by the de­duc­tive pro­cess.

This seems to be similar to what Vadim was do­ing in sec­tion 3 of this pa­per, ex­cept that that pa­per moved to a con­tin­u­ous set­ting, did not deal with com­putabil­ity, and aban­doned pre­dict­ing the­o­rems as a goal.

No comments.