Hypercomputation: Is it hyper over current? – By Aditya Abeysinghe

Hypercomputation is a theoretical concept researched to solve many problems that current machines are unable to solve. Most hardware, which provides a set of functions, have limitations such as the number of steps it could process, use of only computable input or the need for a set of instructions to provide an output. Hypercomputation is computing that does not limit to the obstacles in real-world computing.

Automata

An automaton is a self-operated machine that follows a set of inputs and process them or operates on a set of instructions. For example, a TV, PC, or a vehicle is an automaton. Different classes of automata can be seen. These differ on each other based on the computational power and the amount of memory they can hold. The most common classes are combinational logic, finite state machines, pushdown automata and Turing machines.

Combinational logic is the basic form of all automata. It represents a Boolean circuit, and the outputs are 0, 1 or a combination of both. The output of combinational logic is based on only its input. Therefore, they form the simpler circuit logic used in electronics. Combinational logic-based circuits do not store history of inputs or change of state. In contrast, a finite state machine stores states of inputs and uses state-based input processes to provide output. For example, most remote controllers and built-in controllers of electronic products are finite state machines. Remote controllers of a TV, Fan or Cooling machine use state to store when a certain button was used to increase the volume or control the temperature. The state stored is used when pressing the increase or decrease button to get the current volume or temperature and change it to the new value.

Pushdown automata differ from finite state machines as they use a stack to change the current state at each step. A pushdown automaton is thus able to use memory to store transitions making it powerful than a finite state machine. Since it uses a stack only the top element is read during each search for which transition to be made. Therefore, to update the transition to a new transition the top element must be popped. This causes a loss of stored data in the stack. Therefore, it is seldom useful for machines that require permanent memory storage. Turing machines overcome this memory drawback of pushdown automata by using a tape with infinite storage. The tape can be used to store and write data based on a machine’s finite state table. Therefore, it is more efficient, powerful and uses less storage to process more processes than other automata.

Computability

Computability is the ability to provide output based on input(s) using an algorithm. An algorithm is a set of steps or processes which process inputs to provide an output. For example, a simple algorithm would be a set of steps to determine whether a person is obese based on his/her weight. If the weight of a person is over a limit the person is obese else normal or underweight. According to the thesis by Turing and Church, only computable functions can be processed by a mechanical device such as a TV, a PC, or a smart phone. The basic definition of a computability function can be more formally described as a function which produce output after a “finite” number of steps or halts when met with an uncomputable event. Therefore, the limitation of all automata is that they can be used only with computable, i.e., finite functions.

Hypercomputation

Hypercomputation is computing beyond the limitations posed by Turing machines. Although hypercomputation is a theory and is rarely used for real-world applications, it could be made to process uncomputable functions. A common model used in hypercomputation is the “infinite step” model. Devices which are based on algorithms use a finite set of instructions to provide output. The infinite step model could use an infinite set of instructions to either provide output or process without halt. Other models that are used for hypercomputation also try to move away from limits of real-world machines such as the use of a set of algorithms defined by a user or produce an output in an infinite storage or time.

Image Courtesy: https://www.eni.com