Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).
Questions tagged [computability]
2395 questions
0
votes
1 answer
Index Sets are Cylinders
A cylinder is a set of the form $C\times \mathbb{N}:=\{\langle c,n \rangle \ | \ c\in C\}$. I want to prove that
Every index set $C$ is computably isomorphic to a cylinder.
My attemp: Since $C\leq_1 C\times\mathbb{N}$ (1-1 reducible) by Myhill…
xyz
- 929
- 4
- 12
0
votes
0 answers
Implementing the function $f(x)=\left[ 2x/3 \right]$ on Unlimited Register Machine
I am reading Cutland's "Computability: An Introduction to Recursive Function Theory". In Exercise 3 of Page 22, Cutland asks to prove that the function $f(x)=\left[ 2x/3 \right]$ is computable on Unlimited Register Machine.
Here's my idea of my…
ashK
- 3,985
0
votes
1 answer
Wikipedia's definition of a computable numbers
According to Wikipedia,
computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm.
I'm somewhat confused here. I always thought that given some fixed number of decimal places…
0
votes
0 answers
A function that calculates the number of lines of code is computable?
How to prove that a function that accepts any argument and outputs the number of lines of code in its program is computable on Unlimited Register Machines. It seems like one should use the recursion theorem, but I don't quite understand how. Or…
sana
- 1
0
votes
1 answer
Is there any infinitesimal number both definable and computable?
Suppose we take for example the smallest number strictly greater than 0 (which in the conventional real number system realm doesn't exist but in some other number systems does (e.g the hypereals).
Well it's clearly defined (we just have), but we…
user403504
- 49
- 3
0
votes
1 answer
Does the definite description operator generate all general recursive functions?
Suppose, instead of adding the $\mu$ operator to the primitive recursive functions, we add the definite description operator. For a given relation $R$, the definite description operator returns the unique natural number that satisfies $R(y)$. Let us…
user107952
- 20,508
0
votes
1 answer
When formulating general recursive functions, did Godel knew that they correspond to effectively calculable functions?
...or did it only became apparent after Church's thesis (which asserted that lambda-definable functions and recursive functions are equivalent) and subsequent Turing's thesis? It is known that Godel was not impressed with lambda calculus, does it…
Siegmeyer
- 263
0
votes
0 answers
The family $\text{CF} \cup \left\lbrace \omega \right\rbrace$ is not computable.
I've got an interesting task from my friend and didn't understand, how to prove that:
The family $\text{CF} \cup \left\lbrace \omega \right\rbrace$ is not computable.
$\text{CF}$ is the family of all graphs of computable functions.
$\left\lbrace…
Legat
- 1
0
votes
2 answers
How to write a program from a predecessor function using only the clear, successor, copy, for loop and while loop commands?
This is a question from the first chapter of Herbert Endertons Computability book
I've been stuck on it since yesterday and its been driving me crazy. The basic commands from this language are as follows:
1) x <- 0 - to assign the value 0 to x
2) x…
0
votes
0 answers
Indexed family of all unary partial computable functions. The existence of computable numbering
Please help prove the following statement:
The indexed family of all unary partial computable functions that have total computable extension is computable.
Definitions:
Total function - a function which is defined for all inputs of the right…
T uS
- 1
0
votes
1 answer
Computable decision problem versus non-computable function problem
Consider the function problem find_solution(input) -> output, and the decision problem solution_exists(input) -> yes_or_no. Is there any problem that is computable in its decision problem form, but not computable in its function problem form?
In…
ABu
- 451
- 2
- 9
0
votes
0 answers
Is this function computable? Is this reduction correct?
Let $A$ be a set, $K=\{x:\phi_x(x)\downarrow\}$. Let c to be a total computable function such that $\phi_{c(x,y,n)}(z)=\begin{cases}\phi_n(z) & \text{if }\phi_x(y)\downarrow\\\uparrow &\text{otherwise}\end{cases}$
Suppose $\forall x,y\exists…
0
votes
1 answer
Relationship between existence and computable function
Let $A$ be a set, $K$ a non recursive set, and a total computable function $g$ such that $\forall x\exists n.x\in K \Leftrightarrow g(x, n)\in A$.
The question is if the function:
$f(x)=a$ such that $x\in K \Leftrightarrow g(x, a)\in A$
is total…
0
votes
1 answer
The property of being an index set is not computably invariant
Let $\omega$ denote the set of natural numbers including $0$.
Definition 1. Let $A\subseteq \omega$. Then we call $A$ to be an index set if the following holds, $$\forall x\forall y((x\in A\land \varphi_x\equiv \varphi_y)\implies y\in A)$$where…
user170039
0
votes
1 answer
Is there a computable infinite set of natural numbers all of whose computable subsets are either finite or cofinite?
I was reading about amorphous sets recently and I thought the idea was quite intriguing, but couldn't come up with any natural example of one (perhaps because the existence of one implies the falsehood of Choice).
Setting my sights lower to include…
