Log-space transducer
id:
log-space-transducer-241-17137805
title:
Log-space transducer
text:
In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, M , has three tapes: A read-only input tape.
A read/write work tape.
A write-only, write-once output tape. M will be designed to compute a log-space computable function f : Σ ∗ → Σ ∗ . If M is executed with w on its input tape, when the machine halts, it will have f remaining on its output tape. A language A ⊆ Σ ∗ is said to be log-space reducible to
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Log-space_transducer
date created:
date modified:
2023-03-14T01:20:40Z
main entity:
{"identifier":"Q6666758","url":"https://www.wikidata.org/entity/Q6666758"}
image:
fields total:
13
integrity:
13