New answers tagged computability
0
I can easily write a program which given an input n, either outputs the smallest prime p > n such that p+2 is also a prime, or runs forever if no such p exists. If you can solve the problem to predict whether my program halts for every input, you just solved the Twin Prime Conjecture.
It is quite possible that this conjecture might be proven undecidable, ...
4
Rice's theorem is indeed applicable. Remember the intuitive meaning of Rice's theorem: any nontrivial property of partial computable functions either always holds, always fails, or is nonrecursive - in the sense that the set of natural numbers with that property is nonrecursive. This isn't how you've phrased it but it's a bit easier, in my opinion, to think ...
3
First, let me correct your definition of VC dimension: it is the largest size of a set which can be shattered.
If the VC dimension is $d$, then this means that for every set $C$ of size larger than $d$ there exists a function $f\colon C \to \{0,1\}$ which is not compatible with any function computed by an $n$-state Turing machine.
You are attempting to ...
1
Reversal Bounded Counter Automata have decidable equivalence. They're a fascinating class, because augmenting them in any obvious way makes one of their main properties (equivalence, emptiness, etc.) undecidable.
Oscar Ibarra's work explored their properties extensively: http://www.lsv.ens-cachan.fr/~demri/Ibarra78.pdf
If I recall correctly, visibly ...
1
Given a Turing machine $M$, we can construct another Turing machine $T$, which on input $1^n$ simulates $M$ for $\log n$ steps, and returns whether $M$ halted within these steps. The new Turing machine runs in linear time, and is equivalent to the constant time Turing machine which always returns "No" iff $M$ doesn't halt. Therefore program equivalence is ...
6
No. The Padding Lemma states that there is a primitive recursive function $\sf pad$ such that, if $n$ is a code for $f$, then ${\sf pad}(n)$ is another code for $f$ which is larger than $n$.
Therefore, if $f$ has a code, it has infinitely many.
The intuition is: if you have a TM $M$ computing $f$, you can modify the TM so that it starts with some useless ...
3
Let us actually prove more: If $L$ is a language and $L \not\in \mathsf{R}$, then $L \not\le_\mathrm{T} L'$ for any $L' \in \mathsf{R}$. (Here, $\le_\mathrm{T}$ indicates a Turing reduction; this is synonymous with your notion of a "computability" reduction.) In other words, $\mathsf{R}$ is closed under Turing reductions.
Suppose towards a contradiction ...
1
We will show that $A_{TM}$ is complete for your class.
In order to show that, we need to show that for every language $A\in L\cup \{A_{TM}\}$, it holds that $A\le_L A_{TM}$.
First, if $A=A_{TM}$, then the trivial reduction suffices. That is, a reduction that given input $x$, return $x$. Clearly $x\in A_{TM}\iff x\in A_{TM}$.
Now, if $A\in L$, we need to ...
0
Pushdown automata are nondeterministic, and there is no a priori bound on the length of computation (imagine $\epsilon$-transitions that add and remove the same element from the stack). Therefore it's not clear how to perform your simulation.
Fortunately, we know how to convert a pushdown automaton to an equivalent context-free grammar, and the latter have ...
0
As dkaeae indicated in his comment, a right-moving or staying Turing machine (TM) is essentially a finite deterministic automaton (FDA). Here's a proof.
Let $M$ be such a machine, whose transition rules is in the form of $\delta(q, \gamma)=(t, \beta, d)$ where $q$ is the current state, $\gamma$ is the contents of the current cell, $t$ is the new state, $\...
1
This inherently depends on your exact model of a TM, I'm assuming the following:
A left-bounded tape, the head starts at position 0 and the word to decide is written at the tape. Furthermore, the TM has finitely many states.
Now the TM can only look at the first symbol at a time, can do finite computation (i.e. can have finitely many transitions to ...
9
If I understand you correctly, your question is —
why a solution can be encoded by a natural number and a problem with a real number.
(I assume that you understand the next phase of the proof which is based on the difference between sets of cardinality $\mathfrak c$ and $\aleph_0$.)
The reason lies in set theory, more specifically in the cardinality ...
11
Reformulating in a more mathematically precise way, what the lecturer is trying to say is this: Any algorithm can be (uniquely) encoded as a finite string of bits, and any finite string of bits (uniquely) encodes a program; hence, there is a bijection between $\mathbb{N}$ and the set of algorithms, so both are countable sets. Conversely, having fixed an ...
6
Every algorithm can be described by a finite string, and so there are only countably many algorithms. In contrast, we can describe every decision problem as an infinite decimal in base 2, and moreover this is a surjective mapping: every number in $[0,1]$ can be "decoded" into a decision problem. Therefore there are uncountably many decision problems.
The ...
2
To simplify, let’s only speak about decision problems.
Decision problems have yes or no answers.
For example; Is X prime? Is a decision problem.
We can re-formulate the following question to be a set membership problem.
We define a language L to be the set of all prime numbers, ie the set of all strings that would make the decision problem return yes. ...
2
The language of all palindromes needs quadratic time on a single-tape Turing machine. See for example lecture notes of Eric Ruppert. The proof uses crossing sequences. In contrast, on a two-tape Turing machine, the language can be decided in linear time.
3
There are two important misunderstandings in your question.
You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it.
If a Turing machine decides a language $L$ then, by definition, it accepts every input in $L$ ...
0
Turing machines can halt or not halt. Languages cannot. The category of halting does not apply to them.
We say that a language is recursive if there is a Turing machine which always halts, and accepts exactly the words in the language. It is not the language itself which always halts, but rather the Turing machine that decides it.
In your case, the ...
0
Your enumerator is incorrect. Because there are infinitely many Turing machine descriptions in $G$, the loop corresponding to Line 3 will not halt, so i will never be increased. Also, Line 3.2 may not halt too.
The correct enumerator is:
E' =
for i = 1 to infinity:
Run E, the enumerator of G, to get the ith description of Turing machine <Mi>
...
0
As Konstantin Vladimirov said in the comment: Consider you have this program. Take any while-program and put any instruction 1000 times just before halt. Next run your program and ask if this instruction will be reached 1000 times. Bingo, halting is solved.
1
If I understand your argument correctly, you are reducing languages in the wrong direction.
If $L$ is not context-free, then $K$ is not context-free.
Is equivalent to
If $K$ is context-free, then $L$ is context-free.
We have to reverse the construction, as we are using the closure properties of the context-free languages. In do not know of any useful ...
1
Let us check the first part, $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$ where $m>n>o>0$, $i_1,i_2,...,i_{2m} \geq 0$, $j_1,j_2,...,j_{2n} \geq 0$, $k_1,k_2,...,k_o \geq 0$. Note the "where" clause means $\#_b(w)$ and $\#_e(w)$ are even and $\#_b(w)>\#_e(w)>2\#_h(w)$.
Assume $L$...
2
Start with a long enough string $w$ in $L$ in which $m=p+2,n=p+1,o=p$ and
$i_1,...,i_{2m}=0$
$j_1,...,j_{2n}=0$
$k_1,...,k_{o}=0$
$w = a\; b^{2(p+2)}\; d\; e^{2(p+1)}\; g\; h^{p} $
Then apply pumping lemma (it should be easier ;-).
If you want to "reduce" $L$ to $L' = \left\{0^i1^j2^k|1\le \:i<j<k\right\}$ then you must use closure properties, in ...
2
A stronger result than Turing's halting problem is Rice's theorem: the determination of any nontrivial property of programs is undecidable.
To be precise, that's a semantic property, i.e. any property of programs determined by their behavior and independent of exactly how the program is expressed: the property has to have the same value for any two programs ...
2
Is that proof correct?
Let's assume f is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size.
This TM works as following:
Using blackbox for f, calculate f(n)
Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {_, 0, 1, .... n}
...
0
We can enumerate all possible inputs, giving them numbers 1, 2, 3, 4, ...
We can then write a program that systematically checks if one of the first n inputs is accepted in n steps, for n = 1, 2, 3 etc. This will in finite time find the input that halts.
I wasn't qute sure if I would call the approach of user679128 to be "cheating" since the question was ...
1
No
Finite Automata are not Turing Complete because they have a limited amount of memory. If that limit of memory were to be removed, the Finite Automaton in question would be Turing Complete.
Let's take a Finite Automaton which is a Turing Machine except it is restricted to 10 states. This would not be able to be Turing Complete because it wouldn't be able ...
Top 50 recent answers are included
