Well a random network isn't necessary, a Turing machine suffices-that's what's meant by the statement that it is universal. The mathematical proof was provided by Turing. 

.

not sure what you mean by "behavior generating network" but maybe you are referring to Ramsey-type theorems ?

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

.

Dear James,

I believe your question is too complicated to be easily understood (at least by me). You might want to consider adding some more details to it.

However, I would like to point out that a non-random behavior in one space might seem as a random event in a different space and vise versa. It all depends on the angle by which you are looking at the problem area. I would like to point at chaos theory and its applications in fields such as control, as an example for what I mean.

Best regards

Peyman

Dear Friends

Thank you for your thought-provoking answers to my question.

>>> Stam – Yes, TMs can do anything (roughly) but my question is about seemingly random networks (ie graphs) – partly motivated by the apparent randomness of the human cerebral cortex. So you might reformulate my question as “Can it be PROVED that for any specific TM there is a seemingly random network that is equivalent to it?

>>> Fabrice -- I have glanced at Ramsey-Theory and believe it is both somewhat relevant (maybe more than somewhat) and interesting! Thank you! I will look in more detail – but there are so many other things that are interesting too!

>>> Peyman --. I agree that that randomness depends on point of view which is why I spoke of a standard test of randomness of a network (Is there one?). Obviously we can invent one! (cf tests for randomness of pseudo-random numbers).

REMEMBER I am looking for a mathematical PROOF, not just an opinion

It seems to me that a possible proof plan is: (i) point out that it is by assumption possible to design a network N (so non-random) to do the specified job (e.g. an artificial neural network to control a driverless automobile) (2) then show always possible to add many, many NON-FUNCTIONAL “INERT” nodes and connections C to the network, and then (3) show that a test of network randomness will find the whole N+C to be random.  Hence proof.

But I don’t like this plan much, and should one be focussing on a STANDARD test of randomness or on ALL tests of randomness?

Can anyone help further?

Best

Jim

.

Martin-Löf definition of randomness boils down to passing through all randomness tests

warning : "boils down" means "a lot of handwaving here" ! for a rigorous treatment :

http://www.scholarpedia.org/article/Algorithmic_randomness

.

Dear James,

you said above "...but my question is about seemingly random networks (ie graphs) – partly motivated by the apparent randomness of the human cerebral cortex."  I think the words "apparent randomness" are missplaced. I am convinced that any cerebral cortex is not working in a random way. Even if you admit that it looks like random, I don't understand the motivation behind your question to find a mathematical proof that the cerebral cortex network is random.

I know it is not an answer to your question, but an interesting topic anyway and a bit philosophical.

Regards,

Wolfram

Colleagues

>> Fabrice -- OK I need to explore the Martin-Lof definition. However, at this moment I find the concept of “all statistical tests of network randomness” hard to define precisely or take seriously.

>> Wolfram -- No, I am not trying to prove that the cerebral cortex is randomly organised! But I do not doubt that it is to some degree randomly grown.

My motivation for looking at this potential theorem is that designing complex systems often seems to involve creating subsystems or substructures that are substantially randomly specified e.g. when setting up an Artificial Society.

It seems that a behaviour B can be obtained EITHER by designing a network to do B, OR by setting up a random network and then “tuning” it to do B.

NOTE -- I have not forgotten that a process that generates a network at random, may by chance (a very small chance) generate a network that is actually not at all random!

Best

Jim

PS Does anyone have an opinion about the proof plan I gave in my previous answer?

Dear James,

I think one should limit the problem space so that all the conditions can be visualized.

Unrepeatable pattern or behavior in the problem space is a good sign for the randomness.

I suggest a limited problem area to start with.

Regards

Peyman

.

i'm still quite unsure of what you're looking for but your last post reminded me of the Highly Optimized Tolerance (HOT) concept, an approach of designed complex systems pioneered by Carlson and Doyle a few years ago

i have not followed that too closely but you could start here :

http://web.physics.ucsb.edu/~complex/research/robustness.htm

http://web.physics.ucsb.edu/~complex/research/hot.htm

.

Hi!

Thanks for further helpful answers -- but clearly my line of thought is not getting across!

I will try to fill out my proof plan a bit which should make things clearer. This will include being precise about (i) what I mean by a network and its I/O behavior, and (ii) what I mean by a statistical test of randomness for the connectivity of  a network .

An obvious problem in the proposed proof is WHICH test of randomness is it to refer to -- there are surely many  tests  that can be specified with some plausibility. (non-randomness corresponding to extreme value(s) of some suitable numerical function of connectivity).

Watch this space!

Best

Jim

Dear colleagues!

As promised, some jottings to elaborate the questionable proof plan (see my earlier post)

THE CONJECTURE TO BE PROVED OR REJECTED

Any MM-network N can be modified to N* in such a way that its I/O behaviour is unchanged and N* passes the test of network randomness MM-T.

DEFINITION OF A MM-NETWORK

An MM-Network is comprises:

A set of nodes,

Set of arcs (each arc an ordered pair of nodes),

Set of mappings, (one for each outgoing arc of each node, from current node input value sets to output values),

Execution process, (all nodes execute repeatedly and in lock step, computing the output values they transmit according to the mappings).

DEFINITION OF TEST OF NETWORK RANDOMNESS, MM-T

MM_T can be a two-tailed significance test as follows:

For any particular MM-Network we can calculate the number of nodes in it with NO outgoing arcs – call this integer DE (for dead ends)

By random generation on a computer of a large sample of networks (easy!) or formal analysis (hard!) we can obtain the frequency distribution of DE. Intuitively extreme values of DE correspond to structural non-randomness (is this acceptable?) hence we get a two-tailed significance test of the null hypothesis of random generation (just of structure – nothing to do with the mappings).

MODIFICATION OF MM-NETWORK TO PASS TEST MM-T

As appropriate:

EITHER if too few dead-end nodes repeatedly add a new dead-end node by adding a new outgoing arc leading to a new dead-end node from an existing non-dead-end node

OR if too many dead-end nodes repeatedly eliminate dead end nodes by adding a new outgoing arc from an existing dead-end node to a second existing dead-end node

UNTIL network passes test and so can be declared “random” or “seemingly random”, the phrase used in my original question.

I/O behaviour will be unchanged because no outputs are changed by the modifications made.

What do you think? Progress?

Cheers

Jim