22
votes
How to determine if a set is countable or uncountable?
Some common approaches to prove that some set is countable:
Give an enumeration, i.e. a list that contains all of the elements of the set. It's fine if the list contains duplicates.
Show that it is a ...
- 23.8k
21
votes
Accepted
Is the infinite language unrecognizable in a Turing machine?
I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable.
A language is ...
- 7,176
20
votes
Accepted
Halting problem theory vs. practice
Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of ...
- 3,800
20
votes
Does contradiction definitively prove nonexistence
A proof is a proof, even if the system you work in is inconsistent.
So if you prove that the existence of a decider leads to contradiction, you have proved that such a decider does not exist. If in ...
- 31.2k
19
votes
Probabilistic methods for undecidable problem
So, we have a TM $M$ that can in addition flip a fair coin. We have the promise that for every input $M$ will eventually halt and give an answer, no matter what the coin results are. Moreover, we ...
- 3,293
14
votes
Accepted
The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?
The language
$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$
is not an index set, that is it is not of the form
$\qquad L_P = \{ \langle M \rangle \mid M \text{ is ...
- 72.9k
14
votes
What does it mean to prove the halting problem is undecidable "using arithmetization"?
I would guess/assume that by "arithmetization", they mean the concept that every Turing machine can be associated with a bit-string or natural number (the fact that we can encode a ...
D.W.♦
- 166k
12
votes
Accepted
Dovetailing in Turing Machines?
Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time.
Why is dovetailing useful? Here is one ...
- 279k
12
votes
What are the conditions necessary for a programming language to have no undefined behavior?
First off, let's be clear on what "undefined behaviour" is. In just C alone (and this is the understanding inherited by C++), there are two possible meanings, depending on which version of ...
- 23.8k
11
votes
Accepted
Show that a language is decidable iff some enumerator enumerates the language in lexicographic order
It's easier to think of $A$ as a list of natural numbers. If $A$ is decidable, then we can list all numbers in $A$ in increasing order by just testing all of them in order – Is $0 \in A$? Is $1 \in A$?...
- 279k
10
votes
Is it decidable if a TM takes at least 2016 steps on all inputs?
A Turing machine only sees (at most) the first 2015 symbols of the input in its first 2015 steps. Hence whether it stops within 2015 steps depends only on the first 2015 symbols of the input. This ...
- 279k
10
votes
Is L={<M>|M is a TM and L(M) is uncountable} decidable?
This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it.
(I ...
- 3,192
9
votes
Accepted
Is it decidable whether a Turing machine modifies the tape, on a particular input?
Yes, this is decidable. Here are two different proofs of that fact.
A counting proof
Define a configuration to be the state of the tape, the location of $M$'s head, the state that $M$'s finite ...
D.W.♦
- 166k
9
votes
Accepted
Undecidable Problem for Regular Languages
Yes, there are undecidable problems like the Post Correspondence Problem that can be coded into the language of a finite state automaton, as explained in my earlier answer to a (slightly broader) ...
- 31.1k
9
votes
Accepted
Relation between Undecidable problems and NP-Hard
I believe that this answer by Yuval Filmus all the questions you have asked.
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ ...
- 175
9
votes
Proof of the undecidability of compiler code optimization
For most interesting optimisations, I think this is implied by Rice's theorem. For real numbers, Richardson's theorem is also relevant here.
- 23.8k
8
votes
Undecidable predicate logic is decidable by people?
The author is incorrect. A consequence of Godel's incompleteness is that any sufficiently complex logic has statements that are true, but have no proof of truth.
If every statement had a proof or ...
- 30.1k
8
votes
Why doesn't infinite run time violate Turing completeness? Shouldn't "completeness" include halting?
You do not yet understand what Turing completeness means.
Turing completeness is the ability to perform arbitrary finite computations.
To simplify matters, we say an arbitrary finite computation is ...
- 5,941
8
votes
Accepted
How to prove the emptiness of intersection of two context free languages is undecidable?
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is ...
- 39.1k
8
votes
Accepted
show that in every infinite computably enumerable set, there exists an infinite decidable set
Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$.
Let $D$ consist of all words $w_i$ which are longer than all words ...
- 279k
8
votes
What are the conditions necessary for a programming language to have no undefined behavior?
The C language may say "if you do X, then whatever the result is, is not a violation of the C Standard". "Whatever the result is" can include the result that you hoped for, some ...
- 31.6k
8
votes
Accepted
Is the Turing machine the only framework to analyse limits of computation?
Turing machines are far from being the only model of computation considered by computer scientists. Among well-studied models of computation are:
Turing machines,
λ-calculus (and its many variants, ...
- 532
7
votes
Is the Rice Theorem applicable for these problems?
Rice's theorem cannot be used to show the undecidability of these two languages.
Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property ...
- 2,516
7
votes
What are the strongest known type systems for which inference is decidable?
[EDIT: Voilà a few words on each]
There are several ways of extending HM type inference. My answer is based on many, more or less successful, attempts at implementing some of them.
The first one I ...
- 214
7
votes
Accepted
What is the purpose of interpreting elements in the proof of reduction of PCP to validity decidability problem of predicate logic?
Lets start with what exactly you are trying to prove.
You're dealing with a signature $\sigma$ which consists of one constant $e$, two function symbols $f_0,f_1$, and one binary predicate $P(s,t)$. ...
- 13.6k
7
votes
Undecidable/Decidable Language
No, because A TM has 3 possibilities: run forever, accept, or reject. So the language of a TM is recursively enumerable as the TM M either accepts some input x, which means x is in L(M), or otherwise ...
- 309
7
votes
Accepted
Why can useless states in TMs not be found by traversing the state graph?
Your proposed algorithm finds some useless state, but not all of them.
Remember that you have tape content to deal with. Say, for instance, a state is reachable when there's a symbol ...
- 72.9k
7
votes
Is effective solvability a coherent and/or useful concept?
By your definition, all problems with defined finite solutions are effectively solvable. Just set the algorithm $A(P_i)$ to be "output $x$", where $x$ is the solution to $P_i$. For example, the ...
- 71
7
votes
Accepted
Proving that the set of deciders is not Turing-recognizable
The basic idea of the proof is to come up with a Turing machine which doesn't belong to the enumeration, hence contradicting the claim that deciders can be enumerated. To this end, we use ...
- 279k
Only top scored, non community-wiki answers of a minimum length are eligible