Optical implementation of bounded non-deterministic Turing Machines

摘要

Method and an optical computation device for obtaining an indication about the existence of a feasible solution for a bounded instance of a problem that belongs to the non-deterministic polynomial class of problems, using parallel optical computations employing a multitude of light rays simultaneously propagating along paths in an optical arrangement. An optical arrangement that can implement a universal non deterministic Turing Machine that can solve bounded instances of problems of the class is determined. An initial incoming ray is directed to a point in the optical arrangement, that represents the initial configuration of the universal non deterministic Turing Machine, such that the initial configuration corresponds to the bounded instance. Each incoming ray is split within the optical arrangement into two or more outgoing rays at pre-determined locations in the optical arrangement. Each incoming ray and/or outgoing rays is amplified, such that each of the outgoing rays has at least the same power as the initial incoming ray. The position, measured in two or more dimensions, of the rays, on the components of the optical arrangement, is used to represent intermediate and/or final computation results, and whenever an outgoing ray is detected within a predetermined time at a position in the optical arrangement that represents a final state of the universal non deterministic Turing Machine, this position is converted to that indication.