Computers solve problems using algorithms, in a systematic, repeatable way However, you may ask are there computational limits to the extent at which a computer can perform? More specifically in class we discussed The Halting problem is the problem of determining whether an arbitrary input to a function will at some point stop/finish running (Halt) or continue to loop forever (not-halt).
Crazy enough in 1936 before the existence of computers, Alan Turing proved that an algorithm that compute whether a program will halt/not-half for all possible program-input pairs CANNOT exist. There are no way of computing these functions. At first I was stubborn and had a hard time believing this is true when computers didn’t exist when Turing’s proof was deduced. Then I decided look into it further and I discovered Gödel’s incompleteness theorems (Which basically is a theorem concerning the limits of provability in formal logical axioms in terms of number theory also take into undecidable propositions into account) which helped me understand some background knowledge, but I was still on the edge of full believing the halting problem is non computable. After thinking about it for days it finally became more clear as to the conclusion.
Now you might be thinking what about Artificial Intelligence, Watson for example; can’t these super computers solve problem such as the halting problem? Well some people are concerned that we are on the road to technological singularity in the computer world, but lets just have some faith Turing’s Disproof to the Halting problem is strong enough to prevent skynet from ever happening haha!
Computability Terminology :
Definition 1: Let f:I→O be a function. Then f is well-defined ⟺ for each x∈I, there is a unique y∈O such that f(x)=y.
Let g,h:I→O be well-defined functions (computable)
Then g is computable ⟺ there is a program P such that ∀x∈I, g(x)=P(x).
Reductions: Then g reduces to h ⟺ g can be implemented with h.
My Professor showed us a proof technique in order to prove a function computable then all we have to do is that that function reduces to a computable function, vice versa.
Until next time,
Yours Truly, CodeShark