General information
Project Description
We study the relation between space and time of computation of a Turing machine,
which can be alternatively described in terms of depth and size of a circuit.
Our current goal is to improve the result of TIME(T) ⊆ SPACE(T/log T).
Progress
1st week
Introductory
presentation to the topic.
Studying time vs. space and size vs. depth relations in turing machines and circuits, respectively.
2nd week
We have figured out a way of converting multitape Turing machine into a circuit
of linear depth (w.r.t. the original time), linear-logarithmic size,
bounded in-degree,
and other useful properties.
3rd week
We were proving correctness of our construction
and discovering possible ways
of compressing the depth of the circuit.
A simple compression leads to the same depth
as state-of-the-art constructions.
4th week
We were trying to combine two known constructions for depth compression.
Unfortunately, this appeared to be a blind alley because of proving their equivalence.
Finally, another possible research direction was found.
5th week
We were developing the new ideas and obtained a new construction for one-tape Turing machine.
We were however not able to adjust the construction for multiple tapes, yet.
6th week
Kyle succeeded modifying the construction by adding a new but read-only tape into the Turing machine.
He also partitioned the construction into multiple stages and presented it in a well-structured way.
We were then trying to allow modifications of the new tape,
which was not successful, yet.
7th week
We were preparing our final presentation with results
and saw all the other presentations on Thursday and Friday.
There was little progress during the remaining time.
8th week
Two workshops and a conference were happening that week,
so there was also not much time for research.
We were thinking about our constructions
but no useful ideas appeared.
