Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) Turing machine:

By predicates I will mean predicates in first-order predicate calculus. (Note that predicates may have free variables.)

  • constant-time modus-ponens resolution (yes or no) and then adding $y$ to the end of this array if yes, for given predicates $x$ and $y$ and an array (or a linked list) of predicates. By definition of modus ponens, it's yes, if and only if some element of the arrays is $X\Rightarrow y$ where $X$ is a pattern matching $x$.

Remark: The above operation is a part of the standard procedure of proof-checking is first-order predicate logic.

If the above hypothesis is false, then what is the running time upped bounds of the above operation in different kinds of Turning machine equivalents (such as Turing machine, Markov algorithms, von Neumann architecture with infinitely many infinitely big words of memory, etc.)?

BTW, is von Neumann architecture with infinitely many infinitely big words of memory a Turning machine equivalent? (I think yes, but not 100% sure.)

  • $\begingroup$ You can assume that the current array size is always not above the elapsed running time + input size. $\endgroup$
    – porton
    Commented Apr 16, 2021 at 9:33
  • $\begingroup$ I don't understand the operation you are trying to specify. A Turing machine doesn't have arrays or linked lists; it has a tape with symbols on it, and the symbols are from some finite alphabet that is specified in advance. What are the domains of $x$ and $X$ and $y$? What is the space of possibilities for them, and how are they represented? $\endgroup$
    – D.W.
    Commented Apr 16, 2021 at 19:22
  • $\begingroup$ It is easy to formulate what is a linked list in Turing machine. I told that these variables are first-order predicate logic formulas such as $A\land \exists X\forall Y(F\Rightarrow G)$. Then could be represented as trees. $\endgroup$
    – porton
    Commented Apr 16, 2021 at 20:23
  • $\begingroup$ I also find it unclear what is the domain of $X$, i.e., what kinds of patterns can be represented, and what is the definition of "matching". $\endgroup$
    – D.W.
    Commented Apr 16, 2021 at 20:46
  • $\begingroup$ @D.W. Any predicate formula (that can have free variables). Matching is like one in the propositional calculus: if replacement of some of free variables in $X$ by subexpressions of $x$ "located" at the same "positions" (tree paths like 0-2-3-2, denoting the numbers of child notes starting from the roots) in $X$ and in $x$ produces result equal to $x$ then (and only then) it's a match. $\endgroup$
    – porton
    Commented Apr 16, 2021 at 22:12

1 Answer 1


This boils down to the question of whether there exists a polynomial-time algorithm for your matching operation.

If there exists such an algorithm, call it $A$, then the answer to your question is yes: given an augmented Turing machine that uses these operations, you can convert it to an ordinary Turing machine by simulating those operations using $A$. This blows up the running time by at most a polynomial. (Invoking a polynomial-time subroutine at most polynomially many times leaves with a running time that remains polynomial.)

If there is no such algorithm, then the answer to your question is no: the matching problem can be solved in polynomial time (indeed, constant time) on an augmented Turing machine, but cannot be solved in polynomial time on an ordinary Turing machine.

I'm not clear on the definition of your matching operation, and I'm not an expert in computational logic, so I don't know what is the computational complexity of the matching operation you have in mind.

  • $\begingroup$ First a polynomial algorithm $A$ exists (for example, it can be deduced from the fact hat my thing is a special case of proof checking that is well known to be polynomial). But I don't understand you: What do you mean by simulating those operations using $A$? Isn't it the reverse: simulating $A$ using the Turiing machine? $\endgroup$
    – porton
    Commented Apr 16, 2021 at 22:15
  • $\begingroup$ @porton, Suppose you have code for an augmented Turing machine. I'll show how to build code for an ordinary Turing machine that does the same thing. When the code for the augmented Turing machine says "invoke that operation", then actually we call $A$. $\endgroup$
    – D.W.
    Commented Apr 16, 2021 at 23:09

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.