Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
infinite recursion
Recursion with (??{$re}) is only sufficient for context-free matching. Even primitive recursion requires some sort of argument passing. Pretty much the only thing you can "pass" is the current pos of the string, which is way too restricted: You have only a fixed number of values for pos, and a fixed number of regexes you could be "recursing" to, so you can answer the halting problem for these creatures (see footnote below).
cellular automata
Here the grid of automata must be unbounded. Otherwise, you only have a finite number of possible grid configurations (number of automata states ^ size of grid).
Diophantine equations
The number of variables in the equation is fixed, but their values can be arbitrarily large integers. If their values are bounded, then you only have a finite number of combinations to try (possible values ^ number of variables), and you can always halt while determining if a Diophantine equation has a solution.
cyclical tag systems
This is just like an automaton with a queue -- take from the front and add to the back. But you must allow for rules which increase the size of data in the queue, which can happen indefinitely. If you are not allowed to increase the size of the queue data (or if you have an upper limit on the queue size), you only have a finite number of queue contents and thus configurations of the automaton (number of states * (queue alphabet size ^ max queue size))
SK combinators
I don't pretend to have any special insight on SK combinators. But what you have is a very restricted projection operator K, and a very restricted recursion operator S which still encompasses primitive recursion and μ recursion. The μ recursion is the key part of the universality of general recursive functions, as the value being minimized may grow arbitrarily large.

Footnote: when a system has a finite number (say, N) of possible configurations on a given input, you can answer the halting problem for it as follows (where "halting" means entering some special subset of configurations): Simulate it for N steps. If it hasn't reached a halting configuration by then, it must repeat a configuration. Since the next configuration depends only on the previous configuration, it must be in an infinite loop and thus will never reach a halting configuration. Turing machines have an infinite tape and thus an infinite number of possible configurations.

Clearly if you can answer halting queries on a system, it is not universal (Halting Problem).


In reply to Re^3: Are Perl patterns universal? by blokhead
in thread Are Perl patterns universal? by sleepingsquirrel

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (5)
    As of 2017-11-24 21:22 GMT
    Find Nodes?
      Voting Booth?
      In order to be able to say "I know Perl", you must have:

      Results (353 votes). Check out past polls.