flat assembler
Message board for the users of flat assembler.

 Index > DOS > Finite Automata in FASM Goto page Previous  1, 2, 3, 4  Next
Author

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
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 )
29 Aug 2006, 15:20
TmX

Joined: 02 Mar 2006
Posts: 839
Location: Jakarta, Indonesia
TmX 30 Aug 2006, 08:28
Quote:
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.

Err.. could you a lil bit elaborate on this ?
This seems interesting
Probably there's a Turing machine for this problem
30 Aug 2006, 08:28

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
I uploaded the division by six with some explanations:
http://enos.itcollege.ee/~mkalme/PAHN/Automata/DivideBy6.svg
30 Aug 2006, 10:01
MHajduk

Joined: 30 Mar 2006
Posts: 6108
Location: Poland
MHajduk 30 Aug 2006, 12:12
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.

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.

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.
Your sentence is a supposition or You know any theorem saying this exactly?

Regards,
M.H.

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

Last edited by MHajduk on 21 Oct 2010, 20:30; edited 2 times in total
30 Aug 2006, 12:12

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
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.
30 Aug 2006, 12:55
MHajduk

Joined: 30 Mar 2006
Posts: 6108
Location: Poland
MHajduk 30 Aug 2006, 13:24

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.
30 Aug 2006, 13:24

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
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.
30 Aug 2006, 13:34
MHajduk

Joined: 30 Mar 2006
Posts: 6108
Location: Poland
MHajduk 30 Aug 2006, 14:23
Parallel processing is very interesting. I think, that You suggest using NN here (one neural cell for every prime factor)?

Regards,
M.H.
30 Aug 2006, 14:23
MHajduk

Joined: 30 Mar 2006
Posts: 6108
Location: Poland
MHajduk 30 Aug 2006, 15:30
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]

Last edited by MHajduk on 25 Oct 2010, 22:39; edited 4 times in total
30 Aug 2006, 15:30
shoorick

Joined: 25 Feb 2005
Posts: 1613
Location: Ukraine
shoorick 31 Aug 2006, 06:21
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!
31 Aug 2006, 06:21
MHajduk

Joined: 30 Mar 2006
Posts: 6108
Location: Poland
MHajduk 31 Aug 2006, 18:25
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.
31 Aug 2006, 18:25
shoorick

Joined: 25 Feb 2005
Posts: 1613
Location: Ukraine
shoorick 01 Sep 2006, 04:46
Are You biochemist?
i have medical education (but no mathematical )

_________________
UNICODE forever!
01 Sep 2006, 04:46
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 01 Sep 2006, 14:10
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"
01 Sep 2006, 14:10
MHajduk

Joined: 30 Mar 2006
Posts: 6108
Location: Poland
MHajduk 01 Sep 2006, 14:38
vid:
vid wrote:
"reversing" some neural network
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
01 Sep 2006, 14:38
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 02 Sep 2006, 09:38
Quote:
I guess, that You mean "reverse engineering" applied to animal brain

yup
02 Sep 2006, 09:38
shoorick

Joined: 25 Feb 2005
Posts: 1613
Location: Ukraine
shoorick 04 Sep 2006, 05:13
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!
04 Sep 2006, 05:13
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 04 Sep 2006, 06:37
Quote:
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).

got some interesting links on this?
04 Sep 2006, 06:37
shoorick

Joined: 25 Feb 2005
Posts: 1613
Location: Ukraine
shoorick 04 Sep 2006, 12:52
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.
04 Sep 2006, 12:52
shoorick

Joined: 25 Feb 2005
Posts: 1613
Location: Ukraine
shoorick 04 Sep 2006, 13:12
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
04 Sep 2006, 13:12
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 04 Sep 2006, 14:13
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
04 Sep 2006, 14:13
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2, 3, 4  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum