Tagged Questions
1
vote
2answers
120 views
Decidability and undecidability of a set or language
I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing ...
2
votes
1answer
127 views
Injection from computable numbers into natural numbers
Each Turing machine which writes an infinite sequence of 1 and 0 can be regarded as
representing a (computable) real number (and of course each Turing machine represents a natural number by its ...
2
votes
1answer
146 views
Is this undecidable language recognizable?
Is this language:
$L = \{\langle M\rangle : \text{$M$ is a Turing machine and $L(M)$ is decidable}\}$
which I know that is undecidable, turing-recognizable?
Is its complement recognizable?
...
1
vote
2answers
93 views
Turing machine for balancing parentheses on a two letter alphabet
How to construct a Turing machine $M=(Q,\Gamma,b,\Sigma,\delta,q_0,F)$ which decides if a sting on the alphabet $\{(,)\}$ is ''balanced'' (e.g. $(()())$ is balanced and $))(($ or $()(($ is not) with ...
-2
votes
1answer
103 views
Computability of busy-beaver sequence? [closed]
We can draw a parallel between cellular automata and busy-beaver numbers.
For example the initial case occupies some kxk square in the plane,leaving all the other cells emty, after how many ...
6
votes
2answers
80 views
Are there known natural problems of intermediate degrees of unsolvability?
I know there exist intermediate degrees of unsolvability, i.e. there are undecidable problems which can be reduced to the Halting Problem, but not vice versa. Are there any "natural" problems known or ...
3
votes
1answer
57 views
Explain why if the language A is recursive, then A is reducible to 0*1*
I'm in a theory of computation class and there is a problem that I think I am way overthinking.
Can anyone point me in the right direction with the following:
Give a short justification of the fact ...
1
vote
1answer
90 views
The set of Turing machines that recognize $\{00, 01\}$ is undecidable
$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable.
I am really having difficulties even understanding the reduction to use ...
4
votes
1answer
103 views
Question about $\Sigma_n$-soundness
According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
2
votes
2answers
133 views
I do not understand why the Turing computable sets of N are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy
The reason I don't understand it is this. Take for example the twin primes conjecture, which is $\Pi_2^0$. The set of twin primes is computable right? (there is a Turing machine that enumerates all of ...
1
vote
1answer
364 views
Language that is recursively enumerable, but not recursive
I have a problem with this task:
Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
12
votes
2answers
258 views
How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?
This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound:
"... in the context of ordinary ...
