relationship between countability and turing machine halting

Question

Hi i have a doubt over countability. Why is it necessary to find out whether certain things are countable. Is there a use over finding it? And also if some thing is uncountable does it mean that there is no Turing machine to solve it ?

Answer 1

I hope I am not helping you answer an exam question by answering your question.

Countability and Turing machines are very much two sides of the same coin. They're complementary ways of determining if a problem is "computable." There are other equivalent ways of showing computability as well (look up abacus machines, countable functions, computable functions, etc.). By definition, you show a problem to be computable if you can demonstrate that it can be solved by a Turing machine. Alternatively, you can show a problem to be computable if you can show that it has a solution bijection from the countably infinite set.

By the way, the countably infinite set is the "small" infinite set or the set ℵ₀. (In layman's terms, the small infinite or countably infinite set is the set of integers. Integers, odd numbers or even numbers has the same cardinality—the small infinite set. There is an infinite hierarchy of infinite sets, starting with ℵ₀ and going up to ℵ_∞. ℵ₀, the set of integers, is the smallest infinite set. ℵ₁ is a superset of ℵ₀. R, the set of real numbers, has the same cardinality as ℵ₁, and so on.) Understanding that there is a hierarchy of infinities will help you understand what you need to prove to show computability.

The elementary Turing machine has a small infinite tape. Showing that a problem can be computed by a Turing machine means showing that the problem has a solution bounded by small infinite time and space. A Turing machine has a tape that has infinite cells that can hold symbols. There are infinite cells in either direction (small infinite), just like the set of integers is infinite in either direction. Associated with the tape is a read-write head that can travel left or right on the tape and can read or write a single symbol on each move. Show a sequence of instructions that moves the head on the tape from the initial state to an eventual halting or terminating state is to show that a problem is "computable." Proving that no solution of a problem can be done by the Turing machine is to prove that a problem is not computable—regardless of whether we give countably infinite time or resources. By the way, time and space are complementary. If you can solve a problem in finite time using countably infinite space or solve it consuming finite space with countably (i.e., small) infinite time, you show the problem to be computable.

Answer 2

I can give you a little bit of an answer (sorry I only know a little bit of computing theory).

There are only countably many Turing machines. So, if you have a set of problems that is uncountable, you know there is at least one problem in that set for which there is no Turing machine that will solve it.

So, for example, if your set of problems is

For some function f:N -> N, write a program that, given n, computes f(n)

You know that there is at least one f for which no such program can be given, because there are uncountably many such f.

I don't believe this analysis can be applied to the halting problem, though, because the halting problem consists of exactly 1 problem: "given the code for a Turing machine, decide if, given a blank tape, it will eventually halt." This is just one problem with countably many possible inputs, so, just by counting, it looks potentially solvable. You'd have to argue some other way that it is not solvable.

Of course, the importance of countability and uncountability is far more diverse than this one example. I hope other people can supply some more.

Answer 3

Countability is actually pretty important when it comes to a Turing machine, and in many other places in math and science. A since a Turing machine has to perform operations sequentially, each step can be assigned a counting number. If the process goes on forever, then the process is countably infinite.

An example of an operation for which a Turing machine would be inadequate would be summing the squares of all numbers between 1 and 2. It can be shown quite easily that the entire list of rational numbers in this interval can be listed in a countable list in which every number can be mapped 1-to-1 with a counting number. So performing the steps one at a time on this list of numbers could be carried out by a Turing machine. However, this could not be done with the irrational numbers on this interval, because there are just too many of them. It can be shown (not quite as easily) that the list of the irrational numbers cannot be put into an ordered (countable) list. So, the is no order in which every number on the interval could be listed, meaning that the Turing machine could not accomplish the task, even if given an infinite amount of time.

Countability of rationals

Uncountability if irrationals - Cantor Set