notes-cs-theory-computability

The notes on this page are summaries that are not meant to make any sense to anyone who doesn't know this stuff already.

Some quick notes on computability (please email me if any of these are incorrect):

• "decidable set", "recursive set", "computable set" are synonyms (i find "decidable set" to be the most memorable one)
• "computably enumerable", "recognizable language", "recursively enumerable", "semidecidable", are synonyms (i find the first two to be the most memorable; note however that there are some people who use the phrase "recognizable set" completely differently: https://en.wikipedia.org/wiki/Recognizable_set )
• a set is decidable iff both it and its complement are computably enumerable
• if a set is computably enumerable but not decidable, its complement must not be computably enumerable
• all finite sets are decidable
• the (countably infinite) set of all natural numbers is decidable
• a set of finite strings over a finite alphabet has countably infinite cardinality
• a set of countably infinite strings over a finite alphabet has uncountably infinite cardinality (e.g. the set of decimal expansions of real numbers >= 0); think "2^infinity", this can be put into bijection with a powerset, namely the set of all subsets of the previous bullet point (you can encode any infinite set of finite strings into an infinitely long string)
• the set of all computer programs is countable (and countably infinite, e.g. can be put into bijection with the natural numbers)
• the halting problem (subset of all programs which halt on a given input) is computably enumerable but not decidable
• there are countable sets that are not computably enumerable. E.g. the complement of the halting problem
• no set of uncountable cardinality is computably enumerable
• the set of all total functions on the natural numbers is of uncountable cardinality, because any string of countably infinite length can be encoded as a total function on the natural numbers
• the set of all total computable functions, that is the set of all computer programs that halt on every input, is not recursively enumerable (note that even though the halting problem is recursively enumerable, that only tells you if a program halts on one inputs, you'd have to check that for infinitely many inputs to be sure that the function is total by that method)
• more generally, i think that any property of computer programs such that either (a) for some programs you cannot tell if that program has the property without running it for an arbitrarily long amount of time, or (b) for some programs you cannot tell if that program does NOT have the property without running it for an arbitrarily long amount of time, then that property is not decidable. For example, http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no shows that you can't compute whether an arbitrarily program which is known to run in polynomial time runs in O(n^2) or not, because it may appear to run slower than that for small inputs but then shift its behavior at some arbitrarily large input. If you need to prove that something can shift its behavior unpredictably at an arbitrarily large input, you can reduce it to the halting problem.
• even if a set is not computably enumerate, you might be able to define it (to uniquely specify it), e.g. the set of all total computable functions. However, any definition is itself a finite string over a finite alphabet. Therefore, there are only countably many definitions. Therefore, almost all of the members of any set of uncountable cardinality are undefinable.
• Rice's theorem says that, for any property of computable sets, unless that property holds for all computable sets or for none of them, the task of whether the set computed by an arbitrary given computer program has that property, is undecidable: https://en.wikipedia.org/wiki/Rice%27s_theorem
• DFAs and stacks and queues:
  • " A DFA with a stack is a PDA. A DFA with two stacks is a Turing machine. Looking at the 3 different classes as DFAs with 0, 1, or 2 stacks is just so beautiful" -- https://news.ycombinator.com/item?id=6790295 "you can treat two stacks like one tape. The top of the first stack is the current location on the tape. You can move the tape head to the left by popping from Stack 1 and pushing that value onto Stack 2. Pop from Stack 2 and push on Stack 1 to move to the right." -- https://news.ycombinator.com/item?id=6790508 .
  • ""Another way of saying this is that the two stacks as a list zipper[1], which makes the correspondence between a DFA with arbitrarily writable memory and a DFA with two stacks readily apparent." -- https://news.ycombinator.com/item?id=6790508"
  • "a DFA with a queue is a Turing machine. You can show this by putting a sentinel value in the queue that separates two stacks and having some crazy loop structures that allow you to push and pop from the two stacks it represents." -- https://news.ycombinator.com/item?id=6789631