In class we defined what it meant for a language to be decidable in space t(n).

Question

In class we defined what it meant for a language to be decidable in space t(n). To properly define what it means for a function to be computable in space t(n), we need to use multitape Turing Machines. We treat tape 1 as a read-only input tape, tape 3 as a write-only output tape, tape 2 as a read/write work tape, and we only count the space used on tape 2 Formally, a function f is computable in space t (n) if there exists a 3-tape Turing Machine M with the following property: for every w E y, if M is started with w written on tape 1, then M halts with f(w) written on tape 3, while touching at most t(Iwl) cells on tape 2, never writing to tape 1, and never reading from tape 3 Notice that it is possible to perform non-trivial computations while using sub-linear space In fact, many important functions can be computed using only O(log n) space.

Explanation / Answer

if the question is related to funtion h(w)= f(g(w)) is computable in O(log n) the we can state by the above mentioned therory

h is computable for all the valid strings as well is g language is also the same

while calculating the space f and g are computable in polynomial time log n for all the possible strings

hence we can say it is computable for the time space complexity of O(log n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.