Linked Questions

1 vote
0 answers
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 ...
user1730118's user avatar
36 votes
8 answers
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. ...
MaiaVictor's user avatar
  • 4,137
45 votes
2 answers
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 ...
user5507's user avatar
  • 2,191
42 votes
2 answers
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 ...
Squidly's user avatar
  • 531
12 votes
1 answer
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 ...
Andrey Lebedev's user avatar
9 votes
4 answers
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 ...
Stefan Lutz's user avatar
8 votes
3 answers
519 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 ...
magnetar's user avatar
  • 201
3 votes
2 answers
881 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 ...
advocateofnone's user avatar
5 votes
5 answers
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 ...
agemO's user avatar
  • 177
7 votes
2 answers
384 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 ...
Joey Eremondi's user avatar
3 votes
3 answers
256 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 ...
Novellizator's user avatar
2 votes
2 answers
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 ...
shane's user avatar
  • 195
2 votes
2 answers
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 ...
user avatar
2 votes
2 answers
773 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 ...
Valentin Tihomirov's user avatar
1 vote
2 answers
279 views

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
1 vote
1 answer
669 views

Is the set of Gödel numbers of computable constant functions recursively enumerable?

I've been working on the following exercise: $S = \{ x | f_x \text{ is constant} \}$. Is $S$ recursively enumerable? Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a ...
PALEN's user avatar
  • 327
2 votes
1 answer
752 views

Why does my answer sheet say the set of computable functions is uncountable?

I'm trying to understand why I can't find room for the set of computable functions in the hotel of the Hilbert's Hotel Paradox. I was thinking that, because Gödel numbering, I could consider the set ...
estebarb's user avatar
  • 152
0 votes
0 answers
478 views

What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
André Souza Lemos's user avatar
3 votes
1 answer
117 views

Total functional computable real numbers

Is there any computable real number which can not be computed by a higher order primitive recursive algorithm? For computable real number I mean those that can be computed by a Turing machine to any ...
user3368561's user avatar
1 vote
1 answer
159 views

Does every r.e. set containing the set of total recursive functions contain all partial recursive functions?

Any r.e. subset of $A\subseteq\mathbb{N}$ which contains the set $$\mathrm{Tot}=\{i\mid i\ \mbox{is an index of a total function } f\}$$ must, by a standard argument (of Post?) contain some partial ...
cody's user avatar
  • 8,233
3 votes
1 answer
148 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
oconnor0's user avatar
  • 393
7 votes
0 answers
41 views

Is there any type system which can assign a type to any halting lambda calculus term? [duplicate]

Some lambda terms, such as the church number 3: (f x -> (f (f (f x)))), are easily typeable on the simply typed lambda calculus. Others, such as ...
MaiaVictor's user avatar
  • 4,137
0 votes
0 answers
50 views

Is there a broader class of total functions than $PR$? [duplicate]

In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann ...
Peter's user avatar
  • 361