say:

op op op op op |x>

So that motivates a short cut:

op^5 |x>

Let's give an example using a simple binary tree:

left |x> => |0> right |x> => |1> child |x> => |0> + |1> left |0> => |00> right |0> => |10> child |0> => |00> + |10> left |1> => |01> right |1> => |11> child |1> => |01> + |11> left |00> => |000> right |00> => |100> child |00> => |000> + |100> left |10> => |010> right |10> => |110> child |10> => |010> + |110> left |01> => |001> right |01> => |101> child |01> => |001> + |101> left |11> => |011> right |11> => |111> child |11> => |011> + |111>

Now, lets use it:

sa: child |x>

|0> + |1>

-- without using the notational short-cut:

sa: child child |x>

|00> + |10> + |01> + |11>

-- using it:

sa: child^2 |x>

|00> + |10> + |01> + |11>

sa: child^3 |x>

|000> + |100> + |010> + |110> + |001> + |101> + |011> + |111>

sa: child^4 |x>

|>

-- we are past the bottom of the tree!

Note that child^k only gives you horizontal slices through the tree.

What if you want a vertical component too?

We can do that.

First recall from maths: exp(x)

And that exp(x) has the Taylor Series:

exp(x) = 1 + x + x^2/2 + x^3/3! + x^4/4! + x^5/5! + ...

If we tidy that up (we don't need the n! denominators), we have:

exp[op,n] |x>

is equivalent to:

(1 + op + op^2 + op^3 + ... + op^n) |x>

eg:

-- equivalent to:

-- |x> + child |x> + child^2 |x>

sa: exp[child,2] |x>

|x> + |0> + |1> + |00> + |10> + |01> + |11>

sa: exp[child,3] |x>

|x> + |0> + |1> + |00> + |10> + |01> + |11> + |000> + |100> + |010> + |110> + |001> + |101> + |011> + |111>

sa: exp[child,2] |1>

|1> + |01> + |11> + |001> + |101> + |011> + |111>

sa: exp[left,2] |1>

|1> + |01> + |001>

Finally, what if you want everything, but you don't know how deep to go?

Hence:

exp-max[op] |x>

which is equivalent to:

exp[op,n] |x> such that exp[op,n] |x> == exp[op,n+1] |x>

eg:

sa: exp-max[child] |x>

|x> + |0> + |1> + |00> + |10> + |01> + |11> + |000> + |100> + |010> + |110> + |001> + |101> + |011> + |111>

sa: exp-max[child] |0>

|0> + |00> + |10> + |000> + |100> + |010> + |110>

Finally, the idea of "six degrees of separation"

If we had the data, then eg:

sa: friends^6 |Fred>

sa: exp[friends,6] |Fred>

sa: exp-max[friends] |Fred>

That's more than enough for now. More later!

Update: now with the magic of tables:

sa: load binary-tree-with-child.sw sa: table[node,child,text] exp-max[child] |x> +------+----------+-------------------+ | node | child | text | +------+----------+-------------------+ | x | 0, 1 | start node | | 0 | 00, 10 | first child node | | 1 | 01, 11 | second child node | | 00 | 000, 100 | third child node | | 10 | 010, 110 | fourth child node | | 01 | 001, 101 | fifth child node | | 11 | 011, 111 | sixth child node | | 000 | | | | 100 | | | | 010 | | | | 110 | | | | 001 | | | | 101 | | | | 011 | | | | 111 | | | +------+----------+-------------------+

## No comments:

## Post a Comment