Struktur Diskrit : Mesin Turing dan Contoh Soal
Turing Machine
The finite-state automata cannot be used as general models of computation. They are limited in what they can do. For example, finite-state automata are able to recognize regular sets, but are not able to recognize many easy-to-describe sets, including {0n1n | n ≥ 0}, which computers recognize using memory.
We can use finite-state automata to compute relatively simple functions such as the sum of two numbers, but we cannot use them to compute functions that computers can, such as the product of two numbers.
To overcome these deficiencies we can use a more powerful type of machine known as a Turing machine, after Alan Turing, the famous mathematician and computer scientist who invented them in the 1930s
Basically, a Turing machine consists of a control unit, which at any step is in one of finitely many different states, together with a tape divided into cells, which is infinite in both directions.
Turing machines have read and write capabilities on the tape as the control unit moves back and forth along this tape, changing states depending on the tape symbol read. Turing machines are more powerful than finite-state machines because they include memory capabilities that finite state machines lack.
At each step, the control unit reads the current tape symbol x. If the control unit is in state s and if the partial function f is defined for the pair (s,x) with f(s,x) = (s’, x’, d), the control unit
- enters the state s’
- writes the symbol x’ in the current cell, erasing x,
- moves right one cell if d = R or moves left one cell if d = L
We write write this step as five tuple (s, x, s’, x’, d). If the partial function f is undefined for the pair (s,x), then the Turing machine T with halt.
Example
What is the final tape when the Turing machine T defined by the seven five-tuples
- (s0,0, s0,0,R),
- (s0,1, s1,1,R),
- (s0,B, s3,B,R),
- (s1,0,s0,0,R),
- (s1,1,s2,0,L),
- (s1, B, s3,B,R), and
- (s2,1, s3,0,R)
is run on the tape shown in Figure (a)?
Turing Machine as Language Recognizer
Example: Find a Turing Machine that recognizes the set of bit strings that have a 1 as their second bit, that is, the regular set (0 U 1)1(0 U 1)*.
- Read first symbol => (s0,0,s1,0,R), (s0,1,s1,1,R)
- Read second symbol:
- 0 : (s1,0,s2,0,R)
- 1 : (s1,1,s3,1,R) => recognized, s3 is a final state
- Second bit must not be 0 => (s2,0,s2,0,R)
- To avoid empty string and 1-bit string => (s0,B,s2,0,R), (s1,B,s2,0,R)
Exercises
1. What does the Turing machine described by the five tuples (s0, 0, s0, 0,R), (s0, 1, s1, 0,R), (s0,B, s2,B,R), (s1, 0, s1, 0,R), (s1, 1, s0, 1,R), and (s1,B, s2,B,R) do when given
- 11 as input?
- an arbitrary bit string as input?
2. What does the Turing machine described by the five tuples (s0, 1, s1, 0,R), (s1, 1, s1, 1,R), (s1, 0, s2, 0,R), (s2, 0, s3, 1,L), (s2, 1, s2, 1,R), (s3, 1, s3, 1,L), (s3, 0, s4, 0,L), (s4, 1, s4, 1,L), and (s4, 0, s0, 1,R) do when given
- 11 as input?
- a bit string consisting entirely of 1s as input?
3. Construct a Turing machine with tape symbols 0, 1, and B that, when given a bit string as input, replaces the first 0 with a 1 and does not change any of the other symbols on the tape.
Posting Komentar