https://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.html

Computational Complexity

Computational Complexity and other fun stuff in math and computer
science from Lance Fortnow and Bill Gasarch

Sunday, December 03, 2023

Where do Non-Primitive Recursive Functions come up NATURALLY?

The following is a conversation between Clyde Kruskal and Bill
Gasarch.

CLYDE:  Bill, a student, Ian Roberts,  asked me if there are any
non-primitive recursive functions that people actually want to
compute. (See here for a definition of Primitive Recursive. Also see 
here for Ackermann's function which is computable but not primitive
recursive.) 

BILL: Off hand I would say no, but non-prim rec functions DO come up
in natural ways.

CLYDE: That's not what he asked.

BILL: Even so, that's what I will blog about. OH, one more thing, why
does he want to know?

CLYDE: Ask him directly. (BILL then emailed Ian)

BILL: Good question about NATURAL problems that are not prim-rec, but
why do you want to know?

IAN:  Meyer and Richie proved (see here) that if you limit the
control flow to IF statements, FOR loops with finite iterators then
the class of functions you implement is  exactly the primitive
recursive functions. So I was wondering if I could avoid ever using
WHILE loops since they are harder to reason about. 

BILL: YES you COULD avoid ever using WHILE LOOPS; however, there are
times when using them is the best way to go.

CLYDE: Bill, when is the last time you wrote a program? And LaTex
does not count. 

BILL: Good point. Rather than take my word for it, let's ASK my
readers. I'll add that to my list of RANDOM THOUGHTS ABOUT non-prim
rec functions. 

SO, random thoughts on non-prim rec functions

0) Are there problems for which writing a WHILE loop is the way to go
even though they are  not needed? 

1) HALT is not prim recursive and we want to compute it. Oh well. All
future examples will be computable.

2) QUESTION: Are there simple programming languages so that HALT
restricted to them is decidable but not primitive recursive? I
suspect one could contrive such a language so I ask for both natural
and contrived examples. 

3) The Paris-Harrington Numbers from Ramsey Theory are computable
and  grow MUCH faster than prim rec. Indeed- they grow much faster
than Ackermann's function. See Wikipedia Entry.

4) The Kanamori-McAloon Theorem from Ramsey theory is computable and
grow MUCH faster than prim rec. Indeed- they grow much faster than
Ackemann's function. See Wikipedia Entry. They are not as well known
as the Paris-Harrington numbers. Hopefully this blog post will help
that. 

5) Goodstein's Theorem yields numbers that are computable and grow
MUCH faster than prim rec. Indeed, they grow much faster than
Ackermann's function. See Wikipedia Entry and/or my blog post on
them.

6) QUESTION: Of PH, KM, GOOD, which grows fastest? Second fastest?
Third fastest? Perhaps some are tied.

6) QUESTION: We know that GO and CHESS have very high complexity, but
are still prim recursive. We know that there are some math games
(e.g., the Hydra game) that are not prim recursive. Are there any
FUN  games whose complexity is NOT prim recursive?

7) Tarjan's UNION-FIND data structure has amortized complexity
roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's
function. This is also a lower bound. See Wikipedia entry
on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data
structure actually used? It can be used to speed up Kruskal's MST
algorithm, but that just takes the question back one step: Is MST a
problem people really want to solve? I asked Lance and he asked
chatty. For the results of that see here . The answer seems to be
YES, though I wonder if the speedup that UNION-FIND gives is
important. Union-Find is also used in the Hoshen-Kopelman Algorithm
for (to quote Wikipedia) labeling clusters on a grid, where the grid
is a regular network of  cells, with the cells being either occupied
or unoccupied.  Other issues:  (a) is UNION-FIND hard to code up?
Lance tells me that it is easy to code up.  (b) Is the constant
reasonable?

8) Is the Ackerman Security Company called that since they claim that
breaking their security is as hard as computing Ackerman's function?
Unlikely- they spell it with only one n at the end. Even so, my class
believed me when I told them that. 

9) The finite version of Kruskal's Tree Theorem YADA YADA YADA not
prim rec. Wikipedia Entry

CLYDE: You can't YADA YADA YADA my Uncle Joe!

BILL: It's my party and you'll cry if you want to, cry if you want
to, cry if you want to. (See here for Leslie Gore's song Its my party
and I'll cry if I want to which is not about non primitive recursive
functions. Also see her sequel Judy's turn to cry.  A much better
song with a better message for teenagers is her You don't own me.)

CLYDE: Oh well. However, I'll make sure to tell that example to my
class.


Posted by gasarch at 7:41 PM # #
Email ThisBlogThis!Share to TwitterShare to FacebookShare to
Pinterest

12 comments:

 1. [blank]
    Dave Doty8:03 PM, December 03, 2023

    The reachability problem for chemical reaction networks
    (equivalently, Petri nets or vector addition systems or
    "commutative semigroups") is decidable but not in any primitive
    recursive time bound (shown independently in two FOCS 2022
    papers: https://arxiv.org/abs/2104.13866, https://arxiv.org/abs/
    2104.12695). It's the reachability problem on directed graphs
    defined by chemical reaction networks, where nodes are
    configurations and edges are determined by reactions.

    For instance, starting with configuration {1X} (1 copy of X),
    with possible reactions (1) X --> Y+Y+Y and (2) Y --> A+Z+Z, we
    can reach {3A,6Z} by doing reactions 1,2,2,2, but we cannot reach
    to {6Z}.

    I find this to be a very natural problem, and it comes up
    repeatedly in studying these systems. (e.g., in verification of
    distributed systems: https://arxiv.org/abs/1703.04367)

    ReplyDelete
    Replies
     1. [blank]
        Clyde Kruskal10:25 PM, December 03, 2023

        For such natural sounding problems, the results seem to be
        very recent. Is there a reason for that?

        Delete
        Replies
            Reply
     2. [blank]
        Dave Doty12:02 AM, December 04, 2023

        Yeah, because they are really difficult. :)

        It's fairly straightforward (once you've wrapped your head
        around the model and how it can simulate register machines,
        which can in turn simulate Turing machines) to show that the
        problem is PSPACE-hard, by directly simulating register
        machines with register counts bounded by an exponential
        function of the number of reactions, and register machines
        with exponential counts can simulate polynomial-space Turing
        machines.**

        Lipton in the 1970's (https://www.cs.yale.edu/publications/
        techreports/tr63.pdf) showed a more complex simulation where
        the registers can have *doubly* exponential counts, which can
        simulate exponential-space Turing machines. For many decades
        hardness results were stuck there, but in the past few years
        there were some breakthroughs culminating in the two FOCS
        papers I mentioned.

        It's perhaps even more difficult to show that the problem is
        decidable. That result has a contentious history, which many
        people claiming credit. Jerome Leroux won the Best Paper
        Award at the Turing Centential 2012 conference for giving a
        simpler proof of this result. (https://easychair.org/
        publications/paper/Blr) He also discusses the history of
        various proofs of this result in the intro of that paper.


        **Here's an argument for PSPACE-hardness if you're curious.

        You simulate a transition "increment register R and go from
        state A to state B" by the reaction A --> B+R, where you have
        exactly one molecule representing the state, and n copies of
        R to represent that register R has value n. The difficulty is
        simulating the decrement transition "decrement register R and
        go from state A to state B, UNLESS R is already 0, in which
        case go to state C instead". One is tempted to do this via a
        pair of reactions A+R --> B (in case R has positive count)
        and A --> C (in case R has count 0), but the fundamental
        difficulty is how to prevent the second reaction from
        occurring if R has positive count. The hard problem for
        reaction networks is detecting when some molecule is absent
        and enabling certain reactions only if it is, ability not
        built into the model.

        A way around this, but that only works for register machines
        with counts bounded by 2^k, where there are O(k) total
        reactions, is this. First, represent register R by a pair of
        species R and R'. When you start, before incrementing R,
        increment R' to 2^k via reactions R1 --> R2+R2, and R2 -->
        R3+R3, ... R{k-1} --> R'+R'. Increment and decrement now
        convert between R and R' rather than simply creating and
        destroying R, preserving that R+R'=2^k at all times, e.g., to
        increment as above, use reaction A+R' --> B+R.

        Then, to test whether R is 0, instead test whether R'=2^k via
        reactions

        R'+R' <--> T{k-1}
        T{k-1}+T{k-1} <--> T{k-2}
        ...
        T2+T2 <--> T1
        T1+A --> T1+C

        which can produce T1 (which converts A into C) if and only if
        R' is at least 2^k (which means it is in fact equal to 2^k
        since it can't be larger). Notice the reactions are
        reversible in case R' has smaller count, so that we don't get
        stuck in the test making R' unavailable for increment
        operations; if you wait long enough eventually you'll get all
        the R' back through the reverse reactions.

        Delete
        Replies
            Reply
     3. [blank]
        Anonymous3:06 AM, December 04, 2023

        Pardon my ignorance, but doesn't the chemical reaction
        reachability problem look very much like "Is string X in
        language L?" found in automata and regex?

        Delete
        Replies
            Reply
     4. [blank]
        Anonymous7:16 AM, December 04, 2023

        Superficially, these look like the reduction rules for a
        Context Free Grammar, and the register machine simulation a
        linear bounded Turing Machine.

        Delete
        Replies
            Reply
     5. [blank]
        EG9:05 AM, December 04, 2023

        Both problems involve the notion of reachability or
        attainability. In chemical reactions, it's about reaching a
        certain state or configuration of molecules, while in
        automata, it's about reaching an accepting state when
        processing a string.
        Both problems can be formally represented and analyzed within
        the frameworks of their respective models (chemical reaction
        networks and automata).
        but there are differences, Chemical Reaction Reachability:
        Involves the dynamics of chemical reactions and the evolution
        of molecular configurations over time.
        Language Membership (Automata/Regex): Involves recognizing
        whether a given string belongs to a formal language defined
        by a set of rules (automaton or regular expression).
        correct me please.
        Chemical Reaction Reachability: The decidability of the
        problem is discussed, with Leroux's proof of decidability
        being mentioned. But Language Membership (Automata/Regex):
        Membership in regular languages is decidable, but
        decidability depends on the class of languages (regular,
        context-free, etc.).

        Delete
        Replies
            Reply
        Reply
 2. [blank]
    EG10:05 PM, December 03, 2023

    https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem
    Paris-Harington --> Paris-Harrington

    ReplyDelete
    Replies
     1. [blank]
        Anonymous10:13 PM, December 03, 2023

        (This is Bill) Fixed, thanks. I used to call them `The Large
        Ramsey Numbers' but a professor who had Harrington as his
        advisor told me NO, call them the Paris-Harrington Numbers.
        So now I do and usually spell it correctly.

        Delete
        Replies
            Reply
        Reply
 3. [blank]
    Alex Fischer9:13 AM, December 04, 2023

    The union-find algorithm has an application to decoding the
    surface code, an important quantum error correcting code. https:/
    /arxiv.org/abs/1709.06218

    ReplyDelete
    Replies
        Reply
 4. [blogger_lo]
    CR Drost11:54 AM, December 04, 2023

    Ian, while loops are exceedingly useful for expressing workloads
    where doing a workstep can create more work. Define a to-do
    queue, while it's not empty, process an element, if that element
    has follow-up work add it to the queue.

    The "classics" that use this are breadth-first-search and
    Dijkstra. You almost never have a problem that needs it but every
    once in a while you do.

    A limited form is rules engines. I like Slither Link and Nurikabe
    and other logic puzzles like Sudoku but they often involve a
    large amount of "grunt work" at the large sizes where you get
    interesting logical structures that you actually have to think
    deeply about. I don't want to check the entire board for patterns
    because that makes the checks hard to write, rather I want my
    input to cause the computer to check for some simple local
    patterns that I define, like in Sudoku "does this square have
    only one place for a 3, then fill in a 3 there." But then those
    need to "cascade" if and only if the computer fills in a value,
    to the locale of the new cell the computer used. But this should
    not interrupt checking the other contexts of this particular move
    that I made. So the best way I have found to express this sort of
    problem is to be able to define a sum-type of contexts (Sudoku:
    row 3 vs column 3 vs square 3 vs maybe the value 3, since Sudoku
    is abstractly a 9x9x9 cube of bits), rules that look for a
    certain context and then inspect it to see if they can simplify
    it, and when you make a move you push the contexts onto a queue.
    While the queue is nonempty, apply rules to that context, if the
    rule substitutes into a cell, then push that cell's contexts onto
    the queue.

    One other experience that I have had: sometimes the level of
    nesting of for-loops is itself a parameter, so if I want to
    generate all permutations of n values for example, the ideal
    imperative structure does not exist without hardcoding in n: I
    can give you all 4-permutations with 3 nested for-loops! So then
    you have to do like a "recursive plus for loop" mix that I don't
    like the look of... Or you can just create another queue! So for
    permutations this would be a queue of (Prefix, rest) tuples,
    while queue has items, pull out an item, if there's only one last
    item emit prefix ++ rest, else for each of the rest, jam it onto
    a copy of the prefix and insert those "todos" into the queue.

    Point is from the moment you notice "argh I need to nest the for
    loops dynamically" you can almost always reach for this tool
    instead, essentially maintaining your own lightweight call stack.

    ReplyDelete
    Replies
        Reply
 5. [blank]
    Sylvain Schmitz12:07 PM, December 04, 2023

    For (2): the lower bounds mentioned by @Dave Doty are established
    through rather simple counter programs. They have a HALT
    instruction, whether they halt is decidable, but the complexity
    is Ackermann.

    ReplyDelete
    Replies
     1. [blank]
        Sylvain Schmitz1:33 PM, December 04, 2023

        For (6): IIRC, they're tied (all independent of Peano
        arithmetic, but not more)
        For (7): Union-find is also used in some unification
        algorithms, which are themselves used in first-order
        resolution and in type inference. I gave once a student
        assignment implementing type inference for an ML-like
        language with polymorphic types; union-find is rather easy to
        code and really efficient.

        Delete
        Replies
            Reply
        Reply

Add comment
Load more...

 

Older Post Home
Subscribe to: Post Comments (Atom)

Books

[9780691175]

Commissions earned from Amazon Links

Mastodon Feed

Blog Links

  * Bill's Home Page
  * Lance's Home Page
  * ChatPNP
  * Ask Questions to the Blog
  * Videos
  * Podcasts
  * Posts Feed
  * Comments Feed
  * Foundations of Complexity Lessons
  * Computational Intractability: A Guide to Algorithmic Lower Bounds
  * P v NP Survey (2009)
  * Fifty Years of P vs. NP (2022)
  * CACM Conference Viewpoint
  * Favorite Theorems
  * Favorite Complexity Books (commissions earned)
  * Graduate Student Guide

Popular Posts

  * In the bad old days we had Punchcards. How did people deal with
    that?
  * Where do Non-Primitive Recursive Functions come up NATURALLY?
  * Inverting a Function
  * The Engineer and The Computer Scientist
  * Why did 1+1=2 take Russell and Whitehead 300 pages?
  * Forgetting your password is usually not a big deal. Unless....
  * Othello. Solved.
  * War Games
  * Can I make money in the betting markets based on what i ``know''
    about the Republican VP choice
  * Intelligent questions about the alleged P NE NP proof

Complexity Links

  * Complexity Conference
  * SIGACT
  * Theory Announcements
  * Theory Stack Exchange
  * Complexity Zoo
  * Complexity on arXiv
  * Electronic Colloquium on Computational Complexity

Blog Archive

  * V  2023 (87)
      + V  December (1)
          o Where do Non-Primitive Recursive Functions come up...
      + >  November (8)
      + >  October (8)
      + >  September (7)
      + >  August (8)
      + >  July (9)
      + >  June (6)
      + >  May (9)
      + >  April (7)
      + >  March (8)
      + >  February (8)
      + >  January (8)

  * >  2022 (77)
      + >  December (7)
      + >  November (7)
      + >  October (9)
      + >  September (6)
      + >  August (7)
      + >  July (6)
      + >  June (5)
      + >  May (6)
      + >  April (5)
      + >  March (6)
      + >  February (7)
      + >  January (6)

  * >  2021 (89)
      + >  December (6)
      + >  November (7)
      + >  October (8)
      + >  September (8)
      + >  August (9)
      + >  July (7)
      + >  June (7)
      + >  May (8)
      + >  April (8)
      + >  March (7)
      + >  February (6)
      + >  January (8)

  * >  2020 (76)
      + >  December (8)
      + >  November (7)
      + >  October (7)
      + >  September (7)
      + >  August (6)
      + >  July (6)
      + >  June (6)
      + >  May (7)
      + >  April (7)
      + >  March (9)
      + >  February (1)
      + >  January (5)

  * >  2019 (84)
      + >  December (4)
      + >  November (3)
      + >  October (8)
      + >  September (7)
      + >  August (2)
      + >  July (8)
      + >  June (9)
      + >  May (9)
      + >  April (9)
      + >  March (8)
      + >  February (8)
      + >  January (9)

  * >  2018 (100)
      + >  December (7)
      + >  November (8)
      + >  October (10)
      + >  September (8)
      + >  August (9)
      + >  July (8)
      + >  June (8)
      + >  May (9)
      + >  April (9)
      + >  March (8)
      + >  February (8)
      + >  January (8)

  * >  2017 (102)
      + >  December (7)
      + >  November (8)
      + >  October (9)
      + >  September (8)
      + >  August (9)
      + >  July (9)
      + >  June (9)
      + >  May (9)
      + >  April (9)
      + >  March (8)
      + >  February (8)
      + >  January (9)

  * >  2016 (102)
      + >  December (9)
      + >  November (8)
      + >  October (9)
      + >  September (7)
      + >  August (8)
      + >  July (7)
      + >  June (10)
      + >  May (9)
      + >  April (10)
      + >  March (8)
      + >  February (9)
      + >  January (8)

  * >  2015 (103)
      + >  December (7)
      + >  November (9)
      + >  October (9)
      + >  September (8)
      + >  August (9)
      + >  July (9)
      + >  June (10)
      + >  May (8)
      + >  April (9)
      + >  March (9)
      + >  February (8)
      + >  January (8)

  * >  2014 (111)
      + >  December (8)
      + >  November (8)
      + >  October (10)
      + >  September (11)
      + >  August (9)
      + >  July (9)
      + >  June (11)
      + >  May (10)
      + >  April (10)
      + >  March (8)
      + >  February (8)
      + >  January (9)

  * >  2013 (108)
      + >  December (9)
      + >  November (8)
      + >  October (8)
      + >  September (11)
      + >  August (9)
      + >  July (9)
      + >  June (8)
      + >  May (9)
      + >  April (10)
      + >  March (9)
      + >  February (9)
      + >  January (9)

  * >  2012 (132)
      + >  December (7)
      + >  November (9)
      + >  October (12)
      + >  September (10)
      + >  August (10)
      + >  July (9)
      + >  June (10)
      + >  May (12)
      + >  April (12)
      + >  March (15)
      + >  February (14)
      + >  January (12)

  * >  2011 (134)
      + >  December (10)
      + >  November (10)
      + >  October (12)
      + >  September (13)
      + >  August (10)
      + >  July (10)
      + >  June (14)
      + >  May (11)
      + >  April (12)
      + >  March (12)
      + >  February (11)
      + >  January (9)

  * >  2010 (191)
      + >  December (8)
      + >  November (12)
      + >  October (15)
      + >  September (14)
      + >  August (18)
      + >  July (15)
      + >  June (17)
      + >  May (20)
      + >  April (22)
      + >  March (20)
      + >  February (15)
      + >  January (15)

  * >  2009 (249)
      + >  December (16)
      + >  November (19)
      + >  October (23)
      + >  September (21)
      + >  August (21)
      + >  July (23)
      + >  June (23)
      + >  May (22)
      + >  April (21)
      + >  March (22)
      + >  February (20)
      + >  January (18)

  * >  2008 (253)
      + >  December (19)
      + >  November (18)
      + >  October (27)
      + >  September (21)
      + >  August (19)
      + >  July (22)
      + >  June (23)
      + >  May (23)
      + >  April (22)
      + >  March (20)
      + >  February (21)
      + >  January (18)

  * >  2007 (159)
      + >  December (10)
      + >  November (15)
      + >  October (18)
      + >  September (10)
      + >  August (13)
      + >  July (11)
      + >  June (8)
      + >  May (8)
      + >  April (7)
      + >  March (16)
      + >  February (20)
      + >  January (23)

  * >  2006 (238)
      + >  December (18)
      + >  November (22)
      + >  October (22)
      + >  September (19)
      + >  August (24)
      + >  July (18)
      + >  June (18)
      + >  May (18)
      + >  April (18)
      + >  March (21)
      + >  February (20)
      + >  January (20)

  * >  2005 (237)
      + >  December (18)
      + >  November (20)
      + >  October (24)
      + >  September (19)
      + >  August (22)
      + >  July (17)
      + >  June (19)
      + >  May (21)
      + >  April (19)
      + >  March (17)
      + >  February (17)
      + >  January (24)

  * >  2004 (200)
      + >  December (18)
      + >  November (16)
      + >  October (19)
      + >  September (15)
      + >  August (16)
      + >  July (15)
      + >  June (18)
      + >  May (13)
      + >  April (13)
      + >  March (17)
      + >  February (16)
      + >  January (24)

  * >  2003 (149)
      + >  December (13)
      + >  November (12)
      + >  October (15)
      + >  September (11)
      + >  August (7)
      + >  July (11)
      + >  June (13)
      + >  May (10)
      + >  April (15)
      + >  March (15)
      + >  February (11)
      + >  January (16)

  * >  2002 (76)
      + >  December (20)
      + >  November (17)
      + >  October (15)
      + >  September (18)
      + >  August (6)

Blog Roll

  * 
    Combinatorics and more
    Progress Around Borsuk's Problem
    3 hours ago
  * 
    GovAffairs
    Computing Researchers Get Crash Course in Government Advocacy at
    CRA's Leadership in Science Policy Institute (LiSPI)
    3 days ago
  * 
    11011110
    Linkage
    4 days ago
  * 
    Godel's Lost Letter and P=NP
    Thanks to Will Shortz
    1 week ago
  * 
    Shtetl-Optimized
    More Updates!
    1 week ago
  * 
    Healthy Algorithms
    AI Assistance for Pseudopeople: GPTs for configuration dicts
    2 weeks ago
  * 
    What's new
    Formalizing the proof of PFR in Lean4 using Blueprint: a short
    tour
    2 weeks ago
  * 
    Mathematical Enchantments
    Numbers Far Afield
    2 weeks ago
  * 
    Process Algebra Diary
    Eleven postdoc positions in Computer Science at the Gran Sasso
    Science Institute
    2 weeks ago
  * 
    Thoughts
    Victory in Newton MA
    3 weeks ago
  * 
    Theory Dish
    2024 Motwani Postdoc Announced
    4 weeks ago
  * 
    Windows On Theory
    Harvard, we have a problem
    5 weeks ago
  * 
    Theory Matters
    New book on Probability
    1 month ago
  * 
    Bits and Pieces
    Arthur Augustus Johnson
    3 months ago
  * 
    FYI: The AIP Bulletin of Science Policy News
    Leadership Turning Over Across DOE Science Office and National
    Labs
    5 months ago
  * 
    The Big Data Theory
    Theory Jobs 2023
    6 months ago
  * 
    in theory
    Introducing Bocconi's new M.Sc. in Artificial Intelligence
    8 months ago
  * 
    My Brain is Open
    Cryptics book is available on Amazon
    11 months ago
  * 
    Turing's Invisible Hand
    2023 SIGecom Test of Time Award -- Call for Nominations
    11 months ago
  * 
    Opinions of Doron Zeilberger

Show 10 Show All
Creative Commons License
Computational Complexity Weblog by Lance Fortnow and William Gasarch
is licensed under a Creative Commons Attribution-NonCommercial 4.0
International License. Additional permissions can be requested.
 
Powered by Blogger.