# embodied computation

placeholder page - just notes - to be completed ...

## roots

socio-organisational church turing
hypouthesis

mobile and ubiquitous

cellular automata

computing power of evolution

## fundamentals

finite processing and unbounded computation

### location

move computation to data

e.g. Turing machine

### replication

lots of communicating computation

e.g. cellular autromata

### ram

move data to computation

e.g. traditional computer

### oracle!

magically tell computers

e.g. Kohonen net and ART

## real memory

### pointers have size

dutch national flag problem

sorting oracles and informnation

### memory takes space

cube root N access

but concurrency -> sqrt N (3D), 2/3 root
(2D)

but always O(N) slower 1D without program
caching

## problem complexity

### what is computation?

### compexity theory?

complexity of algorithms and gross complexity
of problems

### sorting

#### virtually sole example

information theoretic argument

#### for biggest r?

N logR - prove it?

biggest 1 - information -> logN

why not N-1?

### which questions to ask?

weighing oracle

N-1 tests for sorted

### perfect sorting oracle

O(N) sort?

put ... pointers have size! => O(NlogN)
info

### sorting finite domains

O(NlogD) count and bucket sort

### links to Galois theory?

## representation not information

represention =

location –
where is information

+

comprehension
– who understands information

examples ...

sorting comparisons

FFT multiplication - properties!

control unit and arithmetic logical unit