• Turing machine was invented by Alan Turing in 1936. This is the hypothetical machine which runs any complicated algorithm. A truing machine consists of a tape of infinite length on which read and write operations can be performed. The tape consists of infinite cells on which each cell either contains input symbol (OR) a special symbol called blank. It also consists of a head pointer which points to cell currently being read and it can move in both directions. A TM is expressed as a 7-tuple (Q, T, B, ∑, δ, q0, F).

Turing Machine Formal Definition

M = (Q, Σ, Γ, δ, q0, qaccept, qreject), where Q, Σ, and Γ are finite sets, and

1. Q is the set of states,

2. Σ is the input alphabet not containing the blank symbol⊔,

3. Γ is the tape alphabet, where ⊔∈Γ and Σ⊆Γ,

4. δ: Q⨯Γ⟶Q⨯Γ⨯ {L, R} is the transition function,

5. q0∈Q is the start state,

6. qaccept∈Q is the accept state, and

7. qreject∈Q is the reject state, where qaccept ≠ qreject.

Defining a Turing Machine Configuration

Things that must be tracked:

1.Current state

2.Current tape contents

3.Current head location

These 3 things are the configuration of the TM:

For a state q and two strings u and v over the tape alphabet Γ, we write uqv for the configuration:

●Current state is q,

●Current tape contents is uv,

●Current head location is the first symbol of v, and

●Tape contains only ⊔ after v.Example Configuration:1011q701111

Turing Machine Formal Definition of Computation

M receives input w = w1w2...wn∈Σ* on the leftmost n squares of the tape, and the rest of the tape is blank. Configuration C1 yields configuration C2 if the TM can legally go from C1 to C2 in a single step.

For a, b, and c in Γ, as well as u and v in Γ*, and states qi and qj in Q:

●uaqibv yields uqjacv if δ(qi, b) = (qj, c, L)

●uaqibv yields uacqjv if δ(qi, b) = (qj, c, R)

Special case: Left movement when head is at first position. qibv yields qjcv.

Start Configuration of M: q0w Accepting and Rejecting configurations have state qaccept and qreject, respectively. A TM accepts input w if a sequence of configurations C1, C2, ... , Ck exists, where:

1. C1 is the start configuration of M on w,

2. Each Ci yields Ci + 1, and

3. Ck is an accepting configuration.

Collection of strings recognized by M (or, the Language of M) is denoted as L(M).

Member's Languages for TURING MACHINE

1. Kiran Perveen (SP19-RCS-028) L = { 0^a1^b0^c : a + c = b }

2. Javaria Tahir (SP19-RCS-026) L = { w#w#w : Σ = {a , b }^✱}

3. Syed Muzafar Ali (SP19-RCS-052) L = { aⁱ b^j aⁱ : i ≠ j }

• The first language is 0^a1^b0^c such that a + c = b . We have proved for this language which describe that it is not a context free and regular language. Where 0 is sub-string of a and b 1 is sub string of b and set of strings belong to this language consists of characters 0 and 1 . In this language, two strings are provided 0 and 1 where in these strings the string will be accepted when sum of and c is equal to the value of b. The language says that length of a and C are equal while b should be double then the sum of a and c then we consider this non-context free language.

• The language is w#w#w such that Σ = {a , b }^✱ and we have proved for this language which describe that it is not a context free and regular language. Th set of strings belong to this language consists of characters a and b. In this language, the strings are provided w where these strings are separated by # symbol and those separated strings are in language.

• The language is aⁱ b^j aⁱ such that i ≠ j and we have proved for this language which describe that it is not a context free and regular language. However, there is no separation of # symbol. The set of strings in this language proved as it is not a context free and regular and it is consisted of 0 and 1 in a set of string belong to language.

• In Palindrome Input from user in binary form and after building machine input field must hide. Move head through space bar. After input the string, states changes every time by pressing the space button. In palindrome the first and last digit must be same. Basically, in this Turing machine it will read the letter remembers it and compare it with the last letter. They both must not be same otherwise it will be rejected. In case of the even length palindrome, if you read the complete input without any mismatch then it will be accepted and declared as palindrome.