There are tasks that a computer cannot solve and they are not as complicated as you think (movie)
In the video on the udiprod channel, the fascinating topic of the halting problem in the context of computing machines is discussed. The author begins by introducing machines A and C, which solve typical mathematical problems and play checkers. Although these are advanced machines, they have limitations when faced with problems they are not designed for. An example is presented where machine A cannot comprehend the state of a checkerboard, and machine C cannot calculate an arithmetic result. This leads to a discussion about the existence of machine H, which can analyze whether a machine halts or not. H is a theoretical machine that we might imagine building, but soon the author introduces the logical intricacies that challenge its existence.
The film presents how H attempts to resolve the output of machines A and C by using blueprints to analyze their functions. The author then describes a scenario involving a clever combination of a copying machine with a machine called the negator to demonstrate the paradox surrounding H's existence. Assuming that H always produces the correct output, the incorrect judgments of H lead to contradictions proving that H's existence is logically impossible.
The introduction of machine X, which takes its own blueprint as input, becomes the focal point of the analysis. The author constructs the blueprint of machine X using the negator and the copying machine, which initiates a series of tests to see if H can accurately evaluate the result of machine X based on its own blueprint. If H claims that X will not get stuck, it indeed gets stuck, leading to a troubling assertion that H does not operate according to the assumptions. Ultimately, the author creates an infinite sequence revealing the paradox, demonstrating that H, despite the theory, cannot be realized.
The video ultimately raises serious questions regarding the limitations of computational mathematics and the design of automated problem-solving. The introduction of H and the tests performed on machine X highlight many issues with the assumptions made in designing automatic decision-making processes. The author draws surprising conclusions and reflections on a topic that transcends the general context of computer calculations.
At the time of writing this article, the video on the udiprod channel has garnered 2,595,998 views and 78,541 likes. The topic of the halting problem certainly sparks a lot of curiosity and inspires further reflection on the boundaries of artificial intelligence and automation. For many viewers, it becomes clear that there are limitations that will not allow for complete automation of decision-making processes by machines.
Toggle timeline summary
-
Introduction about soda request.
-
Description of computing machines A and C.
-
Feeding A a checkers board and C an arithmetic question.
-
Blueprint of computing machine A explained.
-
Introduction of machine H that solves the halting problem.
-
Examples of H analyzing blueprints.
-
Discussion on the logical impossibility of building H.
-
Introducing the photocopying machine.
-
Creation of machine X that interacts with H.
-
X fed with its own blueprint leading to a contradiction.
-
Contradiction proving H cannot exist.
Transcription
Everybody here asked me if you wanted a soda Neptune silver and I blatantly said, Please butchered me. ibilityBut... I was right to give it to you. This is computing machine A. A solves problems in arithmetic. It receives a problem written on paper and it prints the answer. It always prints the right answer. Here's another computing machine C. C plays checkers. It receives the current state of the board and it prints how it would move one of the red pieces. C plays checkers so well, it will never lose a game. A and C are machines we can already build today and computers keep getting smarter and smarter. Will they eventually be able to do everything? Let's feed A with a board of checkers. A was not designed to handle this kind of input and when it tries to process it, it gets stuck. The same thing happens to C when fed with a question in arithmetic. Let's draw a blueprint of A. This blueprint is detailed down to the level of the logic circuits and it fully defines how A works. We are now finally ready to introduce a marvellous machine called H. H solves what is known as the halting problem. It can analyse the blueprint of another machine and determine which inputs are good for it and which will cause it to get stuck. It receives the blueprint of the machine to be tested and an input to test it with. Based on the blueprint, H simulates the given machine on the given input and then determines if it gets stuck or not. H solves the halting problem perfectly. It always prints the right answer. Here are two more examples with the blueprint of the checkers machine. H is a nice machine, but can we really build it? We'll now prove that its very existence is logically impossible. Let's assume that H does exist. We'll place it on this stand for reasons that will be made clear in a minute. Recall that we assume H solves the halting problem perfectly. It should always print the correct answer. We are about to put this to the test. This is a photocopying machine. It simply prints two copies of its input. We'll place it behind H. Here's another simple machine. We call this one the negator. When the negator receives the words not stuck, it gets stuck, and when it receives the words stuck, it does not get stuck. And it prints a smile. We'll place it in front of H. Let's wrap it all in a neat package we call the X machine. X has one input and one output. Let's draw its blueprint. As before, this blueprint fully defines X. What do you think will happen if we feed X with its own blueprint? Will it get stuck? Let's find out. P simply duplicates our input. H receives two copies of the blueprint of X. It should now determine what happens when X is fed with its own blueprint. Let's assume it says not stuck. N negates that and gets stuck. So feeding X with its own blueprint causes it to get stuck. But H said it wouldn't. H was wrong. Let's try again. This time, we'll assume H says stuck. X didn't get stuck. But H said it would. H was wrong again. But H is supposed to always be right. This is a contradiction proving H cannot exist. Let's try again. H is supposed to always be right. But H is wrong again. But H is supposed to always be wrong again. But H is supposed to always be right. But H is supposed to always be wrong again. But H is supposed to always be right.