- Tubelator AI
- >
- Videos
- >
- Education
- >
- Building Deterministic Turing Machines: A Tutorial with Examples
Building Deterministic Turing Machines: A Tutorial with Examples
Learn how to build deterministic Turing machines step by step in this tutorial video. Understand the capabilities of Turing machines and get hands-on experience in specifying their operations. Gain insights into accepting specific languages and develop a deeper understanding of calculability.
Install Tubelator On Chrome
Video Summary & Chapters
No chapters for this video generated yet.
Video Transcript
Welcome to the fourth part of the series about calculability.
In this video we want to build some DTMs.
We will build a Turing machine that accepts this language.
You can watch this video as a tutorial.
There won't be much new.
I think it's important to build some DTMs yourself.
At the beginning we have to get used to what deterministic Turing machines can do.
As the Church-Turing-Thesis already said, they can do everything you can do with any other programming language.
But we have to get used to it first. We have to get a feeling for it.
and until we have the feeling we will specify the Turing machine in a very concrete way and
later we will go to the point that you only specify the Turing machine in a pseudo code way
something like yes the Turing machine writes this and that, it copies it to there and so on
but we are not there yet so we are now building concrete Turing machines and this is the
first language yes the language consists of words of the form a also in b in c in n with n
greater than or equal to 1 yes an old acquaintance if we remember the context-free languages that
were a typical example of a language that is not context-free but we will now
indicate a turing machine for this, that is, we will show that this language is
turing recognizable ok and if you get such a task then it is best to
always think of a strategy first, so how would you proceed if you get any word that
a, b and c. How would you proceed to find out whether this is really
the form a to n b to n c to n. So first of all, let's think about the strategy.
That means we get a word like this. In this case it is of the form a to n b to n c to n.
How would we verify that now? There can of course be different options.
I will now just present one. One possibility is, so our
tolling machine will be at the beginning on the first symbol here, yes, one possibility is to
check whether it really has first A's, then B's and then C's, yes, so that we
have the first C and then B and then A or something that we can exclude them, yes, that
So we could run through the code and see if there are any a's, b's, c's and the word is at the end.
This could be a first step, a pre-processing.
If this is not the case, we can throw away the code.
If this was the case, we run through the code again.
back to the beginning and now we check whether the numbers are really correct, i.e. whether we have
exactly the same number of a's b's and c's and we can do that now we can mark this first
a here so replace the a with a new symbol and then we look for a b find
one then we mark that we keep going and then we look for a c if we find one then we mark
that and as soon as we have marked c we go back to the beginning and do the whole thing
front that is a loop so we look for a mark such a b mark such a c mark
run back here a mark b mark c run back and at some point when the word is only
made up of marked symbols yes that means if we can only see marked symbols
and at the end we bump into a blank without bumping into a
b or c in between, then we can accept that should now be our
strategy and we are now building it as a touring machine so here I have the pre processing
step written down so where we only look over the word once are first a then b
then c and it always has to be at least one yes here n was bigger than one that means we
look is the first symbol in a then leave it at a and go to the right then there can be
a b must come at some point and several bs can also come then at some point c must come then
several cs can also come we leave the symbols all so and just run
over to the right and at some point a blank comes yes at some point we are here yes hopefully so if
the word of the form is also a b or a c then there will definitely be a blank at some point
yes then there is no longer an a or something else and then we walk a step
