Linked Questions

1 vote
1 answer

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

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

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

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

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

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

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

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

15 30 50 per page