Alan Dix - research topics

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


Alan Dix 22/10/2002