My understanding is since it is not computable, it may not halt when the answer is 'yes' or 'no'. That's why it cannot be co-recursively enumerable since it can't guarantee it always halts on 'no'.
Something is not computable, can it be co-recursively enumerable?
381 Views Asked by sharprabbitz At
1
There are 1 best solutions below
Related Questions in TURING-MACHINES
- Understanding Unary PCP Reduction to a Matching Problem (UPCP)
- Build a Turing Machine that counts a's and b's
- Language for Turing Machine
- Unable to export Chains class from Julia's Turing library
- Complicated, long equations in MCMC [Julia, Turing.jl]
- Turing Pattern Formation
- Is there a way to prove that the intersection of a decidable language and a recognizable language is also recognizable?
- binary search with JFLAP turing machine
- python - 3 Turing Machine script, getting errors on an undefined variable, even though I assigned it
- Prove that the following problem is undecidable by a reduction from the halting problem:
- Construct a Turing Machine that halts on an unbroken string of 1s
- Jump to a specific vector place if a condition is met and start reading it from there
- Binary to unary turing machine
- How to generate an Unrestricted grammar if a language defination is given
- Can we assure a strictly decreasing function is computable?
Related Questions in COMPUTABILITY
- Prove that the following problem is undecidable by a reduction from the halting problem:
- Can we assure a strictly decreasing function is computable?
- Why do we define equivalent turing machines as two turing machines with the same accepted languages?
- Disjunctive Normal Form and satisfiable is in P (DNFSAT)
- Make the assumption that P = NP
- Equality between two propositions nat -> nat
- Inputs to Program to Illustrate Halting Problem
- "Reduction" from the complement of the universal language (L_u) to the language of nonempty-language Turing machines (L_ne)
- How to define a function with Church numerals in lambda-terms?
- How to define a coding function for all finite subsets of N?
- Proving the inexpressibility of a function in a given language
- proving that a language is part of a grammar and vice versa
- How do you prove whether a simple unmeaningful code is computable or not?
- What is the most concise way to generate strings of language anbncn using JavaScript without using loops?
- Turing machines and decidability
Related Questions in DECIDABLE
- I have two types that should be semantically identical. Why is one resulting in an error while the other one gets accepted?
- Applying Reflexivity of String Equivalence in Agda Proofs
- Are linear problems on rational numbers decidable in Z3?
- Z3: is Nonlinear integer arithmetic undecidable or semi-decidable
- Is "less than" for rational numbers decideable in Coq?
- Prove that we can decide whether a Turing machine takes at least 100 steps on some input
- Recognizabilty of a set in regards to their size bounds
- Recursive vs recursively enumerable language in Turing Machines?
- Undecidable if TM overwrites its input?
- Looking for the Agda module that contains decidable equality for lists
- "Reduction" from the complement of the universal language (L_u) to the language of nonempty-language Turing machines (L_ne)
- Is a given TM having finite states is decidable or not?
- reduction from ALLtm to Etm
- How to define a subformula of an inductively defined type in Agda?
- Turing machines and decidability
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
A problem can be uncomputable but still be co-recursively enumerable.
Computable, decidable, or recursive sets have TMs which can always halt by either accepting or rejecting any input.
Uncomputable sets can still be semidecidable, recursively enumerable or co-recursively enumerable if they have TMs which can halt by accepting everything in the set (while possibly failing to halt at all when the input isn't in the set) or by rejecting everything that's not in the set (while possibly failing to halt at all when the input is in the set).
Clearly, if a set is both recursively enumerable as well as co-recursively enumerable, it is recursive (computable, decidable) since you can run both TMs - one that eventually halts by accepting, the other one that eventually halts by rejecting - and you know one of the two will eventually give you the correct answer.