Computers of today, which are enabled by technologies that use artificial intelligence, are capable of engaging in convincing discussions with people (thanks, ChatGPT), composing songs, painting artworks, playing chess and go, and diagnosing diseases, to name just a few examples of the technological prowess they possess.
These successes may be interpreted to suggest that there are no boundaries to what can be computed. It is essential to have an understanding of what factors contribute to the potency of a computer in order to determine whether or not this is the case.
A computer's power may be broken down into two categories: the number of operations its hardware is able to carry out in a single second and the effectiveness of the algorithms that it employs. The laws of physics place a cap on the maximum speed of the device. Humans are responsible for the writing of algorithms, which are essentially sets of instructions that are then translated into a sequence of operations that computer hardware may carry out. Even if the speed of a computer were to reach its physical limit, there would still be computational hurdles to overcome because of the limitations of algorithms.
These obstacles consist of difficulties that cannot be solved by computers and problems that can be solved in theory but cannot be solved in practise by even the most powerful versions of computers that are now available. Experiments are conducted on fictitious computers and mathematical models in order for mathematicians and computer scientists to determine whether or not a problem can be solved.
An Imaginary Computing Machine
Alan Turing, a British mathematician, is credited with developing the current concept of an algorithm in 1936. This concept is often referred to as a Turing machine. It is a fictitious machine that simulates the manner in which mathematical computations are performed using a pencil and paper. The Turing machine serves as the model from which all modern computers are constructed.
In order to handle computations that, if done manually, would require more paper, it is assumed that a Turing machine's supply of virtual paper is endless. This is done for the same reason. This is analogous to imagining an endless ribbon or "tape" of squares, where each square is either empty or contains one sign.
The machine is directed by a limited set of rules, and it commences operation by locating a predetermined pattern of symbols on the tape. The machine is capable of performing the actions of moving to an adjacent square, erasing a symbol, and writing a symbol on a square that is otherwise blank. The computation is performed by the machine by carrying out this series of steps in sequential order. The output or outcome of the machine is the symbols that are still there on the tape after it completes its work or "halts."
The field of computing frequently involves making choices with either yes or no possible responses. By way of comparison, a medical test is a sort of problem, and a patient's specimen is an instance of the problem. The test checks to see if the specimen contains a certain illness indication (with a yes or no result). The instance, which is the initial sequence of symbols, is what is represented in a Turing computer when it is in digital form.
A issue is said to be "solvable" if a Turing machine is able to stop for every instance of the problem, regardless of whether the instance is positive or negative, and properly decide which answer the problem produces.
There is not always a solution to a problem.
While a number of problems can be solved by using a Turing machine and, consequently, can be solved using a computer, there are also a number of problems that cannot be addressed using a computer. For instance, the domino problem, which is a subset of the tiling problem and was conceived of by the Chinese-American mathematician Hao Wang in the year 1961, cannot be solved.
The objective of this challenge is to fill a full grid with a set of dominoes while adhering to the guidelines of the majority of dominoes games and ensuring that the number of pips on the ends of adjacent dominoes are same. It has been discovered that there is no algorithm that can begin with a set of dominoes and identify whether or not the set will completely cover the grid. This discovery came as a bit of a surprise to many people.
Maintaining a Moderate Attitude
It is possible for algorithms that can complete their work in a fair amount of time to find solutions to a number of problems that can be solved. These so-called "polynomial-time algorithms" are examples of efficient algorithms, which means that it is feasible to make use of computers in order to solve instances of the problems they address.
Despite the continued extensive attempts to identify polynomial-time algorithms, there are thousands of other solvable problems that do not now have any known polynomial-time algorithms. Among these is something known as the "Travelling Salesman Problem."
‼️ Learn Artificial Intelligence (AI)
— Europe.study (@wwweuropestudy) February 12, 2023
✅ Free Online Courses
➡️ https://t.co/2uA6CnX4gM
The question posed by the Travelling Salesman Problem is whether or not a graph, which is a collection of points, including some points that are directly connected to one another, can have a path that begins at any place, travels to every other point precisely once, and then returns to the starting point. Imagine that a salesman needs to design a path that will take him through a neighbourhood exactly once while also allowing him to circle back to the place where he began.
Two different computer scientists, American Canadian Stephen Cook and Ukrainian American Leonid Levin, separately came up with the formulation for these problems, which are known as NP-complete, and demonstrated that they existed in the early 1970s. For his contribution to this field, Cook received the Turing Award in 1982, which is considered to be the field's most prestigious accolade.
The Price Paid for Precise Knowledge
The most well-known algorithms for NP-complete issues simply involve looking through all of the available solutions for a way to solve the problem. On a graph consisting of a few hundred points, running the Travelling Salesman Problem on a supercomputer might take years of time. Because of this, there are no mathematical short cuts available because the algorithms are inefficient.
Approximations are all that can be provided by practical algorithms that attempt to solve these problems in the actual world, despite the fact that these approximations are getting better. One of the seven millennium open issues that the Clay Mathematics Institute posed at the turn of the 21st century, each of which carried a prize of $1 million, was the question of whether or not there are efficient polynomial-time algorithms that can solve NP-complete problems.
Turing and Beyond
Could there be a new kind of computation that goes beyond the framework that Turing established? Richard Feynman, an American physicist who was awarded the Nobel Prize in Physics in 1982, was the first person to propose the concept of basing computers on quantum mechanics.
Peter Shor, an American applied mathematician, presented a quantum algorithm to factor integers in polynomial time in the year 1995. The algorithm was named after him. Mathematicians are of the opinion that this problem cannot be solved using algorithms that run in polynomial time under Turing's paradigm. Finding a smaller integer that is greater than one and can divide an integer is what it means to factor an integer. One illustration of this would be the fact that the integer 688,826,081 can be divided by the smaller integer 25,253, given that 688,826,081 = 25,253 x 27,277.
Related link : What Exactly Is CNC Machining, Anyway?
The computational difficulties of factoring large integers is the foundation of a significant algorithm known as the RSA algorithm. This technique is commonly employed in the process of protecting network communications. According to Shor's findings, should the concept of quantum computing ever become a reality, it will fundamentally alter the landscape of cybersecurity.
Is it possible to construct a fully functional quantum computer that could factor integers and solve other problems? There are scientists that hold the view that this is possible. One is now being developed by a number of scientific research teams all over the world, and some of these teams have actually constructed prototype quantum computers.
Nevertheless, just like with every other innovative technology that has come before it, problems with quantum computing will almost certainly emerge at some point and impose new boundaries.