Turing Machine
Introduction to Turing Machines ~ Part I
Introduction:
A Turing machine consists of a finite control, a tape, and a head that can be used for reading or writing on that tape. The Turing Machine (T.M.) has a tape that has a left end, but it extends indefinitely to the right. To prevent the machine from its head off to the left we assume the leftmost end of the tape is always marked by a special symbol B, distinct symbols → and ← movements of the head to the left or right.
A Turing machine is superior then a DFA, NFA & PDA.
Church-Turing Thesis
“No computational procedure will be considered as an algorithm unless it can be represented as a Turing Machine”.
Essentially, the Church-Turing thesis asserted that the correct way to describe a computing machine was via what we now call the Turing machine, which is pretty much equivalent to a modern computer, but with unlimited memory.
Is T.M. a machine?
Yes, it is an abstract machine that applies to solve the problems. There are no such solvable problems that the Turing machine cannot solve.
Formal Definition of Turing Machine
A Turing machine is a quintuple (B, S, K, ∑, δ, 𝝉, F) where
K is a finite set of states
B → special Blank Symbol
∑ → an alphabet containing the blank symbol B and the left end symbol but not containing the symbol ← and →
S ϵ K is the initial state
F ⊆ K is the set of Halting state
𝝉 → tape symbols
δ → the transition function is a function from (K — H). ∑ to K. (∑ U {←, →}) such that
a) for all q ϵ K → H, if δ(q, B) = (q, b) then b = →
b) for all q ϵ K — H then a ϵ ∑, if δ(q, a) = (q, b) then b ≠ B.
Problem
Design a T.M. for language L = { ww^R: w is any palindrome over ∑ = {a,b }.
Here given,
Let N-PDA (B, S, K, ∑, δ, 𝝉, F) and T.M and assuming w5w5^R be “aabbaabbaa”. Here we do not know the central of the string, so it behaves as an even palindrome.
B is the blank symbol
h = halting or the final state
| w5w5^R | = 10 (even length of a’ s and b’ s characters)
Programming Part
#include <stdio.h>
#include <string.h>
#define TAPE_LENGTH 100
#define BLANK 'B'
// Define states
typedef enum {
q0, q1, q2, q3, q4, q5, halt
} State;
typedef struct {
char tape[TAPE_LENGTH];
int head;
State state;
} TuringMachine;
void initializeTape(TuringMachine *tm, const char *input) {
memset(tm->tape, BLANK, TAPE_LENGTH);
strncpy(tm->tape + 1, input, strlen(input)); // Leave a blank at the beginning
tm->head = 1; // Start at the first character of input
tm->state = q0;
}
void runTuringMachine(TuringMachine *tm) {
while (tm->state != halt) {
char current = tm->tape[tm->head];
switch (tm->state) {
case q0:
if (current == 'a') {
tm->tape[tm->head] = BLANK;
tm->head++;
tm->state = q1;
} else if (current == 'b') {
tm->tape[tm->head] = BLANK;
tm->head++;
tm->state = q4;
} else if (current == BLANK) {
tm->state = halt;
}
break;
case q1:
if (current == 'a' || current == 'b') {
tm->head++;
} else if (current == BLANK) {
tm->head--;
tm->state = q2;
}
break;
case q2:
if (current == 'a') {
tm->tape[tm->head] = BLANK;
tm->head--;
tm->state = q3;
} else {
tm->state = halt; // Error state
}
break;
case q3:
if (current == 'a' || current == 'b') {
tm->head--;
} else if (current == BLANK) {
tm->head++;
tm->state = q0;
}
break;
case q4:
if (current == 'a' || current == 'b') {
tm->head++;
} else if (current == BLANK) {
tm->head--;
tm->state = q5;
}
break;
case q5:
if (current == 'b') {
tm->tape[tm->head] = BLANK;
tm->head--;
tm->state = q3;
} else {
tm->state = halt; // Error state
}
break;
default:
tm->state = halt;
break;
}
}
}
int isPalindrome(TuringMachine *tm) {
return tm->state == halt && tm->tape[tm->head] == BLANK;
}
int main() {
TuringMachine tm;
char input[TAPE_LENGTH];
printf("Enter the input string (consisting of 'a' and 'b'): ");
scanf("%s", input);
initializeTape(&tm, input);
runTuringMachine(&tm);
if (isPalindrome(&tm)) {
printf("The input string is a palindrome.\n");
} else {
printf("The input string is not a palindrome.\n");
}
return 0;
}A Turing Machine — Overview (youtube.com)
References
- Wikipedia
- YouTube
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Pearson — Addison-Wesley.
- Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, 2nd Edition, Prentice Hall
Suggestions and Feedback: dillihangrae@gmail.com
