Yioop - PHP Search Engine

Apr 15 In-Class Exercise Thread.

Post your solution to the Apr 15 In-Class Exercise to this thread.

Best,

Chris

Post your solution to the Apr 15 In-Class Exercise to this thread. Best, Chris

-- Apr 15 In-Class Exercise Thread

In the exercise we consider an alphabet of 2 symbols. We can simulate more inputs symbols by using more states corresponding to strings of the original symbols. In this example we can map one to one binary numbers as strings of 1s and 0s in the input to the new set of symbols.

For example an input of abc would using mappings a->00 b->01 c->10 the new input would be 000110

More generally n starting symbols mapped to m new symbols can be represented with base-n strings where the length of these strings would have to be log-base-n of m. This would be the average increase in complexity for each symbol.

(Edited: 2020-04-15)

In the exercise we consider an alphabet of 2 symbols. We can simulate more inputs symbols by using more states corresponding to strings of the original symbols. In this example we can map one to one binary numbers as strings of 1s and 0s in the input to the new set of symbols. For example an input of abc would using mappings a->00 b->01 c->10 the new input would be 000110 More generally n starting symbols mapped to m new symbols can be represented with base-n strings where the length of these strings would have to be log-base-n of m. This would be the average increase in complexity for each symbol.

-- Apr 15 In-Class Exercise Thread

You could simulate the larger inputs by using binary

For ex, the alphabet {A, B, C} could be mapped like

A -> 00

B -> 01

C -> 10

the tape here has to read 2 of the {0, 1} symbols to map to the original alphabet

If the original machine had an input length of k, the new machine has an input length of logk

Each transition from the original machine needs to read, write, then move left/right - reading on the new machine will take logk time, writing on the new machine will take another logk time, and then moving left/right on the new machine will take logk time. Thus overall the new machine will take around 3logk time to process each of the original machine's transitions.

(Edited: 2020-04-15)

You could simulate the larger inputs by using binary For ex, the alphabet {A, B, C} could be mapped like A -> 00 B -> 01 C -> 10 the tape here has to read 2 of the {0, 1} symbols to map to the original alphabet If the original machine had an input length of k, the new machine has an input length of logk Each transition from the original machine needs to read, write, then move left/right - reading on the new machine will take logk time, writing on the new machine will take another logk time, and then moving left/right on the new machine will take logk time. Thus overall the new machine will take around 3logk time to process each of the original machine's transitions.

-- Apr 15 In-Class Exercise Thread

Let the tab alphabet is {a1, a2, a3,....., an}
we can represent:
a1 as 00...00 ( lg n zero)
a2 as 00...01 ( lg n - 1 zero and one 1)
a3 as 00...11
....
an as 11...11 ( lg n one)
-> the size becomes 2^n bigger => it slows down 2^n time

(Edited: 2020-04-15)

* Let the tab alphabet is {a1, a2, a3,....., an} * we can represent: * a1 as 00...00 ( lg n zero) * a2 as 00...01 ( lg n - 1 zero and one 1) * a3 as 00...11 * .... * an as 11...11 ( lg n one) * -> the size becomes 2^n bigger => it slows down 2^n time

-- Apr 15 In-Class Exercise Thread

In order to simulate other alphabet symbols, we can code the new symbols using patterns of 0 and 1. To know what symbol to use, the machine will have to transition into a state for that specific symbol. There would have to be two states for every symbol, one that tells the machine to read or write that symbol. If the number of new symbols is n then there will need to be lg(n) patterns built from 0 and 1. So the slowdown will of the new machine will be lg(n).

-- Apr 15 In-Class Exercise Thread

If we're limited to {0, 1}, a binary system can be used to represent larger tables with more symbols than we have in our alphabet {0, 1}. For example, as we go up the symbols of the larger table, the binary will be assigned to each symbol in ascending order (in binary). Since the binary representation of the numbers grows logarithmically, the slowdown will be 2^n

-- Apr 15 In-Class Exercise Thread

With a TM that has only {0,1} as input alphabet and {0,1,_} for tape alphabet.

 For a larger input, a combination of {0,1} can be used to map the larger input.
 This means the tape will need to read 2 symbols to map back to original alphabet.
 If we have that the original machine has an input length of n, 
 then the new machine would have and input length of log(n). 
 The TM would have to transition into a state for that input.
 When the original machine transitions, each of the new machine's transitions 
 needs to read, write, and whether to move right/left. 
 The new machine will need log(n) time to read, log(n) to write, 
 and log(n) to move right/left. 
 This means the new machine will take 3*log(n) time to process each of the original 
 machine's transitions.

(Edited: 2020-04-15)

With a TM that has only {0,1} as input alphabet and {0,1,_} for tape alphabet. For a larger input, a combination of {0,1} can be used to map the larger input. This means the tape will need to read 2 symbols to map back to original alphabet. If we have that the original machine has an input length of n, then the new machine would have and input length of log(n). The TM would have to transition into a state for that input. When the original machine transitions, each of the new machine's transitions needs to read, write, and whether to move right/left. The new machine will need log(n) time to read, log(n) to write, and log(n) to move right/left. This means the new machine will take 3*log(n) time to process each of the original machine's transitions.

-- Apr 15 In-Class Exercise Thread

You can simulate a machine with a larger input or tape alphabet by introducing patterns of the 1's and 0's if that is all we have to work with. This would ultimately work a lot like binary. Because of this sort of simulation, you would see a slowdown of log(n) because it has a lot more characters to process.

-- Apr 15 In-Class Exercise Thread

Let's say the original machine O we are trying to simulate has k alphabet symbols.

Our new machine M, which tries to simulate the original machine O, has input alphabet {0,1}. It uses this alphabet to simulate the k alphabet symbols of O.

Every consecutive ceiling(log base 2 of k) symbols on the input tape of M correspond to single element of the k alphabet symbols in the original machine O.

M reads consecutive sequences of ceiling(log base 2 of k) symbols at a time, and writes over them, moving left or right after each read according to the transition rules of the original machine O.

Does this explanation suffice?

Let's say the original machine O we are trying to simulate has k alphabet symbols. Our new machine M, which tries to simulate the original machine O, has input alphabet {0,1}. It uses this alphabet to simulate the k alphabet symbols of O. Every consecutive ceiling(log base 2 of k) symbols on the input tape of M correspond to single element of the k alphabet symbols in the original machine O. M reads consecutive sequences of ceiling(log base 2 of k) symbols at a time, and writes over them, moving left or right after each read according to the transition rules of the original machine O. Does this explanation suffice?

-- Apr 15 In-Class Exercise Thread

To simulate the new symbols, we can code them using patterns of 0 and 1. We will have a transition for each symbol, with two states, one that tells the machine to read and one that tells the machine to write. For n new symbols, there will need to be lg(n) patterns built from 0 and 1, which makes the slowdown of the new machine be lg(n).