<p>Is there a widely accepted name and/or notation for the computational process of an algorithm as opposed to its output? To clarify, suppose I have an algorithm <span class="math-container">$A$</span>, and I denote as <span class="math-container">$A(x)$</span> the output of <span class="math-container">$A$</span> on input <span class="math-container">$x$</span>. I wish to analyze the operation of <span class="math-container">$A$</span> on input <span class="math-container">$x$</span> (analyze the intermediate values of variables, for example). Repeatedly saying &quot;as <span class="math-container">$A$</span> runs on <span class="math-container">$x$</span>&quot; or something along these lines is very verbose. Any suggestions?</p>

CC BY-SA 4.0
2024-10-28T19:39:56.563Z
People often talk about the "computation history" or "computation tableau" or, as you said, the "run of A on input x"
Joshua Grochow
CC BY-SA 4.0
2024-10-28T20:28:15.830Z
You might also look at the papers on the simplex method being NP-mighty and PSPACE-mighty, since those notions are about the run of the algorithm rather than its output.
Joshua Grochow
CC BY-SA 4.0
2024-10-28T20:29:24.540Z
Is that a well-defined concept? Can I say something like A<x> is the computation history of A on input x?
gumbelgrumbelgumbel
CC BY-SA 4.0
2024-10-28T20:30:27.873Z
Execution trace.
Andrej Bauer
CC BY-SA 4.0
2024-10-28T22:07:25.930Z
Yes. I mean, you should define it so it's clear in what sense you are using it, but yes it's well defined. The sequence of configurations of the Turing machine A (or whatever computational formalism - in TMs the config includes the tapes and all) when run on input x.
Joshua Grochow
CC BY-SA 4.0
2024-10-29T13:52:24.303Z
Thanks Joshua and Andrej. This has been very helpful.
gumbelgrumbelgumbel
<cc.complexity-theory><ds.algorithms><computability>
Terminology for computation vs. output
gumbelgrumbelgumbel
# Terminology for computation vs. output

(Asked by: username_0 on 2024-10-28)

Is there a widely accepted name and/or notation for the computational process of an algorithm as opposed to its output? To clarify, suppose I have an algorithm $A$, and I denote as $A(x)$ the output of $A$ on input $x$. I wish to analyze the operation of $A$ on input $x$ (analyze the intermediate values of variables, for example). Repeatedly saying "as $A$ runs on $x$" or something along these lines is very verbose. Any suggestions?

**Tags:** cc.complexity-theory, ds.algorithms, computability
> **Comments:**
> **username_1**: People often talk about the "computation history" or "computation tableau" or, as you said, the "run of A on input x"  
> **username_1**: You might also look at the papers on the simplex method being NP-mighty and PSPACE-mighty, since those notions are about the run of the algorithm rather than its output.  
> **username_0**: Is that a well-defined concept? Can I say something like A<x> is the computation history of A on input x?  
> **username_2**: Execution trace.  
> **username_1**: Yes. I mean, you should define it so it's clear in what sense you are using it, but yes it's well defined. The sequence of configurations of the Turing machine A (or whatever computational formalism - in TMs the config includes the tapes and all) when run on input x.  
> **username_0**: Thanks Joshua and Andrej. This has been very helpful.  

---

## 0 answers

