Appropriate syntax checks halt programs whenever they attempt to do something impossible, like writing a non-existent weight. Since the new ``WriteWeight'' primitive has an additional argument (to be guessed correctly), successful programs tend to be less likely.
RESULTS. Out of runs using up a total search time of time steps, 3 runs generated weight vectors fitting the training data. All of them allowed for perfect generalization on all the test data. During execution, one of them filled the storage as seen in table 1. The program ran for 399 out of 1024 allocated time steps. Its space probability was . What it does is this:
(0) Allocate one cell on the work tape. Initialize with zero. Set Min = Min-1.
(2) Increment the contents of address -1.
(4) Make equal to the contents of address -1.
(7) Jump to address 0.
Repeated execution of the instruction at address 0 unnecessarily allocates 100 cells of the work tape but does not do any damage other than slightly slowing down the program. Using different sets of 3 training examples (obtained by randomly permuting the input units that are never on), led to very similar generalization results.
Numerous additional experiments (including rather complicated maze tasks) were performed by Norbert Jankowski and Stefan Heil at TUM. Some are described e.g. in Heil's diploma thesis (1995).
General remarks. The bias towards algorithmic simplicity is a very general one. It is weaker than most kinds of problem specific inductive bias, e.g. (Utgoff, 1986; Haussler, 1988). If a solution is indeed simple, the bias is justified (it does not require us to know ``the way in which the solution is simple''). If the solution is not simple, the bias towards algorithmic simplicity won't do much damage: even in case of algorithmically complex solutions we cannot lose much if we focus our search on simple candidates first, before looking at more complex candidates. This is because in general the complex candidates greatly outnumber the simple ones. The few simple ones don't significantly affect total search time of an optimal search algorithm.