Un-decidability in Theory of Computation

Un-decidability

• Problems that lack a constructible algorithm to provide accurate answers in infinite time are undecidable in the theory of computation (TOC).
• It means the impossibility of affirming or denying a statement within a formal framework.
• A problem is categorized as undecidable if there's no Turing machine capable of consistently halting within a finite time to respond with 'yes' or 'no'.
• Undecidable problems inherently lack an algorithm for determining answers from given inputs.

Examples of Un-decidability

• Ambiguity in context-free languages means for a given language, no Turing machine can halt in a finite amount of time.
• Furthermore, it is not possible to determine whether it is ambiguous or not.
• For two context-free languages, it's impossible for a Turing machine to determine the equivalence of the languages and halt in finite time.
• Given a CFG and an input alphabet, determining if the CFG generates all possible strings of the input alphabet (?*) is undecidable.

Decidable Problems

• A problem is decidable if it's possible to create a Turing machine.
• The machine will halt in a finite time for every input and provide a 'yes' or 'no' answer.
• Decidable problems include algorithms to establish answers for any given input.
• Equivalence of two regular languages can be determined by a Turing Machine and Algorithms.
• Finiteness of regular language can be determined by a Turing Machine and Algorithms.
• Emptiness of context free languages can be determined by Algorithms.

Decidable vs. Undecidable Problems

• Decidable problems can be solved by an algorithm in a finite time, while undecidable problems can't be solved by algorithm for all cases.
• Decidable problems are always solvable using a step-by-step process, but undecidable problems can not be solved for all inputs using a single algorithm.
• Decidable problems have algorithms that work for every input and always finish with an answer.
• Undecidable problems lack an algorithm to solve for every input.
• Algorithms for decidable problems always halt and give an answer, while algorithms for undecidable problems might never halt for some inputs.
• Decision procedures for decidable problems have clear methods to always reach a correct conclusion.
• Decision procedures for undecidable problems don't have guaranteed method to solve the problem in every case.
• Checking if a number is even or odd is decidable, while the Halting Problem is undecidable.
• Decidable problems may be complex but are always computable.
• Undecidable problems are too complex to compute in general.
• Decidable problems are useful in practical computing tasks like compiling code or searching for text patterns.
• Undecidable problems shows the limits of what computers can achieve.

Acceptable (Recognizable) Languages

• A Turing Machine (TM) accepts a string if it transitions into an accepting state during the string's processing.
• A language is deemed acceptable if a TM exists that accepts all strings within that language.
• The TM might get stuck on strings not from the language and may loop indefinitely.

Decidable Languages

• If a TM not only accepts strings in the language but also always halts on any input.
• It provides a clear "yes" or "no" answer for membership in the language, said language is decidable.

Decidability Distinction

• Not all acceptable languages are decidable, it is when a TM accepts it but on some inputs runs indefinitely
• The Halting Problem serves as an example: it's recognizable by a TM for specific input halts.
• But it is not decidable due to not always halting on any input.

Decision Problems

• These are algorithmic problems that have only two output possibilities for each input, true or false.
• A decision problem assigns a truth value (true or false) to each input instance.
• A decision algorithm is used to compute the correct truth value for each input instance of a decision problem.
• All algorithm has to terminate on all inputs.
• These problems are decidable if a decision algorithm exists; otherwise, they're undecidable.
• They can be posed yes-no question based on input values whether a specific input meets a set of conditions.
• Essential in understanding computation limits.
• Studying them gains insights to power and limits of algorithms and computability nature.
• Also helps classify problems based on resources.

Halt and Loop Problems

• The halting problem is a classic example of an undecidable problem in computability theory.
• It questions whether an arbitrary computer program, given specific input, will eventually halt/terminate or loop indefinitely.
• If what computers can achieve is limited, and some limit is whether an algorithm is solvable, this means the problem has profound implications in the field of computer science.
• It highlights the importance of designing and testing to avoid unintentional looping.

The Loop Problem

• The loop problem asks whether a program enters an infinite loop.
• It is an undecidable variant of the Halting Problem.

Halt State in Turing Machine

• Used in Turing Machines and depicts completion of computation.
• When the turing machine is in halt state, it has finished processing the input and does not change operation.
• Significance is defining decidable issues, the problem is decidable if the machine provides a "yes or no".
• Halting problem asks if it's possible to determine if a Turing Machine will halt on a given input.
• General algorithm can't solve, and highlights the limitations.
• Each state can be an outcome, where it stops operating.
• Absence can indicate a never ending loop.

Unsolvable Problems

• A Turing Machine cannot solve it, leading to an un-computable function.
• It means it cannot be solved with algorithms.
• There is no solution, or experts disagree on the solutions.
• For an example of this is natural language processing problems.
• Church's thesis estimates human can also solve with the Turing Machine.

Context Free Languages (CFL)

• Generated by context free grammar (CFG) in theory.