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
Enderton Computability Theory - Calculation of Semi-characteristic Function - Implicit Use of Infinity?
Enderton computability Theory (2011), p66 on kindle states :
Let K be the domain of the diagonal function K = {x | $[x](x) \downarrow$} ( with [x] being a register machine indexed by x, with input data (x) and $\downarrow$ means the machine halts…
user239186
0
votes
1 answer
Give mapping for any alphabet
I am lookng at a suggested solution of the following:
For any alphabet $\Sigma$ give a $1-1$ mapping with $\mathbb{N}_0$ into $\Sigma^{\ast}$.
That's the suggested solution:
Let $\Sigma=\{0,1\}$.
Let $w \in \Sigma^{\ast}$, where $w=\alpha_0 \alpha_1…
Evinda
- 1,460
0
votes
2 answers
Reducing Pcp (Post's correspondence problem) to mPcp
Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version requires any matching sequence of "dominoes"…
0
votes
0 answers
Simulating a k state Turing machine M would require a Turing machine M' that has some f(k) number of states
I am writing a proof for a problem, and in that proof, I am simulating a TM M that has k states and terminates after being started on a blank input. I want to show that to simulate M on a TM M', M' would have f(k) number of states, where f is a…
Jay Hu
- 1
0
votes
2 answers
Why are recursive sets also recursively enumerable?
Why is this? I'm not necessarily interested in a full proof, but just a quick, simple explanation that makes sense as to why this is.
yuopiop
- 37
0
votes
1 answer
There are infinitely many recursively enumerable subsets of the natural numbers which are not recursive
How do I prove this claim? I understand that there are countably many recursive as well as recursively enumerable sets, and that the natural numbers have uncountably many subsets.
azureai
- 1,772
0
votes
1 answer
A subset of $ \mathbb{N}$ is recursively enumerable iff it is the range of some recursive function from $\mathbb{N }$ to $\mathbb{N}$.
I know how to prove the converse of the statement, but given a recursively enumerable set, I don't know how to find such a recursive function.
Also, how to prove that the function can be chosen as injective if the set is infinte?
user280486
0
votes
1 answer
Explain why these sets are recursive or r.e.
A set $A \subseteq \mathbb N$ is recursive. Working from an informal idea of "computability" explain why the set
$B = \big\{ x \in \mathbb N : \exists u,v \in A, u+v=x \big\}$
is recursive and the set
$C = \big\{ x \in \mathbb N : \exists u,v \in A,…
AXN153
- 1
0
votes
1 answer
What does it mean to prove a problem cannot be solved by a Turing machine?
You sometimes see claims that no Turing machine exists which solves a particular problem, for example, no Turing machine exists which, given an arithmetic statement, outputs correctly either "true" or "false" (according to the accepted answer…
Jack M
- 27,819
- 7
- 63
- 129
0
votes
2 answers
A problem that is Turing degree greater than $0'$ and not co-re
I know that halting problem is Turing degree $0'$.
So, what degree would Co-RE complete problems be in?
And is there any problem we can formulate (<- this might be too general, but let us say in terms of writable problems) or think of that has…
user2346
- 631
- 2
- 7
- 14
0
votes
1 answer
enumerability exercise in boolos book
problem 2.2 of Computability and Logic written by Boolos(p.20, fifth edition)
Show that if for some or all of the finite strings from a given finite or enumerable alphabet we associate to the string a total or partial function from positive integers…
fbg
- 861
0
votes
1 answer
Creating ways to encode recursive function.
This is from an exercise in Boolos' Computability text. My problem is as follows:
I am looking for a method that encode numbers for recursive functions.
Then given such an encoding for recursive functions by natural numbers, let d(x) = 1 if the…
Quaternary
- 583
0
votes
1 answer
there is no partial recursive function f s.t. whenever N-W_e has one element, f converges and N-W_e = f(e)
question is as written in the title:
show that there is no partial recursive function f s.t. whenever N-W_e has one element, f converges and N-W_e = {f(e)}.
W_e is the domain of the program coded by e.
So if there is a converging function f such…
John Lee
- 13
0
votes
3 answers
Rice's Theorem when only finite number of instructions run
Rice's theorem says that there is no computable method F(m,p) to determine, if given as input a TM m, and some non-trival property p, if the language accepted by m has property p. To quote another source, "...you can infer from Rice's Theorem…
Bill Cody
- 33
0
votes
1 answer
A revisit to the question: Can total recursive functions be recursively enumerated?
There is not a clear answer in literature on the question: Can total computable functions be computable enumerated?, i.e., is a set of encodings of total computable functions computably enumerable (c.e.)? On the shaking ground, I am tossing an…
