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
    If a model of computation does not natively support recur... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Causation
    HistoryEditSee Inverse

    If a model of computation does not natively support recursion, then defining a function h(y) by primitive recursion over a base function g(y) computable in that model provides no a priori assurance that h(y) is itself computable in that model.

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

    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.

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.Models of computation such as the Turing Machine and Unlimited Register Machine do not natively support recursion as a mode of computation.
      ?

      Think about whether this reason is strong or weak

    • 2.For models that do support primitive recursion, a unique function h(y) satisfying a primitive recursion equation can be shown to exist via external set-theoretic argument.
      ?

      Think about whether this reason is strong or weak

    • 3.Simply setting down a recursive definition does not, by itself, establish computability within a given model.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Church's Thesis entails that any function intuitively computable by a finite procedure is computable by a Turing Machine, regardless of definitional form.
      ?

      Think about whether this reason is strong or weak

    • 2.Primitive recursion is a paradigm case of finite, effective procedure, so any function defined by it over a computable base is already Turing-computable by Church's Thesis.
      ?

      Think about whether this reason is strong or weak

    • 3.Therefore, the claim that primitive recursion over a computable base provides 'no a priori assurance' of computability conflates formal proof within a model with the broader epistemological warrant supplied by Church's Thesis.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Kleene's Normal Form Theorem shows every partial recursive function is expressible via bounded minimization over a primitive recursive predicate, establishing a structural bridge between recursion-theoretic and machine-based models.
      ?

      Think about whether this reason is strong or weak

    • 2.Because this bridge is proven rather than merely conjectured, a function defined by primitive recursion over a computable base inherits computability in any model proven equivalent to the recursive functions, removing the alleged 'a priori' gap.
      ?

      Think about whether this reason is strong or weak

    • 3.The supporting arguments conflate the absence of native recursion syntax in a model with the absence of semantic equivalence, but proven inter-reducibility of models dissolves that gap at the level of extensional computability.
      ?

      Think about whether this reason is strong or weak

    Topics

    CausationTruth & Knowledge

    Key Terms

    a priori(Frege treats 'analytic' as entailing 'a priori' for arithmetic.)
    Knowable independently of empirical experience; here treated as a consequence of analyticity.
    base function(in mathematical recursion)
    The starting function or simplest operation that serves as the foundation for building more complex functions.
    computable(As employed in the technical literature discussed in this passage)
    Computable by an effective method
    model of computation(in computer science and logic)
    A theoretical system that describes how a computer or mathematical machine could solve problems; different models have different capabilities and rules.
    primitive recursion(computability theory / recursive function theory)
    A restricted kind of recursion in which a function h with first argument n+1 is defined in terms of h with first argument n, with all other arguments unchanged.
    recursion(HCF's characterization of the core property of FLN)
    A cognitive universal capacity posited by HCF that underlies not only natural language but also arithmetic (counting and the successor function), and possibly navigation and social relations; not defined over specifically linguistic inputs and outputs.

    Connections

    2 topics

    Modality & Possibility2 linkedMoral Responsibility1 linked

    Related

    Because this bridge is proven rather than merely conjectured, a function defined...Church's Thesis entails that any function intuitively computable by a finite pro...

    Source

    AI-extracted1/3 agreementValid
    SEP: recursive-functions
    View source passageHide passage
    In the case that \(f(y)\) and \(g(y)\) are primitive recursive, we have remarked that it is possible to show that there exists a unique function \(h(y)\) satisfying (\ref{recex}) by an external set-theoretic argument. But we may also consider the case in which \(g(y)\) is assumed to be computable relative to a model of computation \(\mathbf{M}\) which differs from the partial recursive functions in that it does not natively support recursion as a mode of computation—e.g., the Turing Machine mode
    Extraction notes

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

    Details

    For models that do support primitive recursion, a unique function h(y) satisfyin...
    Kleene's Normal Form Theorem shows every partial recursive function is expressib...
    +5 moreShow less
    Models of computation such as the Turing Machine and Unlimited Register Machine ...Primitive recursion is a paradigm case of finite, effective procedure, so any fu...Simply setting down a recursive definition does not, by itself, establish comput...The supporting arguments conflate the absence of native recursion syntax in a mo...Therefore, the claim that primitive recursion over a computable base provides 'n...

    Similar

    If all effectively computable functions are recursive, then any functi...86%Simply setting down a recursive definition does not, by itself, establ...83%For models that do support primitive recursion, a unique function h(y)...83%Models of computation such as the Turing Machine and Unlimited Registe...82%
    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit