The Church Thesis Turing Machine Assignment
Added on 2022-09-09
9 Pages1988 Words32 Views
|
|
|
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:
THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS
Name of the Student:
Name of the University:
Author note:
THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS1
Table of Contents
Introduction:....................................................................................................................................2
Church Turing Thesis:.....................................................................................................................2
Variants of the Turing Machines.....................................................................................................2
Conclusion:......................................................................................................................................6
References:......................................................................................................................................7
Table of Contents
Introduction:....................................................................................................................................2
Church Turing Thesis:.....................................................................................................................2
Variants of the Turing Machines.....................................................................................................2
Conclusion:......................................................................................................................................6
References:......................................................................................................................................7
THE CHURCH THESIS: TURING MACHINE AND ITS VARIATIONS2
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.
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.
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents