2020-04-16
((resource:inclass0416.jpg|Resource Description for inclass0416.jpg))
2020-04-17
Let M be a TM that has only {0,1} as its input alphabet and {0,1, □} as its tape alphabet.
To simulate a TM machine P whose input alphabet has k elements where k > 2, we can map each element of P’s input alphabet to a string of 0 and 1 whose length is at most logk.
Best case scenario: P reads 1 input and then advances to the right. To simulate this behavior, M will read logk input and stop.
Worst case scenario: P reads 1 input, overwrite it with a new one, and then goes left. To simulate this behavior, M will read logk input to determine which input of P it is reading, then go back logk squares to the left, then write a new string of logk input, then go back 2logk to the left. The total is 5logk.
Thus, in worst case scenario, P will slow down by the factor of 5logk. In best case scenario, P will slow down by the factor of logk.
Let M be a TM that has only {0,1} as its input alphabet and {0,1, □} as its tape alphabet.
To simulate a TM machine P whose input alphabet has k elements where k > 2, we can map each element of P’s input alphabet to a string of 0 and 1 whose length is at most logk.
Best case scenario: P reads 1 input and then advances to the right. To simulate this behavior, M will read logk input and stop.
Worst case scenario: P reads 1 input, overwrite it with a new one, and then goes left. To simulate this behavior, M will read logk input to determine which input of P it is reading, then go back logk squares to the left, then write a new string of logk input, then go back 2logk to the left. The total is 5logk.
Thus, in worst case scenario, P will slow down by the factor of 5logk. In best case scenario, P will slow down by the factor of logk.
In order to simulate a machine with a larger input or tape alphabet, we can limit the input alphabet to {0, 1}. When we have a larger input, we can use the combination for the larger input. For every symbol in the TM, there will be read and write which brings us binary relations. Then if we have k symbols in our TM. the time has been slowed down will be lg(k)
In order to simulate a machine with a larger input or tape alphabet, we can limit the input alphabet to {0, 1}. When we have a larger input, we can use the combination for the larger input. For every symbol in the TM, there will be read and write which brings us binary relations. Then if we have k symbols in our TM. the time has been slowed down will be lg(k)
((resource:IMG_2976.jpg|Resource Description for IMG_2976.jpg))
2020-04-19
Large inputs can be computed and mapped as binary symbols [0,1].
2 symbols will be read and can then be mapped to our alphabet.
Example, say 00 = c or 11 = a.
Our original Turing Machine has the input of length n. Then our augmented machine will have input of log(n) for both reading, writing and moving right or left.
Large inputs can be computed and mapped as binary symbols [0,1].
2 symbols will be read and can then be mapped to our alphabet.
Example, say 00 = c or 11 = a.
Our original Turing Machine has the input of length n. Then our augmented machine will have input of log(n) for both reading, writing and moving right or left.
One method in which we can simulate a machine with a larger input or tape alphabet with the given restriction of {0, 1} as our input alphabet is via the binary system. By using the binary system, we're allowed to represent practically any other symbol as long as we systematically map the patterns of 1s and 0s correctly. In terms of speed, our slowdown will be of the time complexity lg(n) due to the fact that with every introduction of a symbol {0, 1}, there will be a two options presented, which is a natural lg(n) growth with respect to the number of symbols.
One method in which we can simulate a machine with a larger input or tape alphabet with the given restriction of {0, 1} as our input alphabet is via the binary system. By using the binary system, we're allowed to represent practically any other symbol as long as we systematically map the patterns of 1s and 0s correctly. In terms of speed, our slowdown will be of the time complexity lg(n) due to the fact that with every introduction of a symbol {0, 1}, there will be a two options presented, which is a natural lg(n) growth with respect to the number of symbols.
We can simulate the larger inputs by introducing new symbols which are the combination of {0,1}. For example, we can make A -> 00, B ->01, C -> 10 and so on.
If we have the original machine has an input length of n, then the new machine will have an input length of log(n). And the Turing Machine will have to transfer into a state of that input. And each of the new machine needs to read, write, and move left or right when the original machine in transition. And need machine needs to take log(n) time for both read, write, and move right or left. Thus, the slowdown will be 3*log(n)
We can simulate the larger inputs by introducing new symbols which are the combination of {0,1}. For example, we can make A -> 00, B ->01, C -> 10 and so on.
If we have the original machine has an input length of n, then the new machine will have an input length of log(n). And the Turing Machine will have to transfer into a state of that input. And each of the new machine needs to read, write, and move left or right when the original machine in transition. And need machine needs to take log(n) time for both read, write, and move right or left. Thus, the slowdown will be 3*log(n)
to find new symbols you can code it using 1's and 0's very similar to binary patterns. set a transition for each new symbol. one for reading and the other for writing. there would be a slowdown of log(n) on the new machine because it has a lot more characters to process.
to find new symbols you can code it using 1's and 0's very similar to binary patterns. set a transition for each new symbol. one for reading and the other for writing. there would be a slowdown of log(n) on the new machine because it has a lot more characters to process.
To simulate a machine with a larger input or tape alphabet, If the original machine has an input length of k, we can map each element of P’s input alphabet to a string of 0 and 1 whose length is at most logk. Then the TM will transfer into a state of that input. And each of the new machine has read write and move left or right with binary relations. Therefore, each step will slow down log(k) and the total slow down should be 3log(k).
To simulate a machine with a larger input or tape alphabet, If the original machine has an input length of k, we can map each element of P’s input alphabet to a string of 0 and 1 whose length is at most logk. Then the TM will transfer into a state of that input. And each of the new machine has read write and move left or right with binary relations. Therefore, each step will slow down log(k) and the total slow down should be 3log(k).
Because we are limited to {0, 1}, we can use binary to simulate the larger input. As we go through the table binary would be assigned in ascending order which is binary. In this case, we would experience a slowdown of log(n) for n characters because there would be way more characters to process.
Because we are limited to {0, 1}, we can use binary to simulate the larger input. As we go through the table binary would be assigned in ascending order which is binary. In this case, we would experience a slowdown of log(n) for n characters because there would be way more characters to process.
(c) 2024 Yioop - PHP Search Engine