Basics of Computability - Cleaning Up Terminology - C4

5-minute read

So far it has been quite easy to get lost in the forest looking for the trees. So this short chapter will bring full circle a few topics already discovered and their relation to Turing Machines.

Turing machines and Algorithms

A Turing machine implements an algorithm. Using the Church-Turing thesis, we can define an algorithm in terms of Turing machines.

Moreover, we can define an algorithm in terms of a Turing Machine.

Turing machines and Languages

Every Turing machine has an associated language L. This is the set of all inputs that the Turing machine halts on.

We say that the Turing machine recognises a language L because it halts on all inputs in L. We place no restriction on what happens if the string is not in L, the Turing machine could loop forever.

We say that a Turing machine decides a language L if it halts and accepts on all elements in L and halts and rejects all elements that are not in L. We call such a Turing machine a decider as it halts on all inputs.

Note: a recogniser may loop forever, but a decider will always halt.

Problem and Languages

Consider the two problems “Is X an even number” and “Is X a number”. Clearly these two problems have some sort of relationship; a solution to the first problem is also a solution to the second problem. However, we would like a formal concept to describe this relationship with. Moreover, we would like to be able to analyse each problem in a formal manner or with an equivalent formal realisation of the problem.

Below we describe a technique for converting a problem into it’s equivalent language.

Another way to look at the problem of “Is X a solution to the problem” is, “if we collect all of the solutions for the problem, is X a part of that set”?

Example

Problem: “Is 20 an even number?”

The naturally occurring language_ from this problem is the set of all even numbers.

$L = \{0,2,4,6,8,10,12,14,16,18,20, 22,24,…\}$

Our problem is now translated to “Is $20 \in L$ ?”

Observe: Languages with infinite sizes are possible. Also observe that the language $L$ defined was overkill. We could have defined the set of even numbers up to 22.

Problem : “Is X an even number?”

Note: We could choose an arbitrary X and so the size of the language must be infinite.

Our problem would then translate to “Is $X \in L$”

Summary

Given a problem, we can find a naturally occurring language for the problem. This is set. Two problems can be related if their sets are related, one set is a subset of the other. If a Turing Machine solves a problem, then the associated language for the Turing Machine will be a superset of the naturally occurring language for the problem.

Languages and Algorithms

Languages and algorithms are both concepts, brought together by a Turing machine; A Turing machine implements an algorithm and has an associated language.

Turing machines and Problems

Another connection we can make is the following:

Define the language associated to a problem A as $L_a$. If a Turing machine decides $L_a$ then at a high level, this means that a Turing machine solves that problem.

Question

What is the naturally occurring language for a problem or the language associated to a problem?

In most cases this will be defined as the elements which are the solutions to the problem over all possible inputs.

Reducibility

Envision the following scenario:

  • Assume your social media accounts are always logged into your computer

  • Now assume you have a password on your computer.

  • Attacker A would like to access your social media accounts.

  • If he can break your password, he can access your social media accounts because they are always logged in.

  • This means that the task of accessing your social media account, reduces to breaking your password.

  • Furthermore, note that if the attacker somehow manages to get your social media accounts without breaking your password, this does not give him access to your password.

  • Therefore accessing your social media account does not reduce to breaking the laptops password.

When we say that an object A reduces to object B, this can be seen as object A can be transformed into object B or object B can be used as a sub-process to solve A. The latter definition is more consistent with the logic, while the former can be used to informally remember this notion.

We say that problem A reduces to problem B, if it is possible to solve A using an algorithm that solves B. This means that A cannot be harder than B, because if you have an algorithm for solving B, you immediately have an algorithm for solving A. A is as hard as B, but not harder.

Note that although we used the word problem, formally we would use the word language because every problem has a naturally occurring language associated with it.

Re-formalised: We say that a language A reduces to a language B, if it is possible to decide A using an algorithm/ Turing machine that decides B

Categorizing Problems

Reducability gives us a tool to categories languages/problems. If I encounter a new problem, but I somehow show that it can be solved using the solution to a known problem, then I can reasonably assume that both problems are in the same category or region.

Note now that if I had the halting problem and an unknown problem B. It is possible to show that problem B is un-solvable if the halting problem reduces to it.

  • If the halting problem reduces to problem B, then an algorithm to solve problem B, could be used as a sub-process to solve the halting problem.

  • This shows that the halting problem is as hard as B, but not harder.

  • Hence B is harder than the halting problem.

  • But the halting problem is undecidable, which means that B is also undecidable.

If we showed that language A reduces to language B and that language B reduces to language A. This would mean that the two problems are equally as hard as each other.