WEBVTT

1
00:00:00.200 --> 00:00:06.173
Sometimes one reading is not enough, and each further test uses time or resources.

2
00:00:06.173 --> 00:00:11.860
We need a plan that works across possible answers, not just a promising next question.

3
00:00:11.860 --> 00:00:18.076
Our question plan changes as answers arrive, while the card's state stays fixed. We are

4
00:00:18.076 --> 00:00:21.400
learning about its Being; Becoming would change that state.

5
00:00:22.720 --> 00:00:24.340
Use the four cards again.

6
00:00:24.340 --> 00:00:32.200
The goal for the next worked example is to identify the complete card, using exact tests while it stays fixed.

7
00:00:32.200 --> 00:00:40.187
A reads colour, B shape, and the library also supplies the question “is this exactly that card?” for each card.

8
00:00:40.187 --> 00:00:43.060
We label this four-card example C4.

9
00:00:43.060 --> 00:00:47.980
Our earlier lamp machine is labeled M0 and has a different set of tests.

10
00:00:47.980 --> 00:00:50.160
Its test set has not changed.

11
00:00:50.870 --> 00:01:02.810
A decision tree is a plan for asking questions. One state is unknown but fixed. Each answer retains the states consistent with it; an informative answer makes that set smaller.

12
00:01:02.810 --> 00:01:08.750
Our four states are zero-zero, zero-one, one-zero and one-one.

13
00:01:08.750 --> 00:01:11.730
A reads the first digit; B reads the second.

14
00:01:11.730 --> 00:01:17.610
The library also contains a test for each individual card: is the state exactly this one?

15
00:01:17.610 --> 00:01:22.090
The current support is the set of states consistent with the answers so far.

16
00:01:22.090 --> 00:01:23.853
Ask A at the root.

17
00:01:23.853 --> 00:01:28.970
Answer zero leaves the first pair, and answer one leaves the second.

18
00:01:28.970 --> 00:01:34.884
Both branches belong in the plan, even though an actual run follows only one.

19
00:01:34.884 --> 00:01:37.171
Ask B on each remaining pair.

20
00:01:37.171 --> 00:01:44.624
On the A-zero branch, B zero identifies zero-zero, and B one identifies zero-one.

21
00:01:44.624 --> 00:01:51.891
On the A-one branch, B zero identifies one-zero, and B one identifies one-one.

22
00:01:51.891 --> 00:01:57.918
Every branch now ends in a singleton, a support containing exactly one state.

23
00:01:57.918 --> 00:02:00.062
That leaf identifies the state.

24
00:02:00.852 --> 00:02:05.108
The depth of a leaf is the number of questions on its path from the root.

25
00:02:05.108 --> 00:02:10.712
Here every leaf has depth two, so the worst-case depth is two.

26
00:02:10.712 --> 00:02:15.472
The tree has four leaves and three internal question nodes.

27
00:02:15.472 --> 00:02:19.305
We do not ask all three questions on one run.

28
00:02:19.305 --> 00:02:22.652
We follow one path, asking two.

29
00:02:22.652 --> 00:02:27.532
Distinguish the size of the entire plan from the number of questions used on a path.

30
00:02:28.322 --> 00:02:32.349
A plan can choose the next question from the answer already received.

31
00:02:32.349 --> 00:02:36.922
After A equals zero, ask whether the state is zero-zero.

32
00:02:36.922 --> 00:02:41.026
After A equals one, ask whether it is one-zero.

33
00:02:41.026 --> 00:02:44.834
Both branches still identify the state in two questions.

34
00:02:44.834 --> 00:02:46.962
That is adaptive choice.

35
00:02:46.962 --> 00:02:53.573
We specify a rule for each possible answer history, rather than promising to ask the same full sequence

36
00:02:53.573 --> 00:02:54.562
everywhere.

37
00:02:54.562 --> 00:02:58.429
A test may become uninformative on a smaller support.

38
00:02:58.429 --> 00:03:02.928
On the pair zero-zero and zero-one, A is constant.

39
00:03:02.928 --> 00:03:05.522
Asking it again produces no split.

40
00:03:06.392 --> 00:03:10.552
Available means a test belongs to the supplied library.

41
00:03:10.552 --> 00:03:16.525
Admissible means it also satisfies the rules at the current support and stage.

42
00:03:16.525 --> 00:03:22.765
For a simple separate rule, allow at most one yes-or-no question in total.

43
00:03:22.765 --> 00:03:26.065
A is available and legal as the first question.

44
00:03:26.065 --> 00:03:33.105
But no one-question plan can distinguish four states, because it has at most two answer leaves.

45
00:03:33.105 --> 00:03:40.372
Feasible means there exists a complete admissible plan meeting the goal on every possible branch.

46
00:03:40.372 --> 00:03:43.932
A legal next move alone does not prove feasibility.

47
00:03:44.722 --> 00:03:50.098
A specialist research branch studies restrictions that depend on the remaining possibilities.

48
00:03:50.098 --> 00:03:51.662
That is optional here.

49
00:03:51.662 --> 00:03:57.602
Our main route keeps the distinction between a permitted next question and a complete plan meeting its goal.

50
00:03:58.472 --> 00:04:00.972
Restore the unrestricted library.

51
00:04:00.972 --> 00:04:04.652
The two-question plan is feasible.

52
00:04:04.652 --> 00:04:09.392
A plan that checks individual states one at a time is also feasible,

53
00:04:09.392 --> 00:04:12.972
but its worst branch uses three questions.

54
00:04:12.972 --> 00:04:15.899
To say optimal, specify a cost.

55
00:04:15.899 --> 00:04:20.859
For worst-case question count, depth two is optimal here.

56
00:04:20.859 --> 00:04:26.572
One binary question has at most two leaves, so it cannot identify four states.

57
00:04:26.572 --> 00:04:31.659
We have exhibited a two-question solution, meeting that lower bound.

58
00:04:31.659 --> 00:04:36.038
Expected depth would additionally require a probability distribution.

59
00:04:36.038 --> 00:04:39.927
Structural constraints require their own admissibility check.

60
00:04:39.927 --> 00:04:46.103
Keep the library, rules, goal and cost visible whenever comparing strategies.

61
00:04:46.893 --> 00:04:50.127
The card tree worked because those queries were supplied.

62
00:04:50.127 --> 00:04:54.973
Return to M0 with only exact READ while the state stays fixed.

63
00:04:54.973 --> 00:05:05.333
Starting from u or v, can repeating READ reveal which predictive group applies?

64
00:05:05.333 --> 00:05:08.426
No. Both give zero on every such reading.

65
00:05:08.426 --> 00:05:13.040
If the goal is only to read the current lamp, zero already answers it.

66
00:05:13.040 --> 00:05:17.013
If the goal concerns the future after PULSE, more is needed.

67
00:05:17.013 --> 00:05:23.173
The next lesson allows actions and checks what they change, including the state being identified.