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
    The notion of a computable set generalizes effective deci... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    The notion of a computable set generalizes effective decidability: a relation R is computable just in case there is an algorithm for deciding whether R holds of any tuple of natural numbers that always returns an answer after a finite (though potentially unbounded) number of steps

    Proof of definition segmentsTruth & 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.Church's Thesis equates computability with effective algorithmic decidability
      ?

      Think about whether this reason is strong or weak

    • 2.Primitive recursive relations are computable
      ?

      Think about whether this reason is strong or weak

    • 3.A computable set is one decidable by an algorithm that always terminates in finitely many steps
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Hypercomputation models (Malament-Hogarth spacetimes, Turing's o-machines) permit decision procedures that transcend finite-step termination constraints.
      ?

      Think about whether this reason is strong or weak

    • 2.If physically realizable processes can decide undecidable sets, then 'computable' cannot be conceptually identified with finite-step algorithmic decidability sans further qualification.
      ?

      Think about whether this reason is strong or weak

    • 3.Church's Thesis is an empirical conjecture about physical computation, not a logical necessity, as Copeland and Proudfoot argue, leaving the definition stipulative rather than revelatory.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Wittgenstein's rule-following considerations entail that no finite symbolic procedure fixes a unique interpretation of 'algorithm,' undermining the determinacy of 'always returns an answer.'
      ?

      Think about whether this reason is strong or weak

    • 2.If the extension of a computable relation depends on how we interpret the algorithm's steps, then effective decidability is norm-relative rather than a mind-independent mathematical fact.
      ?

      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 & KnowledgeProof of definition segments

    Key Terms

    Effective decidability(logic and computability theory)
    The quality of being able to determine whether something is true or false using a clear, mechanical procedure that will always give you an answer eventually.
    Natural numbers(mathematics)
    The counting numbers: 1, 2, 3, 4, and so on (sometimes including 0, depending on context).
    Relation (in mathematics)(logic and mathematics)
    A connection or rule that links items together—for example, 'is greater than' is a relation that can connect pairs of numbers.
    Tuple(mathematics and logic)
    An ordered list or sequence of items—for example, (3, 5, 7) is a tuple of three numbers.
    algorithm(Philosophy of computation and information)
    A fundamental concept in information and computation theory, accepted as a primitive notion alongside data set
    computable set(Extends the definition of primitive recursive relation via Church's Thesis)
    A relation R is computable just in case there is an algorithm for deciding whether R(n-vector) holds that always returns an answer after a finite, although potentially unbounded, number of steps

    Related

    A computable set is one decidable by an algorithm that always terminates in fini...Church's Thesis equates computability with effective algorithmic decidabilityChurch's Thesis is an empirical conjecture about physical computation, not a log...Hypercomputation models (Malament-Hogarth spacetimes, Turing's o-machines) permi...
    +4 moreShow less
    If physically realizable processes can decide undecidable sets, then 'computable...If the extension of a computable relation depends on how we interpret the algori...

    Source

    AI-extracted1/3 agreementValid
    SEP: recursive-functions
    View source passageHide passage
    This definition extends the definition of a primitive recursive relation given in Section 2.1—e.g., since sets like PRIMES and DIV are primitive recursive they are ipso facto computable. Via Church’s Thesis, the notion of a computable set thus also generalizes the accompanying heuristic about effective decidability—i.e., \(R\) is computable just in case there is an algorithm for deciding if \(R(\vec{n})\) holds which always returns an answer after a finite (although potentially unbounded) numb
    Extraction notes

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

    Details

    Primitive recursive relations are computable
    Wittgenstein's rule-following considerations entail that no finite symbolic proc...

    Similar

    A computable set is one decidable by an algorithm that always terminat...88%Church's Thesis equates computability with effective algorithmic decid...85%Proposition 3.5 states that if a set A is reducible to a computable (o...83%A problem is effectively decidable only if its characteristic function...82%
    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit