- #51

selfAdjoint

Staff Emeritus

Gold Member

Dearly Missed

- 6,852

- 9

Let us go back to the LEGO metaphor. It would be easy to build a computable LEGO universe following Kampis's instructions. For the set of all LEGO structures is countable, and may therefore be mapped into the set of binary sequences, in a one-to-one manner. And each binary sequence may be represented as a Turingmachine program, i.e. as a map from binary sequences to binary sequences. Therefore, using Turing machines, each LEGO structure could be interpreted as a function acting on other LEGO structures. The only problem with this arrangement is that it does not satisfy clause (c) of the definition of component-system. Not every LEGO structure is realizable by our dynamics. Only some computable subset of LEGO structures is realizable.

But now -- and here is where my thinking differs from Kampis's -- suppose one adds a random element to one's Turing machine. Suppose each component of the Turing machine is susceptible to errors! Then, in fact, every possible LEGO structure becomes realizable! Structures may have negligibly small probability, but never zero probability! This is an example of a component-system which is computable by a stochastic Turing machine.

I don't see that he

**shows**that a Turing machine with a stochastic component can generate all possible Lego configurations. Surely it can generate solutions that are not in the computable universe (at least, modulo some theorem that says a stochastic-modified Turing machine can't be modeled on a regular Turing machine)

but he hasn't shown the the universe of Lego constructions is contained in the universe of stochastic-Turing solutions, or even that they intersect. The stochastic solutions might all be malformed in Lego terms.

Kastin's Lego constructions remind me strongly of cellular automata, and I wonder if they might be modeled as such. There is apparently a large literatur on what cellular automata can achieve, and I can't resist referencing a new result: http://www.cscs.umich.edu/~crshalizi/weblog/375.html

Any way, very interesting, thanks for the link. BTW I found your other link on the sorites problem interesting too, although I don't know that the solution of the mathematical vague boundary problem solves the physical one.