10.4. Unsolveable Problems¶
10.4.1. Unsolveable Problems¶
1 / 26
Settings
<<<>
Introduction
Even the best programmer sometimes writes a program that goes into an infinite loop.
Of course, when you run a program that has not stopped, you do not know for sure if it is just a slow program or a program in an infinite loop. After "enough time", you shut it down.
Even the best programmer sometimes writes a program that goes into an infinite loop.
Of course, when you run a program that has not stopped, you do not know for sure if it is just a slow program or a program in an infinite loop. After "enough time", you shut it down.
10.4.2. The Halting Problem is Unsolvable¶
1 / 19
Settings
<<<>
The Halting Problem Is Unsolvable
There might be intellectual appeal to knowing that there exists some function that cannot be computed by a computer program But does it really matter if no program can compute a "nonsense" function such as the one shown in Bin 4 of the figure?
There might be intellectual appeal to knowing that there exists some function that cannot be computed by a computer program But does it really matter if no program can compute a "nonsense" function such as the one shown in Bin 4 of the figure?
1
2
3
4
5
$x$
$f_1(x)$
1
1
2
1
3
1
4
1
5
1
6
1
$x$
$f_2(x)$
1
1
2
2
3
3
4
4
5
5
6
6
$x$
$f_3(x)$
1
7
2
9
3
11
4
13
5
15
6
17
$x$
$f_4(x)$
1
15
2
1
3
7
4
13
5
2
6
7
