0
$\begingroup$

I am writing a paper on the invariance thesis introduced by Cees F. Slot and Peter van Emde Boas as;

'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

The paper I am writing is in Croatian where I cannot find a properly convenient word like "overhead". Also, I am unable to find a strict Computer Science definition for the term.

Specifically, I have $Time(M)$ as the cost of reducing the $\lambda$-term $M$ to its normal form and a Turing machine able to simulate this reduction in $O((Time(M))^4)$. Therefore, I would like to say "this TM can simulate $\lambda$-calculus with polynomial-time [overhead]" concisely as it is in English.

I would appreciate any suggestion in the form of literature references for the definition, advice on how to best define it myself or even synonyms of the word.

$\endgroup$
  • $\begingroup$ Can this Wiki article help you a little bit? $\endgroup$ – scaaahu Aug 25 '18 at 14:14
  • $\begingroup$ Thanks. Your suggestion also gives me an idea to narrow my question. It is not that I'm unsure what overhead is, but the problem I have is how to say it concisely in Croatian. I may have to define a new word in my paper or just use "overhead", but I will wait for more suggestions. $\endgroup$ – Sandro Lovnički Aug 25 '18 at 14:36
  • $\begingroup$ I'm not sure that "how do I phrase this concisely in Croatian?" is on-topic here. $\endgroup$ – D.W. Aug 25 '18 at 15:09
  • 1
    $\begingroup$ You are right and I am not asking that. I am asking for various definitions or possible synonyms for overhead to help me with phrasing it. Because, where else could I find a group of people capable of correctly rephrasing polynomial-time overhead when simulating computation machines. $\endgroup$ – Sandro Lovnički Aug 25 '18 at 15:12
1
$\begingroup$

I doubt that “overhead” is a term. Here’s what we use in Russian papers:

  1. оверхед — direct transliteration (for informal texts)
  2. издержки — costs (of production)
  3. Translations of “slowdown” (for time) and “blow-up” (for space).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.