Computability — Turing Machines, Formal Languages
This is Part 1 of Series: “How To Explain Complexity Theory To Your Buddy”. You can check my all posts here:
- Computability — Turing Machines, Formal Languages [THIS POST]
- Computability — Classes of Problems, The Art of Reduction
- Complexity — Introduction
- Complexity — Classes and Their Limitations
- Complexity — Comparison of Different Satisfiability Problems
- Complexity — We Don’t Know Anything Yet?
How Does the Abstraction Look Like?
- A ML algorithm on the internet which calculates the probability if a given image contains a cat / dog / bird using TensorFlow is coded by someone using Python.
- Python, which is an interpreted general-purpose programming language, created in the 90s using C, is used by so many programmers around the world and it requires absolutely no knowledge about dynamic memory allocation or pointers.
- C, which introduces many concepts of a modern programming language, hides underlying complexity of assembly languages.
- Assembly codes are basically pretty-printed CPU instructions made easy.
- CPU (Central Processing Unit) consists of ALU (Arithmetic & Logic Unit) and RAM (Random Access Memory) where all calculations happen in ALU and all programs are stored in RAM.
- ALU is created using Logic Gates, the most basic logical structures hard-coded as 1s and 0s using circuits, which is why when they say it is all 1s and 0s they are not wrong.
This is the chain of abstraction. It is nearly impossible to create everything from scratch, but with abstraction it is just a matter of time. In the following section, we will see how theoretical computers called Turing Machines changed the perspective of an entire world.
Turing Machines Demystified
Turing Machine is a abstract representation of all functions in the computer science world. It can compute anything which is computable.
A Turing Machine M which is basically a “machine” which is allowed to modify the given input by operating on a cell basis, moving the head left and right or none, reading the inputs for example 0, 1, # and writing a letter depending on current state, in order to find out that an input is accepted / rejected. For an amazing introduction, you can check this out:
- To Halt (Stop): The Turing Machine ends in an infinite loop that does nothing.
- To Accept: The Turing Machine halts in a state which is an accepting one that we specified in definition of Turing Machine.
Introduction to Deterministic and Nondeterministic Turing Machines
There are numerous variations of Turing Machines, and the 2 most important ones are:
- Deterministic Turing Machines (DTM): For each input, there is only a single path of computation. A word is accepted if the end state is an accepting one and vice versa.
- Nondeterministic Turing Machines (NTM): There can be many parallel paths of computation. A word is accepted if at least one of the end states is accepting.
Both Turing Machines are equivalent in terms of computational power: For each DTM, there exists a NTM, and for each NTM, there exists a DTM.
The Question Is Not “What?” But “If?”
A problem being computable means that there is an algorithm (not necessarily implemented) so that this problem can be calculated. There is no specification about complexity and efficiency of this problem, the main question is if there exists an algorithm.
Letters to Words to Languages to …
In formal languages theory, there are clear definitions of every aspect we will discuss in the next sections:
- Letter: It can be a number, an alphanumeric letter, but most basically we can represent any letter using 1s and 0s.
- Word: A meaningful combination of letters which represents for example an argument, we will see it mostly as an argument passed in an algorithm.
- Language: A list of words that are accepted by a Turing Machine. We will see it mostly as the word problems (if a word is contained in a language) which also shows whether given argument gives a YES or NO instance.
And also we will mostly see classes as set of languages, containing languages of similar behaviour.
