Turing complete computer implemented machine learning method and system

• US 5,946,674 A
• Filed: 06/29/1998
• Issued: 08/31/1999
• Est. Priority Date: 07/12/1996
• Status: Expired due to Fees

• Current Assignee: Peter Nordin, Wolfgang Banzhaf
• Original Assignee: Peter Nordin, Wolfgang Banzhaf
• Inventors: Nordin, Peter, Banzhaf, Wolfgang
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US09/106,887
• Time in Patent Office: 428 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

One or more machine code entities such as functions are created which represent solutions to a problem and are directly executable by a computer. The programs are created and altered by a program in a higher level language such as "C" which is not directly executable, but requires translation into executable machine code through compilation, interpretation, translation, etc. The entities are initially created as an integer array that can be altered by the program as data, and are executed by the program by recasting a pointer to the array as a function type. The entities are evaluated by executing them with training data as inputs, and calculating fitnesses based on a predetermined criterion. The entities are then altered based on their fitnesses using a machine learning algorithm by recasting the pointer to the array as a data (e.g. integer) type. This process is iteratively repeated until an end criterion is reached. The entities evolve in such a manner as to improve their fitness, and one entity is ultimately produced which represents an optimal solution to the problem. Each entity includes a plurality of directly executable machine code instructions, a header, a footer, and a return instruction. The instructions include branch instructions which enable subroutines, leaf functions, external function calls, recursion, and loops. The system can be implemented on an integrated circuit chip, with the entities stored in high speed memory in a central processing unit.

Claims

1. A programmed Turing complete computer including a memory for storing an indirectly executable computer program and a processor for executing the program, the program including:

a first instruction that points to and designates machine code stored in the memory as data;

a second instruction that points to and designates machine code stored in the memory as directly executable machine code;

a third instruction that alters machine code pointed to by the first instruction; and

a fourth instruction that executes machine code pointed to by the second instruction; and

the processor, memory and program operating in combination for learning by performing the steps of;

(a) creating and storing a plurality of machine code entities, each including a directly executable instruction which includes run time data in the memory;

(b) for at least one of the entities, performing the substeps of;

(b1) executing the second instruction to point to the entity; and

(b2) executing the fourth instruction using input data to produce a result; and

(b3) evaluating the result;

(c) for at least one of the entities, performing the substeps of;

(c1) executing the first instruction to point to the entity; and

(c2) executing the third instruction to alter the entity using an alteration algorithm to include a different directly executable instruction; and

(d) repeating steps (b) and (c) until an end criterion based on the evaluation in step (b3) is reached.

2. A computer as in claim 1, in which:

the first instruction points to and designates machine code stored in the memory as data by casting a pointer thereto as a data pointer; and

the second instruction points to and designates machine code stored in the memory as directly executable code by casting a pointer thereto as a function pointer.

3. A computer as in claim 1, in which:

the first instruction points to and designates machine code stored in the memory as data by creating a data pointer thereto; and

the second instruction points to and designates machine code stored in the memory as directly executable code by creating a function pointer thereto.

4. A computer as in claim 1, in which:

step (a) comprises creating each entity as comprising a header and a footer; and

step (c2) comprises preventing the header and footer from being altered.

5. A computer as in claim 1, in which:

step (a) comprises creating each entity as comprising a return instruction; and

step (c2) comprises preventing the return instruction from being altered.

6. A computer as in claim 1, in which the alteration algorithm in step (c2) comprises a genetic algorithm.

7. A computer as in claim 1, in which step (a) comprises creating each entity as comprising a plurality of directly executable instructions.

8. A computer as in claim 7, in which step (a) comprises randomly selecting the directly executable instructions from a set of directly executable instructions.

9. A computer as in claim 7, in which step (d2) comprises genetically altering the directly executable instructions.

10. A computer as in claim 7, in which:

one of the directly executable instructions comprises an operator and an operand; and

step (c2) comprises genetically mutating the operand.

11. A computer as in claim 7, in which two of the directly executable instructions comprise operators respectively;

and

step (c2) comprises genetically crossing the operators.

12. A computer as in claim 1, in which step (a) comprises randomly selecting the directly executable instruction from a set of directly executable instructions.

13. A computer as in claim 1, in which step (c2) comprises genetically altering the directly executable instruction.

14. A computer as in claim 1, in which:

the directly executable instruction comprises an operator and an operand; and

step (c2) comprises genetically mutating the operand.

15. A computer as in claim 1, in which:

the memory comprises a main memory and a processor memory that is part of the processor; and

step (a) comprises storing the entities in the processor memory.

16. A computer as in claim 15, comprising an integrated circuit chip, in which the processor and the processor memory are formed on the chip.

17. A computer as in claim 1, in which at least a portion of the program is stored in processor memory.

18. A computer as in claim 17, in which:

the processor memory comprises a non-volatile memory section; and

said at least a portion of the program is stored in the non-volatile memory section.