Skip to content
Carmelics
TopicsThinkersChangesContributorsLoading account…

    Carmelics

    A reasoning platform. Break down any belief into clear reasons, explore both sides, and weigh the evidence honestly.

    Navigate

    • Topics
    • Search
    • Recent Changes
    • Contribute
    • How It Works
    • Glossary
    • Thinkers
    • Contributors
    • About
    • Statistics
    • Terms
    • Privacy

    Database

    Statements
    —
    Perspectives
    —
    Topics
    —

    Press ? for keyboard shortcuts

    LoyalLoyalJusticeJustice
    Made withinDC&Austin
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Feasibility of computation is preserved when a function i... — Carmelics
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    Feasibility of computation is preserved when a function is defined by limited recursion on notation

    All sources support itTruth & Knowledge
    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    2 reasons against

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.The basis functions F_0 are feasibly computable
      ?

      Think about whether this reason is strong or weak

    • 2.Feasibility is preserved under composition of functions
      ?

      Think about whether this reason is strong or weak

    • 3.Limited recursion on notation recurses on the binary length of y — proportional to log_2(y) — rather than on the value of y itself as in ordinary primitive recursion, so the number of recursive steps is bounded by the bit-length of the input
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The bound on recursive steps being logarithmic does not bound the size of intermediate values computed during those steps.
      ?

      Think about whether this reason is strong or weak

    • 2.If intermediate values grow polynomially or worse, the total bit-complexity of the computation may escape feasibility even with few recursive steps.
      ?

      Think about whether this reason is strong or weak

    • 3.Cobham's original framework requires bounding both the number of steps and the bitwidth of values; limited recursion on notation alone addresses only the former.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Feasibility is a semantic, resource-sensitive notion tied to actual physical computation, not merely a structural property of definitional schemes.
      ?

      Think about whether this reason is strong or weak

    • 2.A function class closed under limited recursion on notation can still contain functions whose constants or basis functions encode infeasible computations in their descriptions.
      ?

      Think about whether this reason is strong or weak

    • 3.As Slot and van Emde Boas argued, the choice of machine model and encoding can shift the boundary of feasibility independently of the recursion-theoretic characterization.
      ?

      Think about whether this reason is strong or weak

    Sign in or register to share your perspective on this statement.

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.

    Topics

    Truth & KnowledgeAll sources support it

    Connections

    2 topics

    Proof of definition segments1 linkedCausation1 linked

    Related

    A function class closed under limited recursion on notation can still contain fu...As Slot and van Emde Boas argued, the choice of machine model and encoding can s...Cobham's original framework requires bounding both the number of steps and the b...Feasibility is a semantic, resource-sensitive notion tied to actual physical com...
    +5 moreShow less
    Feasibility is preserved under composition of functionsIf intermediate values grow polynomially or worse, the total bit-complexity of t...Limited recursion on notation recurses on the binary length of y — proportional ...

    Similar

    Feasibility is preserved when a function is defined by limited recursi...95%Feasibility is preserved under limited recursion on notation88%Limited recursion on notation constrains the growth of function values...82%In limited recursion on notation, the recursion depth is proportional ...81%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    A first link between formal arithmetic and complexity was provided by Cobham’s (1965) original characterization of \(\textbf{FP}\) in terms of a functional algebra similar to that by which the primitive recursive functions are defined. 1 The function \(f(\vec{x},y)\) is said to be defined from \(g(\vec{x}), h_0(\vec{x},y,z), h_1(\vec{x},y,z)\) and \(k(\vec{x},y)\) by limited recursion on notation just in case \[ \begin{aligned} f(\vec{x},0) &= g(\vec{x})\\ f(\vec{x},s_0(y)) &= h_0(\v
    Extraction notes

    Validity: Extracted via Max plan + API grounding/validity checks

    Details

    The basis functions F_0 are feasibly computable
    The bound on recursive steps being logarithmic does not bound the size of interm...
    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit