SCS Undergraduate Thesis Topics
|Sam Tetruashvili||Manuel Blum||Inductive Inference of Integer Sequences|
Inductive inference denotes hypothesizing a general rule from examples. In this senior thesis, we give a model for inductively inferring integer sequences. Within this model we give algorithms that can (inductively) infer integer sequences with high confidence, under the assumption that all the terms of the sequence are accessible. We provide tight bounds on the number of sequence terms an inference algorithm needs to see before it can make an inference it is confident in.
We use The On-Line Encyclopedia of Integer Sequences (OEIS) to evaluate our model. We are currently able to infer about 18.9% of the OEIS using the methods given in this thesis. We also implement a website for inferring sequences that is meant to complement the OEIS. This site can be publicly accessed at http://atemi.cdm.cs.cmu.edu/~samt/sequences.html