Question

Are there computational problems that cannot be solved by a digital computer(or any Turing machine)? Give one example (that is not computable) and intuitively why it cannot be solved by a digital computer.

Answer 1

The answer for the above mentioned question is explained below ::

Yes , there are computational problems which can't be solved by digital computer .

One example for that computational problem which can't be solved by digital computer is taking a program as a input and find whether it goes into infinite loop or not i.e., When we give a program as a input to the digital computer and if we want to know whether the given program goes into infinite loop or not it is computationally impossible by a digital computer to solve .

Explanation for why the above problem is not solved by digital computer ::

Checking whether the input program goes into infinite loop or not will be done with the help of some indication , i.e., like return value which indicates the program has no infinite loop because it terminated successfully and then returned the corresponding return value to indicate the given input has not goes into infinite loop , this is the case when we gave input ( to the digital computer) a program which doesn't goes into the infinite loop , here we gave the input program to the digital computer in such a way that it doesn't goes into infinite loop , by the help of return value mechanism we can able to find that it doesn't goes into infinite loop (here it only happens in the case of programs which really doesn't goes into infinite loop )

When it is not the case , i.e., when we input a program which really goes into infinite loop to the digital computer to check whether the input program goes to infinite loop or not , it doesn't produce any answer because it might think the input program is doing some useful work and the digital computer waits for the return value of the input program to decide whether the input program has infinite loop or not . This waiting for the digital computer doesn't stop if the input program really goes into infinite loop because our digital computer can't conclude the given input program goes into infinite loop after waiting a long time because it may doing some work so our digital computer may wait until the input program returns a value to indicate that the input program does not goes into infinite loop , but it doesn't happen in case of inputs which really goes into infinite loop .

So checking whether the given input program goes into infinite loop or not is computationally impossible to a digital computer .