# Complexity of pattern matching for modus ponens logical conclusions

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.)

• You can assume that the current array size is always not above the elapsed running time + input size. Commented Apr 16, 2021 at 9:33
• 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?
– D.W.
Commented Apr 16, 2021 at 19:22
• 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. Commented Apr 16, 2021 at 20:23
• 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".
– D.W.
Commented Apr 16, 2021 at 20:46
• @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. Commented Apr 16, 2021 at 22:12

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.)
• 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? Commented Apr 16, 2021 at 22:15
• @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$.