23 questions linked to/from Why are the total functions not enumerable?
1 vote
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 ...
• 327
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 ...
• 152
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, ...
• 3,276
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 ...
• 485
1 vote
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 ...
• 8,233
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 ...
• 393
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 ...
• 4,137
### 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 ...