WEBVTT
00:00:00.000 --> 00:00:04.680
So the first statement here is obviously not true. We have not even talked about time.
00:00:04.680 --> 00:00:08.460
We have just pondered the existence of an algorithm for the halting problem
00:00:08.460 --> 00:00:13.180
or more specifically, the non-existence of such an algorithm, and that is exactly what we have shown.
00:00:13.180 --> 00:00:16.300
We have shown that there's no algorithm that solves the halting problem
00:00:16.300 --> 00:00:21.490
if we allow that algorithm to be given any program and any input, but of course,
00:00:21.490 --> 00:00:28.560
there are specific programs for which we can use algorithms to decide if they will go into loops or not
00:00:28.560 --> 00:00:32.509
and this is for example one technique that is used in automated software testing.
00:00:32.509 --> 00:00:36.260
It's not that there can be an algorithm that solves the halting problem
00:00:36.260 --> 00:00:42.390
for specific cases or specific programs, the halting problem cannot be solved for the general case.
00:00:42.390 --> 00:00:46.950
So if say you have an algorithm that can solve the halting problem for any program,
00:00:46.950 --> 00:00:51.700
any input that you throw at it, that cannot be the case, but for specific,
00:00:51.700 --> 99:59:59.999
special cases, we haven't shown anything so far.