The Church Thesis Turing Machine Assignment

Running head: THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
Name of the Student:
Name of the University:
Author note:

1THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
Table of Contents
Introduction:....................................................................................................................................2
Church Turing Thesis:.....................................................................................................................2
Variants of the Turing Machines.....................................................................................................2
Conclusion:......................................................................................................................................6
References:......................................................................................................................................7

2THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
Introduction:
Invented by Alan Turing, the Turing machine is a mathematical model that recursively
accepts the languages which are generated by the grammar type 0. The machine completely
operates on the infinite memory tape which are divided into “discrete” cells. A Turing Machine
is similar to a finite state automaton with an unrestricted memory. This is a good example of the
central processing unit or the CPU which is responsible for the purpose of controlling the data
manipulation in the computer system. In its initial stage, the Turing machine tape has one input
string and the rest is blank. In order to store information, the machine has to write the
information on the tape and to read the input, it has to move its head over it. Moreover, it can be
stated as the machine or the automaton used for the purpose of order listing the subsets of the
valid set of alphabet strings [1]. The infinite length of the memory tape that is used in the Turing
machine is utilised for the purpose of the reading and writing operations. The operations of the
Turing Machine includes the processing of the unrestricted grammar and thus is capable of
evaluation of the first-order logic of the in infinite possible ways. The following report discusses
about certain variation of the Turing Machines.
Church Turing Thesis:
The Church Turing thesis is also termed as the computational thesis or the Church thesis
Conjectures. This thesis describes the nature of the computational functions. According to the
thesis, “the function of the natural numbers can be calculated by and effective method only if it is
computable by a Turing machine.” The thesis is entitled after two most famous mathematicians
of their time, Alonzo Church and the famous Alan Turing [2]. Here, we will discuss about some
of the variants of the Turing machines which have helped in easing up the process of
computation.

3THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
Variants of the Turing Machines:
A Turing machine is often described as the 7-tuple (Q, X, ∑, δ, q0, B, F), in which:
Q is a finite set of states
X is the tape alphabet
∑ is the input alphabet
δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
q0 is the initial state
B is the blank symbol
F is the set of final states
As described earlier, the Turing machine is a mathematical model which is used for the
purpose of operating reading and writing operations in a system [3]. It is the outermost layer of
the Automata theory. The automata theory is the way in which the abstracts machine and the
self-operating machine (Automaton) are studied and solved. There are four major family of the
Automaton and they are Finite State Automaton (5 tuple system), push down automaton, linear
bounded automaton and the Turing Machine. With the advancement of the technology and
invention of more and more complex machines, development of the Turing machines was more a
necessary. The variants of the machine are much more powerful and capable of performing more
complicated operations. In this section we will discuss about some of the very important variants
of the Turing machines [4].
According to the improvement in performance of the machine and ability to solve more
complicated problems of in the machines, the Turing Machine can be classified into 7 different
variants and they are discussed as follows:

4THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
 Multiple Track Turing Machine: This is a type of the “multi tape Turing Machine” that
is in use. This is also known as the K-track Turing Machine for the value of the K>0. It
has k number of tracks and one head for the reading and the writing function, which reads
or writes the one after the other. It is possible to simulate the k-tack Turing machine to
the Single track Turing machine. The multi-track Turing machine is united by one tape
and has one head as well [5].
 Two way infinite Tape Turing Machine: This can be used for the purpose of the
simulation of the two way infinite tape. The Right part of the “two way tape” is stored on
the TAPE 1. The other half of the tape is Stored in the TAPE 2. There is a stage in this
Turing machine known as the Transitions which is used for the purpose of handling the
transition of the stage from 1 to 2. A standard Turing Machine accepts all the languages
that are accepted by the two way infinite tape machine [6].
 Multi-tape Turing Machine: This variant of the Turing machine have multiple tapes and
are controlled by one single head. These are slightly different from the k-track Turing
Machine with same expressive power. The Multi tape Turing machine can be counterfeit
by the Standard Turing machine [7].
Formal Definition:
A k-tape Turing Machine is M = (Q,Σ,Γ,δ,q0,qacc,qrej)(Q,Σ,Γ,δ,q0,qacc,qrej) where
Q is a finite set of control states
Σ is a finite set of input symbols
F ϽΣ is a finite set of tape symbols. Also, a blank symbol ϵΓ\ Σ
q0 ϵQ is the initial state

5THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
q_{acc}ϵQis the accept state
q_{rej}ϵQ is the reject state, where q_{acc} and q_{rej} are not equal
δ : Q × Γ k−→Q × Γ k × {L, R, S} k , where k is represented as the number of tapes [8].
 Non-deterministic Turing Machine: It is a kind of Turing machine where deterministic
type and non-deterministic type is the same. Both the type of machines have a single
infinite tape which is one way in nature. In this case, there is at least one choice for every
state and input symbol. So there are a finite number of choices or paths to follow for the
next move. Each of those choices however presents several other choice to follow after
that for any string given as input [9].
For a deterministic Turing Machine, we find that, one and only one solution is
given for every condition, but for the non-deterministic Turing machine we find that it
can suggest more than one solution for any specific condition. The formula is:
δ: Q × Γ−→P(Q × Γ × {L, R}).
 Multi-dimensional Tape Turing Machine: It is a kind of Turing machine that can be
simulated by any one-dimensional Turing machine. It basically consists of a head which
can be rotated in any direction, thus it can be rotated in up, down, left or right direction
according to the choice of the controller [10].
 Multi-head Turing Machine: This is also a type of Turing machine that can be simulated
by any single head Turing machine [11]. The speciality of this type of Turing machine is
that is has more than one head, at least two. This allows the Turing machine to read and
scan multiple symbols on the same tape and also allows movement and writing
independently. All the heads sense the symbols at the same time.

6THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
 Multi-tape Multi-head Turing Machine: This is a type of Turing machine that can be
computer-generated by standard Turing machine. This Turing machine has multiple
heads and multiple tapes. Each tape is controlled by a single head [12].
Conclusion:
From the above report it can be said that Turing machine is one of the most important
part of the Automata theory which helps in the process of computing. The famous mathematician
Church and Turing invented a theory which determines the usage of the Turing machine in
computing the most complicated problems in the machine. With the help of the variants of the of
the Turing machines, the computation becomes much easier. There are in total seven variants of
the Turing machines which is currently in use. Each variants are used for some purpose or the
other. Turing machine which is considered to be the seven tuple system becomes more effective
and powerful with the help of these variants in use.

7THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
References:
[1] C.E., Shannon, A universal Turing machine with two internal states. Automata
studies, 34, pp.157-165, 1956.
[2] B.J. Copeland, and O., Shagrir, The Church-Turing thesis: logical limit or breachable
barrier?, Communications of the ACM, 62(1), pp.66-74, 2018
[3] M., Bickford, L., Cohen, R.L. Constable, and V., Rahli, Computability beyond church-
turing via choice sequences, In Proceedings of the 33rd Annual ACM/IEEE Symposium
on Logic in Computer Science (pp. 245-254), 2018, July.
[4] R.Q., Figueroa, D.A., Zamorano, G.J. Martínez, and A., Adamatzky, A turing machine
constructed with cubelets robots, Journal of Robotics, Networking and Artificial
Life, 5(4), pp.265-268, 2019.
[5] S., Kundu, R., Kundu, S., Kundu, A., Bhattachaijee, S., Gupta, S. Ghosh, and I., Basu,
Quantum computation: from Church-Turing thesis to qubits, In 2016 IEEE 7th Annual
Ubiquitous Computing, Electronics & Mobile Communication Conference
(UEMCON) (pp. 1-5), IEEE, 2016, October.
[6] M., Sipsev, Theory of Computation. Cenage Learning, 2020.
[7] K., Sgantzos, Implementing a church-turing-deutsch principle machine on a
Blockchain, Department of Computer Science and Biomedical Informatics, University of
Thessaly, Lamia, Greece, 2017.
[8] P., Rendell, Turing machine universality of the game of life (Doctoral dissertation), 2020.
[9] C.,Gulcehre, S., Chandar, K. Cho, and Y., Bengio, Dynamic neural turing machine with
continuous and discrete addressing schemes, Neural computation, 30(4), pp.857-884,
2018.

8THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
[10] A. Asperti, and W., Ricciotti, A formalization of multi-tape Turing
machines, Theoretical Computer Science, 603, pp.23-42, 2015.
[11] M., Kutrib, A. Malcher, and M., Wendlandt, Simulations of unary one-way multi-
head finite automata, International Journal of Foundations of Computer Science, 25(07),
pp.877-896, 2014.
[12] B., Reus, The Church-Turing Thesis, In Limits of Computation (pp. 123-148),
Springer, Cham, 2016.