I think we can define the states count for primes which is "n-1" but for other numbers the number of states is the sum of factors it is made out of.
For example 7 has 6 states, but 15 also has 6 states because it consists of division by 3 and 5 which are both primes and have 2+4=6 states.

We still can't define finding of primes, but we can say its a prime if it doesn't have less than "n-1" states to define it. This only needs to be proved and we have won a million dollars ( http://en.wikipedia.org/wiki/Clay_Mathematics_Institute#P_versus_NP )

Err.. could you a lil bit elaborate on this ?
This seems interesting
Probably there's a Turing machine for this problem

I uploaded the division by six with some explanations:
http://enos.itcollege.ee/~mkalme/PAHN/Automata/DivideBy6.svg

Freaky Automata.

I want to present you a small curiosity:

1. how does look an automaton determining "divisibility" by 0?
   
2. how does look an automaton, which determines divisibility by 1?
   

Yes, I know, It's slightly crazy, but we are "outta university now" as vid said, so we can think here.

Here is an answer:

1. 
   
   
   core of the code for this automaton:
   
   Code:

   ; Programming model of an automaton.
   ;
   State   Start,  Start,  Start,  NotAccept    

   Because there is no number divisible by 0, automaton doesn't accept any of the input strings.
   
   
   
2. 
   
   core of the code for this automaton:
   
   Code:

   ; Programming model of an automaton.
   ;
   State   Start,  S0_1,   S0_1,   EmptyLine
   State   S0_1,   S0_1,   S0_1,   Accept    

   Because every number is divisible by 1, automaton accepts any nonempty sequence of '0' and '1' chars.

Madis:
Your sentence is a supposition or You know any theorem saying this exactly?

Regards,
M.H.

[EDIT] Image was moved to another server. [/EDIT]

Yeah, my sentence is a supposition, but its based on relatively hard facts:

I just assumed logically from the fact that when 3*5*11=165 and 165 is divisable by 3 AND 5 AND 11 at the same time, you don't need to check the divisibility by 165 anymore.
I can't put out an appropriate theorem, but I think it has something to do with factorization.

Lets take the same example:
We have a number, lets say it is 165. It takes 164 states + start + accepting state (166 altogether) to make a brute-force automata.
But lets factorize it: 3, 5 and 11 are its factors. Now if we divide it by 3: 165/3=55, then divide this by 5: 55/5=11, then we know that it is divisable by 165 because 11/11=1 is divisible.

The automata can take the same approach by dividing the number in question to smaller parts: 165 can be tested against 11 and if it passes the test, then the remaining number MUST be divisable by 3 and 5. Next we try if it passes the "division by 5" test and finally "division by 3" test. If all of them pass, the number in question is divisable by 165.

Madis:

Your method has sense only if we can make k (where k is a number of different prime factors of number n) passes with whole input string.

You are trying to "chain" automata, but I want to make all process of determining divisibility in one pass.

Notice, that every automaton has an Alzheimer's disease , so it "doesn't remember" its past. All memory is contained in states. We can't go back.

Regards,
M.H.

Hmm, yeah - that's right - it means that you can only optimize the last 0s so the only shortcuts are divisions by 2/4/8/16 etc.
The 165 ends with a 1 so it can't be optimized and it has to be 166 states altogether. 166 on the other hand can be divided by 2 and 83 can already be done with 84 states with finally adding 1 state to determine the final division by 2.

PS. Without any more passes, there is a possibility to make k automates (k=number of factors we are dealing with) and make them step in parallel feeding them data in-time. The result is positive if ALL the machines are in the accepted state.

Parallel processing is very interesting. I think, that You suggest using NN here (one neural cell for every prime factor)?

Regards,
M.H.

Here is a schema for neural cell determinig if given (m+1)-bit binary number is divisible by 2:



There is one small problem with neural cells: they (in contradistinction to automata) process on binary sequences with fixed length.

But how does this work actually? Below you have a simple explanation expressed in mathematical terms (since there are many formulas whole text is written using LaTeX and attached as a one picture).



Regards,
M.H.

[EDIT] Image was moved to another server. [/EDIT]

i wouldn't call this as neurons - it is better to compare this with usual logical device, used in digital electronic.
except similar looking, neuron (real or model) should have more complex behavior: its working may change in time due to different complex conditions: frequency, durability, power. postsynaptic membrana has barrier level to start depolarisation, which may vary, repolarisation depends on ion pumps, which depends on ATP, ions spreading, hormons etc.
it is just terms correcting sure, both such automata and neurons are extremely interesting for modelling we have no leave them away . neurons are just more complex, and more interesting.
regards!

shoorick:

Yes, of course I agree with You, that real neural cells are dynamic and more complicated than my schemes. My drawings shows only mathematical models of neurons. But these models give us general idea of NN. It's better than nothing.

P.S. Are You biochemist?

Regards,
M.H.

Are You biochemist?
i have medical education (but no mathematical )

i was always interested in "reversing" some neural network (like of some very simple animals, for beginning), but peple need to know extremely lot, and it's not possible to learn it without getting lot of "overhead"

vid: it sounds very intriguing. Could You explain it to me?

S pozdravom,
M.H.

[EDIT] I guess, that You mean "reverse engineering" applied to animal brain

yup

yes, work of real neurons are really studied often on simple animals, some of them has fixed number of neurons (like gelmint Ascarida - about 120).
---

the difference i've been pointing is this: task you suggested to decide has fixed non-changed rule. Mathematical neurons are far from real, but they have main differences from usual logical shemes: it has to have variable level on enter, and have to change his work in time depending on previous incoming signals. in other words, neuron can be imitated with automata with memory. this is usable in systems to decide tasks where rules are unknown or hard to describe, or are changing in time - self-learning systems (like expert systems, but another technics)

regards!

got some interesting links on this?

i had not read about this from inet - from books only. i had a great book ("Stages of developing of intellect" in rus), but i gave it to my friend long ago... he is too far away now (in usa).
also i have a book by two czech and one german scientists about technic of study high neuro functions using electronic devices - i'll check it at home for proper name and post it here tomorrow.

i was wrong - Ascaris has 298 neurons http://www.wormbase.org/db/misc/paper?name=WBPaper00016470;class=Paper
found with google, just these keywords: neuron animal experiment
ascaris

how far is this research. do they understand how these 300-neuron "persnalities" work?

btw, i am looking forward how will theology look like some 400 years later when human brain is finally understood... probably not much like today