» » » » Computer science – Computability

Computer science – Computability

posted in: Computers 0

Computability

Computer science is a field of scientific, technical and industrial for the automatic processing of information through the execution of computer programs by machines: embedded systems, computers, robots, controllers, etc.

These scopes can be separated into two branches, one theoretical in nature, concerning the definition of concepts and models, and the other of a practical nature, which focuses on practical techniques of implantation and implementation on the ground. Some areas of computing can be very abstract, such as algorithmic complexity, and others may be closer to a lay audience. Thus, languages remains a theory more accessible to professionals trained field (description of computers and programming methods), while occupations related to human-machine interfaces are accessible to a wider audience.

Computability

An algorithm is a systematic way to compute a result. A classic example is the Euclidean algorithm for the computing of the “Greatest common divisor”, which dates back at least to 300 BC., but it is already a complex calculation. Before that, the mere use of an abacus requested to have thought about a systematic (and correct) way to use this tool to perform arithmetic operations.

Algorithms therefore exist since ancient times, but it is only since the 1930s, with the beginnings of the theory of computability, which scientists have asked the questions “what is a calculation model?” And “do everything is computable?” and tried to respond formally.

There are many models of computation, but the main two are the “Turing machine” and “lambda calculus.” Both formal systems define objects that can represent so-called computational procedures, algorithms or programs. They then define a systematic way of applying these procedures, that is to say, to calculate.

The most important result of computability is probably Church’s thesis, which posits that all computer models have the same power. That is to say that there is no procedure that could be expressed in a model but not in another.

A second fundamental result is the existence of countless functions, a function being what computes a procedure or algorithm (these designating rather how to do the calculus). It can be shown that there are well defined functions for which there is no procedure to calculate. The best known example probably being the halting problem, which shows that no algorithm can exist which will always correctly decide whether, for a given arbitrary program and its input, the program halts when run with that input; the essence of Turing’s proof is that any such algorithm can be made to contradict itself, and therefore cannot be correct.

According to the Church-Turing thesis, all the computing models are equivalent, so this result is also applicable to other models, including programs and software that can be found in current computers. There is a strong link between the functions that we can not calculate and problems that we can not decide.

Leave a Reply

Your email address will not be published. Required fields are marked *