COROLLARY 3.15
A language is Turing-recognizable if and only if some multitape Turing machine recognizes it.
Front
Active users
1
All-time users
2
Favorites
0
Last updated
4 years ago
Date created
Nov 5, 2020
Turing Machines
(13 cards)
COROLLARY 3.15
A language is Turing-recognizable if and only if some multitape Turing machine recognizes it.
PROOF
A Turing-recognizable language is recognized by an ordinary (single-tape) Turing machine,
which is a special case of a multitape Turing machine.
That proves one direction of this corollary.
The other direction follows from Theorem 3.13.
After introducing Turing machines, how does our Chomsky hierarchy look like?
What are some decision problems that TM's can't do?
For nonrecognizable/noncorecognizable languages, we use the Turing equivalence to show that
Do we care about efficiency? Can we still focus on decision problems?
No. We care about trying everything to figure out what works. This means we focus on decision problems and in particular, decidable languages.
When is a language Turing-recognizable?
THEOREM 3.21
A language is Turing-recognizable if and only if some enumerator enumerates it.
PDAs can do addition; why can't they do multiplication but Turing machines can?
Turing machines have better memory access than PDAs where you can go back and fourth with your memory stack and your input.
Lets say we multiply 1^a with 1^b to equal 1^ab
What is a decider?
A nondeterministic Turing machine where all branches halt on all inputs.
What is the formal definition of a Turing machine?
A Turing machine is a 7-tuple where
M = (Q,Σ,Γ,δ,q0,qaccept,qreject) with
Q: finite set of states
Σ: finite input alphabet with the empty character not allowed
Γ: finite tape alphabet that must include the input alphabet with the empty character (can include other symbols)
q0, qaccept, qreject: states that are the start, accept, and reject states respectively and with qaccept unable to equal the qreject state
δ: Q x Γ -> Q x Γ x { L, R } is the transition function
If we want to see delta in action, here's how it looks like with our previous example
Here's how you read them
δ(q0,1) = (q1,x,R)
At state q0 when we read a 1, we transition to state q1, we replace 1 with x, and we move right on the memory tape
In our previous examples, this is how it looks like.
After introducing Turing machines, how does our Chomsky hierarchy look like?
What is a Turing Machine in practice?
Turing machines can simulate all the behaviors of a real life modern computer.
Since some machines are programmed to handle certain languages, Turing machines can be pre-programmed computers.
We can also think of Turing machines as algorithms in computers and software.
Are we gonna have a Turing pumping machine?
No. We will have something more complicated.
What is a Turin-recognizable language?
What is a decidable language?
A language is called Turing-recognizable if some Turing machine recognizes it.
A language is decidable if some Turing machine decides it.
Design a Turing machine that does multiplication
First, how do we describe multiplication checking?
The first thing we describe multiplication checking is
In our computational model, we would assume the multiplication expression we're trying to check
Our algorithm that we will design will not need any portion of the tape that doesn't already start with the input on it.
Checking at a high level, we will naturally have a nested for loop. We will have something like this
The idea here is that we mark the number of 1's after the = by the amount of 1's on the right of * and repeat it by the number of 1's to the left of *.
We accept input that marks all the 1's to the right of =.
We leave the empty memory characters alone. They indicate that we reached the end of our input and we can accept our string.
Transitioning from high level pseudocode, we have the following low level pseudo code.
From here we can build a state machine to check our multiplication.
The idea here is when we begin at q0,
Notice there's no accept state yet. Let's create one
Our machine doesn't know when something bad happens like a bad string
Chomsky Hiearchy
(1 card)
We have the Chomsky hierarchy where we introduce Decidable languages.
In Regular Languages:
L = {1^a + 1^b}
In Context free languages:
L2 = {1^a + 1^b = 1^(a+b)}
Decidable Languages:
L3 = {1^a * 1^b = 1^ab }
Before we build the Turing machine, let's go back to the TSP:
In Turing machines, we don't care about efficiency. We care about getting our machine to work.
This means we can focus on decision problems. In particular, we will work with decidable languages.
Decidable languages:
Variants of Turing Machines
(12 cards)
What is a multi-tape Turing machine?
' A multitape Turing machine is like an ordinary Turing machine with several tapes.
Each tape has its own head for reading and writing.
Our transition function will be
We read expressions like
head to move left or right, or to stay put, as specified.
COROLLARY 3.18
A language is Turing-recognizable if and only if some nondeterministic Turing machine recognizes it.
PROOF Any deterministic TM is automatically a nondeterministic TM, and soone direction of this corollary follows immediately. The other direction follows from Theorem 3.16.
Illustrate the robustness of the Turing machine
In our Turing machine definition, the transition function forces the head to move to the left or right on the tape after each step
If we allow the head to stay still
This feature won't improve the power of other Turing models since we can transition left then right.
To show that two Turing models are equivalent
we simply need to show that one can simulate the other
THEOREM 3.16
Every nondeterministic Turing machine has an equivalent deterministic Turing machine.
PF idea:
simulate any nondeterministic TM N with a deterministic TM D
it has explored all of them
What are variants of the Truing machine?
Alternative definitions of Turing machines including
The original model and its reasonable variants all have the same power—
What is a nondeterministic Turing machine?
It has the same definition as the Turing machine except
We can think of a tree whose branches correspond to different possibilities for the machine.
If some branch of the computation leads to the accept state, the machine accepts its input.
What is robustness?
invariance to certain changes
Examples
When is a language decidable?
COROLLARY 3.19
A language is decidable if and only if some nondeterministic Turing machine decides it.
How does an enumerator work?
An enumerator E starts with a blank input on its work tape.
The language enumerated by E
E may generate the strings of the language in any order, possibly with repetitions.
What is an enumerator?
A Turing machine variant that can be loosely defined as a TM with an attached printer.
Are multi-tape Turing machines equivalent to ordinary Turing machines?
THEOREM 3.13
Every multitape Turing machine has an equivalent single-tape Turing machine.
The Definition of Algorithm
(0 cards)