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
Thread Post new topic Reply to topic
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 29 Aug 2006, 15:20
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 ) Very Happy
Post 29 Aug 2006, 15:20
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
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
Post 30 Aug 2006, 08:28
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 30 Aug 2006, 10:01
I uploaded the division by six with some explanations:
http://enos.itcollege.ee/~mkalme/PAHN/Automata/DivideBy6.svg
Post 30 Aug 2006, 10:01
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
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. Laughing Laughing

Here is an answer:

  1. Image

    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. Image
    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:
Madis731 wrote:
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
Post 30 Aug 2006, 12:12
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 30 Aug 2006, 12:55
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.
Post 30 Aug 2006, 12:55
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6108
Location: Poland
MHajduk 30 Aug 2006, 13:24
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 Very Happy, so it "doesn't remember" its past. All memory is contained in states. We can't go back.

Regards,
M.H.
Post 30 Aug 2006, 13:24
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Madis731 30 Aug 2006, 13:34
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.
Post 30 Aug 2006, 13:34
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
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)? Wink

Regards,
M.H.
Post 30 Aug 2006, 14:23
View user's profile Send private message Visit poster's website Reply with quote
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:

Image

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).

Image

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
Post 30 Aug 2006, 15:30
View user's profile Send private message Visit poster's website Reply with quote
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 Smile sure, both such automata and neurons are extremely interesting for modelling we have no leave them away Wink. neurons are just more complex, and more interesting.
regards!
Post 31 Aug 2006, 06:21
View user's profile Send private message Visit poster's website Reply with quote
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. Smile

P.S. Are You biochemist?

Regards,
M.H.
Post 31 Aug 2006, 18:25
View user's profile Send private message Visit poster's website Reply with quote
shoorick



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

_________________
UNICODE forever!
Post 01 Sep 2006, 04:46
View user's profile Send private message Visit poster's website Reply with quote
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" Smile
Post 01 Sep 2006, 14:10
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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 Question
Post 01 Sep 2006, 14:38
View user's profile Send private message Visit poster's website Reply with quote
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
Post 02 Sep 2006, 09:38
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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!
Post 04 Sep 2006, 05:13
View user's profile Send private message Visit poster's website Reply with quote
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?
Post 04 Sep 2006, 06:37
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
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.
Post 04 Sep 2006, 12:52
View user's profile Send private message Visit poster's website Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1613
Location: Ukraine
shoorick 04 Sep 2006, 13:12
i was wrong - Ascaris has 298 neurons Smile http://www.wormbase.org/db/misc/paper?name=WBPaper00016470;class=Paper
found with google, just these keywords: neuron animal experiment
ascaris
Post 04 Sep 2006, 13:12
View user's profile Send private message Visit poster's website Reply with quote
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
Post 04 Sep 2006, 14:13
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3, 4  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2023, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.