23 questions linked to/from Why are the total functions not enumerable?
1 vote
286 views

### Show that the language of all total Turing machines is neither r.e. nor co-r.e [duplicate]

I've been thinking about how to show this but I'm stuck. I'm required to prove this: Show that the language \mathrm{TOT}= \{\langle M \rangle : M\text{ is a Turing Machine that halts with all ...
11k views

### What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
• 4,159
22k views

### How to show that a function is not computable? How to show a language is not computably enumerable?

I know that there exists a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
• 2,201
8k views

### What can Idris not do by giving up Turing completeness?

I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types? I guess this is quite a specific ...
• 531
4k views

### Example of unrestricted grammar which produces non-context-sensitive language

I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$. I can not find any ...
1k views

### Implications of Rice's theorem

Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong. Lets take some non-trivial property of the set of ...
• 535
522 views

### Simple explanation as to why certain computable functions cannot be represented by a typed term?

Reading the paper An Introduction to the Lambda Calculus, I came across a paragraph I didn't really understand, on page 34 (my italics): Within each of the two paradigms there are several versions ...
• 201
895 views

### Is the language of TMs that decide some language Turing-recognizable?

Is the language $\qquad L=\{ \langle \text{M} \rangle \; | \; \text{M is a Turing machine that decides some language} \}$ a Turing-recognizable language? I think it's not, as, even if I am able ...
• 2,992
2k views

### Proof that total computable functions are not enumerable

In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made: Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all ...
• 177
386 views

### Is there an always-halting, limited model of computation accepting $R$ but not $RE$?

So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages. I'm wondering, is ...
• 29.9k
261 views

### Why we cannot prove that a computable function is total?

We know that we cannot find an algorithm that would prove that a computable function "f" is total if it IS total. How come? When a function is total, it must have a proof (derived from soundness and ...
• 133
1k views

### Recursive language subtracted from recursively enumerable language

This is a homework problem but I am awfully confused. The problem reads as follows: If $L_1$ is recursively enumerable but not recursive, and $L_2$ is recursive, then which of the following is the ...
• 195
1k views

### How to prove that "Total" is not recursive (decidable)

$\mathrm{Halt} = \{ (f,x) | f(x)\downarrow \}$ is r.e. (semi-decidable) but undecidable. $\mathrm{Total} = \{ f | \forall x f(x)\downarrow \}$ is not r.e. (not even semi-decidable). I need some help ...
794 views

### Ambiguity vs. context-sensitivity

It is said that attributes supply some semantic information to the grammar. Meantime, the same attributes let you to resolve ambiguities. Text books agree that it is worth haveing a CF grammar which ...
1 vote
### Is an infinite language of halting TM is in $RE$? in $RE \setminus R$?
Let an infinite language, $L$, which contains only TM which halt for every input (meaning, decides some language). Is $L$ in $R$ ? in $RE \setminus R$ ? I've understood that the answer is: it ...