Mixing
![Linear differential form as vector [on hold]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Turing Machine that orders the alphabet/characters of the entered string based on the frequency of each symbol
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Give the following problem:
Design a Turing Machine such that given string from the alphabet $a, b, c, d$, produces on the tape a combination of the string "abcd" in which each symbol occupies the position coresponding to the relative order of it's absolute frequency in the entered/given string. The combination is to be displayed in descending order. In the case of coinciding frequencies, the symbols are to be located in inversed order of appearance en the entry string. For example, the string $underlinetriangle a b a d c d a b c a a triangle triangle ...$ must produce the output $underlinetriangle a c d b triangle triangle ...$
Note:
The $triangle$ represents an "empty" character and _ the position of the reading head.
I have not encountered any problems related to this so I am not sure to proceed.
But if I am correct, I would need to use the counting Turing Machine and possibly a programming technique such as multiple tapes. Would that be necessary?
How do I go about designing such a machine?
turing-machines
asked Aug 2 at 12:33
Omari Celestine
602110
add a comment |Â
up vote
1
down vote
favorite
Give the following problem:
Design a Turing Machine such that given string from the alphabet $a, b, c, d$, produces on the tape a combination of the string "abcd" in which each symbol occupies the position coresponding to the relative order of it's absolute frequency in the entered/given string. The combination is to be displayed in descending order. In the case of coinciding frequencies, the symbols are to be located in inversed order of appearance en the entry string. For example, the string $underlinetriangle a b a d c d a b c a a triangle triangle ...$ must produce the output $underlinetriangle a c d b triangle triangle ...$
Note:
The $triangle$ represents an "empty" character and _ the position of the reading head.
I have not encountered any problems related to this so I am not sure to proceed.
But if I am correct, I would need to use the counting Turing Machine and possibly a programming technique such as multiple tapes. Would that be necessary?
How do I go about designing such a machine?
turing-machines
asked Aug 2 at 12:33
Omari Celestine
602110
Does $triangle$ denote a fifth letter of your Turing machine's alphabet (an "empty" character, or a zero, if you will)? And does $underlinephantomtriangle$ mean that's where the reading head is? Also, multiple tapes is never necessary (it doesn't make a Turing machine more complete), but not having to worry about different countings being in the way of one another is definitely a plus.
– Arthur
Aug 2 at 12:49
@arthur Sorry for lack of those details. The $triangle$ represents an "empty" character and _ the position of the reading head. I will update the question to include this.
– Omari Celestine
Aug 2 at 12:53
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Give the following problem:
Design a Turing Machine such that given string from the alphabet $a, b, c, d$, produces on the tape a combination of the string "abcd" in which each symbol occupies the position coresponding to the relative order of it's absolute frequency in the entered/given string. The combination is to be displayed in descending order. In the case of coinciding frequencies, the symbols are to be located in inversed order of appearance en the entry string. For example, the string $underlinetriangle a b a d c d a b c a a triangle triangle ...$ must produce the output $underlinetriangle a c d b triangle triangle ...$
Note:
The $triangle$ represents an "empty" character and _ the position of the reading head.
I have not encountered any problems related to this so I am not sure to proceed.
But if I am correct, I would need to use the counting Turing Machine and possibly a programming technique such as multiple tapes. Would that be necessary?
How do I go about designing such a machine?
turing-machines
asked Aug 2 at 12:33
Omari Celestine
602110
Give the following problem:
Design a Turing Machine such that given string from the alphabet $a, b, c, d$, produces on the tape a combination of the string "abcd" in which each symbol occupies the position coresponding to the relative order of it's absolute frequency in the entered/given string. The combination is to be displayed in descending order. In the case of coinciding frequencies, the symbols are to be located in inversed order of appearance en the entry string. For example, the string $underlinetriangle a b a d c d a b c a a triangle triangle ...$ must produce the output $underlinetriangle a c d b triangle triangle ...$
Note:
The $triangle$ represents an "empty" character and _ the position of the reading head.
I have not encountered any problems related to this so I am not sure to proceed.
But if I am correct, I would need to use the counting Turing Machine and possibly a programming technique such as multiple tapes. Would that be necessary?
How do I go about designing such a machine?
turing-machines
asked Aug 2 at 12:33
Omari Celestine
602110
edited 2 hours ago
asked Aug 2 at 12:33
Omari Celestine
602110
asked Aug 2 at 12:33
Omari Celestine
602110
asked Aug 2 at 12:33
Omari Celestine
602110
602110
Does $triangle$ denote a fifth letter of your Turing machine's alphabet (an "empty" character, or a zero, if you will)? And does $underlinephantomtriangle$ mean that's where the reading head is? Also, multiple tapes is never necessary (it doesn't make a Turing machine more complete), but not having to worry about different countings being in the way of one another is definitely a plus.
– Arthur
Aug 2 at 12:49
@arthur Sorry for lack of those details. The $triangle$ represents an "empty" character and _ the position of the reading head. I will update the question to include this.
– Omari Celestine
Aug 2 at 12:53
add a comment |Â
Does $triangle$ denote a fifth letter of your Turing machine's alphabet (an "empty" character, or a zero, if you will)? And does $underlinephantomtriangle$ mean that's where the reading head is? Also, multiple tapes is never necessary (it doesn't make a Turing machine more complete), but not having to worry about different countings being in the way of one another is definitely a plus.
– Arthur
Aug 2 at 12:49
@arthur Sorry for lack of those details. The $triangle$ represents an "empty" character and _ the position of the reading head. I will update the question to include this.
– Omari Celestine
Aug 2 at 12:53
Does $triangle$ denote a fifth letter of your Turing machine's alphabet (an "empty" character, or a zero, if you will)? And does $underlinephantomtriangle$ mean that's where the reading head is? Also, multiple tapes is never necessary (it doesn't make a Turing machine more complete), but not having to worry about different countings being in the way of one another is definitely a plus.
– Arthur
Aug 2 at 12:49
Does $triangle$ denote a fifth letter of your Turing machine's alphabet (an "empty" character, or a zero, if you will)? And does $underlinephantomtriangle$ mean that's where the reading head is? Also, multiple tapes is never necessary (it doesn't make a Turing machine more complete), but not having to worry about different countings being in the way of one another is definitely a plus.
– Arthur
Aug 2 at 12:49
@arthur Sorry for lack of those details. The $triangle$ represents an "empty" character and _ the position of the reading head. I will update the question to include this.
– Omari Celestine
Aug 2 at 12:53
@arthur Sorry for lack of those details. The $triangle$ represents an "empty" character and _ the position of the reading head. I will update the question to include this.
– Omari Celestine
Aug 2 at 12:53
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
You go about designing such a machine by first developing an algorithm. It may be a good idea to keep in mind the Turing machine's limitations as you think through the agorithm (it can't "look ahead" very well, for intance, so if you manage to keep your working area free of empty characters, that will make it easy to know when you've reached the end), but apart from that, design the algorithm using language, illustrations and notes that you understand and read well. Things like "move that character to the left side of the string", and so on.
Once you've done that, you can expand on that algorithm with details on what operations your machine will actually be doing during each step and what internal states it will have. For instance, "the first character of the string is an $a$, it saves that as an internal state" and "it keeps swapping this character with its left neighbour until it it reaches an empty character".
And then you can start designing the actual machine instructions.
There are algorithms based entirely on just cleverly reordering the string, and then deleting all the superfluous characters, so you don't have to count the occurrences of each letter on multiple tapes. But you could if you wanted to. If you aleady know how to do that, then that may just as well be a faster machine for you to construct.
answered Aug 2 at 13:50
Arthur
97.9k792173
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
You go about designing such a machine by first developing an algorithm. It may be a good idea to keep in mind the Turing machine's limitations as you think through the agorithm (it can't "look ahead" very well, for intance, so if you manage to keep your working area free of empty characters, that will make it easy to know when you've reached the end), but apart from that, design the algorithm using language, illustrations and notes that you understand and read well. Things like "move that character to the left side of the string", and so on.
Once you've done that, you can expand on that algorithm with details on what operations your machine will actually be doing during each step and what internal states it will have. For instance, "the first character of the string is an $a$, it saves that as an internal state" and "it keeps swapping this character with its left neighbour until it it reaches an empty character".
And then you can start designing the actual machine instructions.
There are algorithms based entirely on just cleverly reordering the string, and then deleting all the superfluous characters, so you don't have to count the occurrences of each letter on multiple tapes. But you could if you wanted to. If you aleady know how to do that, then that may just as well be a faster machine for you to construct.
answered Aug 2 at 13:50
Arthur
97.9k792173
add a comment |Â
up vote
0
down vote
You go about designing such a machine by first developing an algorithm. It may be a good idea to keep in mind the Turing machine's limitations as you think through the agorithm (it can't "look ahead" very well, for intance, so if you manage to keep your working area free of empty characters, that will make it easy to know when you've reached the end), but apart from that, design the algorithm using language, illustrations and notes that you understand and read well. Things like "move that character to the left side of the string", and so on.
Once you've done that, you can expand on that algorithm with details on what operations your machine will actually be doing during each step and what internal states it will have. For instance, "the first character of the string is an $a$, it saves that as an internal state" and "it keeps swapping this character with its left neighbour until it it reaches an empty character".
And then you can start designing the actual machine instructions.
There are algorithms based entirely on just cleverly reordering the string, and then deleting all the superfluous characters, so you don't have to count the occurrences of each letter on multiple tapes. But you could if you wanted to. If you aleady know how to do that, then that may just as well be a faster machine for you to construct.
answered Aug 2 at 13:50
Arthur
97.9k792173
add a comment |Â
up vote
0
down vote
up vote
0
down vote
You go about designing such a machine by first developing an algorithm. It may be a good idea to keep in mind the Turing machine's limitations as you think through the agorithm (it can't "look ahead" very well, for intance, so if you manage to keep your working area free of empty characters, that will make it easy to know when you've reached the end), but apart from that, design the algorithm using language, illustrations and notes that you understand and read well. Things like "move that character to the left side of the string", and so on.
Once you've done that, you can expand on that algorithm with details on what operations your machine will actually be doing during each step and what internal states it will have. For instance, "the first character of the string is an $a$, it saves that as an internal state" and "it keeps swapping this character with its left neighbour until it it reaches an empty character".
And then you can start designing the actual machine instructions.
There are algorithms based entirely on just cleverly reordering the string, and then deleting all the superfluous characters, so you don't have to count the occurrences of each letter on multiple tapes. But you could if you wanted to. If you aleady know how to do that, then that may just as well be a faster machine for you to construct.
answered Aug 2 at 13:50
Arthur
97.9k792173
You go about designing such a machine by first developing an algorithm. It may be a good idea to keep in mind the Turing machine's limitations as you think through the agorithm (it can't "look ahead" very well, for intance, so if you manage to keep your working area free of empty characters, that will make it easy to know when you've reached the end), but apart from that, design the algorithm using language, illustrations and notes that you understand and read well. Things like "move that character to the left side of the string", and so on.
Once you've done that, you can expand on that algorithm with details on what operations your machine will actually be doing during each step and what internal states it will have. For instance, "the first character of the string is an $a$, it saves that as an internal state" and "it keeps swapping this character with its left neighbour until it it reaches an empty character".
And then you can start designing the actual machine instructions.
There are algorithms based entirely on just cleverly reordering the string, and then deleting all the superfluous characters, so you don't have to count the occurrences of each letter on multiple tapes. But you could if you wanted to. If you aleady know how to do that, then that may just as well be a faster machine for you to construct.
answered Aug 2 at 13:50
Arthur
97.9k792173
edited Aug 2 at 13:59
answered Aug 2 at 13:50
Arthur
97.9k792173
answered Aug 2 at 13:50
Arthur
97.9k792173
answered Aug 2 at 13:50
Arthur
97.9k792173
97.9k792173
add a comment |Â
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%2f2870026%2fturing-machine-that-orders-the-alphabet-characters-of-the-entered-string-based-o%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
Does $triangle$ denote a fifth letter of your Turing machine's alphabet (an "empty" character, or a zero, if you will)? And does $underlinephantomtriangle$ mean that's where the reading head is? Also, multiple tapes is never necessary (it doesn't make a Turing machine more complete), but not having to worry about different countings being in the way of one another is definitely a plus.
– Arthur
Aug 2 at 12:49
@arthur Sorry for lack of those details. The $triangle$ represents an "empty" character and _ the position of the reading head. I will update the question to include this.
– Omari Celestine
Aug 2 at 12:53