16
$\begingroup$

Note that this question is not a duplicate of that one. It is specifically about the pattern-matching engine, and explicitly excluding those patterns which call back into the full evaluation (i.e. PatternTest and Condition; if there are others like those, consider them excluded as well).

To state the problem more specifically: Given a problem with a yes/no answer which can be decided in finite time by an appropriate Turing machine, does there always exist a Mathematica pattern involving neither PatternTest nor Condition together with an appropriate encoding for the input data which matches iff the Turing machine would give "yes" for the input data?

To make more clear what I mean, I give an example of a problem solvable both with a Turing machine and with the pattern matcher:

Given a natural number, determine whether that number is even or odd. It is obvious that a Turing machine can solve this problem in finite time. Here's how pattern matching can solve that problem: Encode the natural number into a list of as many 1, so that 0 is {}, 1 is {1}, 2 is {1,1} etc. Then the pattern implementing the test is simply {PatternSequence[1,1]...}.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ The questions on this site are increasingly esoteric. I have no answer for your strange yet interesting question. $\endgroup$ Commented Apr 30, 2012 at 22:41
  • $\begingroup$ You might find Norman Ramsey's response in this thread quite helpful: What are practical guidelines for evaluating a language's “Turing Completeness”? $\endgroup$ Commented May 2, 2012 at 5:46
  • $\begingroup$ do you allow the use of ReplaceRepeated? $\endgroup$ Commented May 2, 2012 at 15:58
  • $\begingroup$ @R.M: No, that's not a pattern, but an operation using patterns. Basically, you should be able to "run" the pattern by writing MatchQ[yourInput,HoldPattern[yourPattern]]. $\endgroup$ Commented May 2, 2012 at 17:35
  • $\begingroup$ The basic operations (union, concatenation and Kleene star) that make regular expressions are all reproducible with patterns. It follows that patterns recognize regular expressions. The question is whether patterns can recognize all recursively enumerable languages, which is the set of langauges definable by Turing Machines. $\endgroup$ Commented May 26, 2012 at 20:43

1 Answer 1

Reset to default
6
$\begingroup$

I cannot offer a rigorous answer to this question, but I will offer some thoughts...

This question asks whether the set of functions computable using basic patterns and MatchQ is isomorphic to the subset of Turing-computable functions whose results can be expressed in a single bit. The one-bit subset restriction is important since MatchQ is clearly not fully Turing-complete since it cannot handle functions outside of that subset.

Basic pattern-matching would seem to be a very close approximation of boolean circuits. With suitable input encoding, we can implement the basic operations thus:

 a OR b --> a | b NOT a --> Except[a] a AND b --> Except[Except[a], b]

For bounded input sizes, boolean circuits are known to be able to compute any boolean function (see, for example, Theorem 1.8.1 on page 32 of Clote and Kranakis: Boolean Functions and Computation Models). The emphasis here is on bounded. Boolean circuits are known not to be Turing-equivalent due to non-uniformity. That is, a fixed-size Turing program can handle any input size while a boolean circuit must grow (exponentially!) in size as input size increases.

What is not clear to me is whether the other pattern-matching features add capability that will let us will evade this conclusion. Perhaps some creative use of BlankSequence, Repeated, Longest, Shortest, PatternSequence, etc. takes us outside of the realm of boolean circuits and toward (one bit) Turing-equivalence.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting. I think a AND b is not quite right though. Maybe should be Except[Except[a] | Except[b]] ? Regardless, once you have Or and Not, you have the full set of possibilities. $\endgroup$ Commented Sep 3, 2012 at 19:55
  • $\begingroup$ @DanielLichtblau That is an alternate representation of AND. I chose the shorter one that exploits the second argument to Except. $\endgroup$ Commented Sep 3, 2012 at 20:12

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.