0
$\begingroup$

Do the following measures qualify as computational resources?

  1. number of even-numbered states that the machine $M$ visits on input $x$

  2. number of times that the machine $M$, when run on input $x$, rewrites symbols on the tape

$\endgroup$
4
  • $\begingroup$ What are even numbered states? Are you assigning numbers to the Turing Machine states? How? Is the numbering part of the input? $\endgroup$
    – Steven
    Oct 3, 2021 at 10:23
  • 1
    $\begingroup$ Also, you might want to add or point to a formal definition of "computational resource". $\endgroup$
    – Steven
    Oct 3, 2021 at 10:35
  • 1
    $\begingroup$ Computational resource is not a standard term (at least not in English), making this question impossible to answer at its present form. $\endgroup$ Oct 3, 2021 at 11:34
  • 1
    $\begingroup$ Please don't delete questions after they have received an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful to others in the future, so deleting your question after it has been answered can be considered impolite to the person who took the time to write an answer. $\endgroup$
    – D.W.
    Oct 5, 2021 at 8:08

2 Answers 2

1
$\begingroup$

You haven't defined what you mean by a computational resource, but I'll answer the question using the definition by the Blum axioms. To paraphrase the Wikipedia page in the notation here, a computational resource is a partial computable function $\Phi$ such that

  1. $\Phi$ takes two arguments -- a Turing machine and an input word -- and evaluates to a natural number,
  2. $\Phi(M, w)$ is defined iff $M(w)$ is, and
  3. given $M, w, k$ it's decidable whether $\Phi(M, w) = k$.

In this formalism your first example is not a computational resource (it doesn't satisfy the last axiom, by a reduction from the halting problem), but the second one is (it's decidable whether a given Turing machine will rewrite at least one more symbol from a given configuration, since if it doesn't, it will soon enter an infinite loop).

$\endgroup$
2
  • $\begingroup$ How to make many-one-reductions to HP for the first language? $\endgroup$
    – Math Geek
    Oct 10, 2021 at 16:39
  • 1
    $\begingroup$ @MathGeek Given machine $M$ and word $w$, make a new machine that behaves as $M$ but using state number $2i$ for state $i$ of $M$, and enters state $1$ when it halts. Leave the other odd states unreachable. $\endgroup$ Oct 10, 2021 at 17:30
1
$\begingroup$

"Computational resource" is a bit of an open-ended notion, but it always signifies a capacity for a program to use, control, or inspect something that is external to the program itself.

According to this understanding your suggestions are not computational resources. They are closer to something like "observations about the behavior of the program" or "analysis of how the resource is used". To make the contrast more explicit:

  1. The tape is a resource (namely mutable state).
  2. Measuring how much tape has been used by a machine constitutes analysis of its space complexity, i.e., how much of the available resource has actually been used.

Your suggestions are more like 2 above. Still more explicit:

  1. The water supply in your house is a resource available to you.
  2. The amount of water you use is not a resource, it is a measure of your water-complexity.
  3. How much water you used on odd-numbered days is still just a measure of your water-complexity, albeit a strange one.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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