Linked Questions

1 vote
0 answers

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 ...
user1730118's user avatar
35 votes
7 answers

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. ...
MaiaVictor's user avatar
  • 4,127
45 votes
2 answers

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 ...
user5507's user avatar
  • 2,191
42 votes
2 answers

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 ...
Squidly's user avatar
  • 531
12 votes
1 answer

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 ...
Andrey Lebedev's user avatar
9 votes
4 answers

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 ...
Stefan Lutz's user avatar
8 votes
3 answers

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 ...
magnetar's user avatar
  • 201
3 votes
2 answers

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 ...
advocateofnone's user avatar
5 votes
5 answers

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 ...
agemO's user avatar
  • 177
7 votes
2 answers

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 ...
Joey Eremondi's user avatar
3 votes
3 answers

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 ...
Novellizator's user avatar
2 votes
2 answers

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 ...
shane's user avatar
  • 195
2 votes
2 answers

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 ...
user avatar
2 votes
2 answers

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 ...
Valentin Tihomirov's user avatar
1 vote
2 answers

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 ...
Elimination's user avatar

15 30 50 per page