Causality Theory

[michielbdejong]

https://en.wikipedia.org/wiki/Ergodicity

[michielbdejong]

https://en.wikipedia.org/wiki/Loschmidt%27s_paradox

[michielbdejong]

https://en.wikipedia.org/wiki/T-symmetry

[michielbdejong]

https://www.one-tab.com/page/Xlho7ZR4R0qlBYtqWTi3Nw

[michielbdejong]

Clocked registers observe streams of values that other registers go through, apply a function to that, and publish their own stream of values.
They can take observe and forget actions, triggered by their own value. So maybe that's procedural?

[michielbdejong]

The fact that observe and forget actions are triggered by (previous) state introduces the arrow of time.

[michielbdejong]

It's different from a Turing Machine because each clocked register is a Finite State Machine, but there is no tape.
Instead, the number of registers is unlimited. But that wou still make a Clocked Register Set equivalent to FSM. Maybe creating/removing a register should be an action too?

[michielbdejong]

Consider the problem of finding out whether the sum of a series of numbers equals its product. For instance:

1 + 2 + 1 + 3 + 1 + 2 + 1 + 1 = 12 = 1 * 2 * 1 * 3 * 1 * 2 * 1 * 1

Both sums and products are "decomposable" but to make them match, there is some communication needed between the subcomponents.

If a sub-series contains many ones, it favours the sum, and this should be counter-balanced by a series that favours the product.

[michielbdejong]

How can we quantify the amount of "entanglement" between components? Does the amount of information that a component needs to "guess" translate directly into computational complexity?

(a v b v c) ^ (!b v d v e) ^ (c v !a v e)

Ways to satisfy this, tree search:

• a !b c
• a !b e
• a d c
• a d e
• a e
• b d c
• b d !a
• b e
• c !b
• c d
• c e

Ways to satisfy this, table:

a	b	c	d	e	C1	C2	C3	EXPR
0	0	0	0	0	0	1	1	0
0	0	0	0	1	0	1	1	0
0	0	0	1	0	0	1	1	0
0	0	0	1	1	0	1	1	0
0	0	1	0	0	1	1	1	1
0	0	1	0	1	1	1	1	1
0	0	1	1	0	1	1	1	1
0	0	1	1	1	1	1	1	1
0	1	0	0	0	1	0	1	0
0	1	0	0	1	1	1	1	1
0	1	0	1	0	1	1	1	1
0	1	0	1	1	1	1	1	1
0	1	1	0	0	1	0	1	0
0	1	1	0	1	1	1	1	1
0	1	1	1	0	1	1	1	1
0	1	1	1	1	1	1	1	1
1	0	0	0	0	1	1	0	0
1	0	0	0	1	1	1	1	1
1	0	0	1	0	1	1	0	0
1	0	0	1	1	1	1	1	1
1	0	1	0	0	1	1	1	1
1	0	1	0	1	1	1	1	1
1	0	1	1	0	1	1	1	1
1	0	1	1	1	1	1	1	1
1	1	0	0	0	1	0	0	0
1	1	0	0	1	1	1	1	1
1	1	0	1	0	1	1	0	0
1	1	0	1	1	1	1	1	1
1	1	1	0	0	1	0	1	0
1	1	1	0	1	1	1	1	1
1	1	1	1	0	1	1	1	1
1	1	1	1	1	1	1	1	1

[michielbdejong]

The pattern created by the expression is quite complex because it is a "stack of masks" of the clauses. What does this look like in time-opposite direction?

[michielbdejong]

I think translating product-of-sums to sum-of-products is equivalent to translating sum-of-products to product-of-sums.
But to satisfy a product-of-sums expression is hard because masks with small windows stack up,
And to dis-satisfy a product-of-sums expression is easy because masks with large windows stack up,
Similarly dis-satisfying a sum-of-products would be hard and satisfying it would be easy.

[michielbdejong]

There are exponentially many "ways" to satisfy a set of clauses, if "way" is an exact valuation of a subset of the variables, like the 'tree search' list above. But does that also mean it takes exponential time to search them?

[michielbdejong]

There are exponential amounts of information involved in the relations between components of a problem instance. You could consider a solver as a single component, but then you would have to recognise its substructures until all the internal structure is accounted for. So the amount of internal structure of a problem instance / solver (as far as it can't be simplified) as a function of the problem instance input length defines the computational complexity of the problem.

[michielbdejong]

A single instance of a problem can be a lookup table. Same for a machine that can only handle limited input length.

Computational complexity arises when you define an ideal machine that can handle unlimited input length.

At the same time, that might be the key to defining possibility cut:

Define a sub-solver that can extract relevant conclusions but is robust to not knowing what the rest of the problem instance looks like.

The difficult part of modelling this is probably the relativity of how a problem instance can be sliced.

Before a problem is hard, it also needs to stay hard no matter how you reslice it. And within a slicing, each slice needs to extract useful conclusions without knowing the input values of the other slices.

So I need to model this slicing (and the relativity of reslicing) as well as this separation of information between the slices of a slicing.

[michielbdejong]

It's OK if a single problem instance can be resliced. As long as there is no reslicing strategy that helps in the worst case.