[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.68,Default,,0000,0000,0000,,So the first statement here is obviously not true. We have not even talked about time.
Dialogue: 0,0:00:04.68,0:00:08.46,Default,,0000,0000,0000,,We have just pondered the existence of an algorithm for the halting problem
Dialogue: 0,0:00:08.46,0:00:13.18,Default,,0000,0000,0000,,or more specifically, the non-existence of such an algorithm, and that is exactly what we have shown.
Dialogue: 0,0:00:13.18,0:00:16.30,Default,,0000,0000,0000,,We have shown that there's no algorithm that solves the halting problem
Dialogue: 0,0:00:16.30,0:00:21.49,Default,,0000,0000,0000,,if we allow that algorithm to be given any program and any input, but of course,
Dialogue: 0,0:00:21.49,0:00:28.56,Default,,0000,0000,0000,,there are specific programs for which we can use algorithms to decide if they will go into loops or not
Dialogue: 0,0:00:28.56,0:00:32.51,Default,,0000,0000,0000,,and this is for example one technique that is used in automated software testing.
Dialogue: 0,0:00:32.51,0:00:36.26,Default,,0000,0000,0000,,It's not that there can be an algorithm that solves the halting problem
Dialogue: 0,0:00:36.26,0:00:42.39,Default,,0000,0000,0000,,for specific cases or specific programs, the halting problem cannot be solved for the general case.
Dialogue: 0,0:00:42.39,0:00:46.95,Default,,0000,0000,0000,,So if say you have an algorithm that can solve the halting problem for any program,
Dialogue: 0,0:00:46.95,0:00:51.70,Default,,0000,0000,0000,,any input that you throw at it, that cannot be the case, but for specific,
Dialogue: 0,0:00:51.70,9:59:59.99,Default,,0000,0000,0000,,special cases, we haven't shown anything so far.