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