What does arbitrary number mean?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ?
My attempt :
Arbitrary length means variable length, and there is no DFA to recognize arbitrary length number, since we need memory to store the number.
Does arbitrary number means (may be) number having infinite digits?
Somewhere, it's given FSM for "add two binary numbers of infinite length by the following FSM".
Can you please explain?
number-theory discrete-mathematics formal-languages automata regular-language
asked Dec 5 '15 at 13:07
Mithlesh Upadhyay
2,94282355
add a comment |Â
up vote
2
down vote
favorite
A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ?
My attempt :
Arbitrary length means variable length, and there is no DFA to recognize arbitrary length number, since we need memory to store the number.
Does arbitrary number means (may be) number having infinite digits?
Somewhere, it's given FSM for "add two binary numbers of infinite length by the following FSM".
Can you please explain?
number-theory discrete-mathematics formal-languages automata regular-language
asked Dec 5 '15 at 13:07
Mithlesh Upadhyay
2,94282355
6
No, an integer must have a finite number of digits. "Arbitrary" here means that there is no limit to the number of digits; so, for instance, an FSM that can only add integers up to 1000 digits long does not qualify. Most FSMs have an infinite storage capacity, so memory is not a problem
– TonyK
Dec 5 '15 at 13:17
1
The FSM in the diagram never halts, so in a sense it can't compute anything at all!
– TonyK
Dec 5 '15 at 14:15
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ?
My attempt :
Arbitrary length means variable length, and there is no DFA to recognize arbitrary length number, since we need memory to store the number.
Does arbitrary number means (may be) number having infinite digits?
Somewhere, it's given FSM for "add two binary numbers of infinite length by the following FSM".
Can you please explain?
number-theory discrete-mathematics formal-languages automata regular-language
asked Dec 5 '15 at 13:07
Mithlesh Upadhyay
2,94282355
A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ?
My attempt :
Arbitrary length means variable length, and there is no DFA to recognize arbitrary length number, since we need memory to store the number.
Does arbitrary number means (may be) number having infinite digits?
Somewhere, it's given FSM for "add two binary numbers of infinite length by the following FSM".
Can you please explain?
number-theory discrete-mathematics formal-languages automata regular-language
asked Dec 5 '15 at 13:07
Mithlesh Upadhyay
2,94282355
edited Aug 16 at 10:19
asked Dec 5 '15 at 13:07
Mithlesh Upadhyay
2,94282355
asked Dec 5 '15 at 13:07
Mithlesh Upadhyay
2,94282355
asked Dec 5 '15 at 13:07
Mithlesh Upadhyay
2,94282355
2,94282355
6
No, an integer must have a finite number of digits. "Arbitrary" here means that there is no limit to the number of digits; so, for instance, an FSM that can only add integers up to 1000 digits long does not qualify. Most FSMs have an infinite storage capacity, so memory is not a problem
– TonyK
Dec 5 '15 at 13:17
1
The FSM in the diagram never halts, so in a sense it can't compute anything at all!
– TonyK
Dec 5 '15 at 14:15
add a comment |Â
6
No, an integer must have a finite number of digits. "Arbitrary" here means that there is no limit to the number of digits; so, for instance, an FSM that can only add integers up to 1000 digits long does not qualify. Most FSMs have an infinite storage capacity, so memory is not a problem
– TonyK
Dec 5 '15 at 13:17
1
The FSM in the diagram never halts, so in a sense it can't compute anything at all!
– TonyK
Dec 5 '15 at 14:15
6
6
No, an integer must have a finite number of digits. "Arbitrary" here means that there is no limit to the number of digits; so, for instance, an FSM that can only add integers up to 1000 digits long does not qualify. Most FSMs have an infinite storage capacity, so memory is not a problem
– TonyK
Dec 5 '15 at 13:17
No, an integer must have a finite number of digits. "Arbitrary" here means that there is no limit to the number of digits; so, for instance, an FSM that can only add integers up to 1000 digits long does not qualify. Most FSMs have an infinite storage capacity, so memory is not a problem
– TonyK
Dec 5 '15 at 13:17
1
1
The FSM in the diagram never halts, so in a sense it can't compute anything at all!
– TonyK
Dec 5 '15 at 14:15
The FSM in the diagram never halts, so in a sense it can't compute anything at all!
– TonyK
Dec 5 '15 at 14:15
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Arbitrary means arbitrary. That means that we put no restrictions on the number, but still each number is finite and has finite length.
This means that we a priori can't assume that it has less than, say $1234$ digits. All we can know is that if we start in one end it and step through we will eventually reach the other end.
Whether you can add them by a FSM depends on the requirement of input and outputs. If for example the numbers are fed into the FSM serially starting at LSD and the output is supposed to be fed out from the FSM serially starting at LSD you can certainly do it. It's the same algorithm you used when doing it by pen and paper - the only state you'll need is the carry.
answered Jan 19 '16 at 13:58
skyking
14.3k1829
1
Yes, thanks for explanation.
– Mithlesh Upadhyay
Jan 19 '16 at 14:01
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Arbitrary means arbitrary. That means that we put no restrictions on the number, but still each number is finite and has finite length.
This means that we a priori can't assume that it has less than, say $1234$ digits. All we can know is that if we start in one end it and step through we will eventually reach the other end.
Whether you can add them by a FSM depends on the requirement of input and outputs. If for example the numbers are fed into the FSM serially starting at LSD and the output is supposed to be fed out from the FSM serially starting at LSD you can certainly do it. It's the same algorithm you used when doing it by pen and paper - the only state you'll need is the carry.
answered Jan 19 '16 at 13:58
skyking
14.3k1829
1
Yes, thanks for explanation.
– Mithlesh Upadhyay
Jan 19 '16 at 14:01
add a comment |Â
up vote
2
down vote
accepted
Arbitrary means arbitrary. That means that we put no restrictions on the number, but still each number is finite and has finite length.
This means that we a priori can't assume that it has less than, say $1234$ digits. All we can know is that if we start in one end it and step through we will eventually reach the other end.
Whether you can add them by a FSM depends on the requirement of input and outputs. If for example the numbers are fed into the FSM serially starting at LSD and the output is supposed to be fed out from the FSM serially starting at LSD you can certainly do it. It's the same algorithm you used when doing it by pen and paper - the only state you'll need is the carry.
answered Jan 19 '16 at 13:58
skyking
14.3k1829
1
Yes, thanks for explanation.
– Mithlesh Upadhyay
Jan 19 '16 at 14:01
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Arbitrary means arbitrary. That means that we put no restrictions on the number, but still each number is finite and has finite length.
This means that we a priori can't assume that it has less than, say $1234$ digits. All we can know is that if we start in one end it and step through we will eventually reach the other end.
Whether you can add them by a FSM depends on the requirement of input and outputs. If for example the numbers are fed into the FSM serially starting at LSD and the output is supposed to be fed out from the FSM serially starting at LSD you can certainly do it. It's the same algorithm you used when doing it by pen and paper - the only state you'll need is the carry.
answered Jan 19 '16 at 13:58
skyking
14.3k1829
Arbitrary means arbitrary. That means that we put no restrictions on the number, but still each number is finite and has finite length.
This means that we a priori can't assume that it has less than, say $1234$ digits. All we can know is that if we start in one end it and step through we will eventually reach the other end.
Whether you can add them by a FSM depends on the requirement of input and outputs. If for example the numbers are fed into the FSM serially starting at LSD and the output is supposed to be fed out from the FSM serially starting at LSD you can certainly do it. It's the same algorithm you used when doing it by pen and paper - the only state you'll need is the carry.
answered Jan 19 '16 at 13:58
skyking
14.3k1829
answered Jan 19 '16 at 13:58
skyking
14.3k1829
answered Jan 19 '16 at 13:58
skyking
14.3k1829
answered Jan 19 '16 at 13:58
skyking
14.3k1829
14.3k1829
1
Yes, thanks for explanation.
– Mithlesh Upadhyay
Jan 19 '16 at 14:01
add a comment |Â
1
Yes, thanks for explanation.
– Mithlesh Upadhyay
Jan 19 '16 at 14:01
1
1
Yes, thanks for explanation.
– Mithlesh Upadhyay
Jan 19 '16 at 14:01
Yes, thanks for explanation.
– Mithlesh Upadhyay
Jan 19 '16 at 14:01
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1560931%2fwhat-does-arbitrary-number-mean%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
6
No, an integer must have a finite number of digits. "Arbitrary" here means that there is no limit to the number of digits; so, for instance, an FSM that can only add integers up to 1000 digits long does not qualify. Most FSMs have an infinite storage capacity, so memory is not a problem
– TonyK
Dec 5 '15 at 13:17
1
The FSM in the diagram never halts, so in a sense it can't compute anything at all!
– TonyK
Dec 5 '15 at 14:15