Overview of Turing’s Theory of Computation
Turing’s theory of computation, proposed by Alan Turing, will be a theory that theorizes the fundamental concepts of computers. This theory provides the basis for understanding how computers work and what computation is, and consists of the following elements
- Turing Machine: The Turing machine serves as the basic computational machine in the theory of computation. This machine can write and read symbols on a paper tape, and performs computations by reading, rewriting, and moving symbols on the paper tape according to a state transition function. For the automata theory of finite state machines, see “Automata and State Transitions/Petri nets and Automated Programming.
- Turing completeness: Turing completeness is the notion that a given machine has the same computational power as all Turing machines. In other words, a Turing-complete machine can perform any kind of computation.
- Countability and noncountability: In Turing’s theory of computation, countability means that a problem can be solved by an algorithm. Non-countability, on the other hand, means that a problem cannot be solved by an algorithm. For example, the halting problem is a non-countability problem and cannot be solved by an algorithm. See “Overview and Implementation of Boolean SAtisfiability (SAT)” for an overview of the NP-complete problem, in which the correctness of a given candidate solution can be verified in polynomial time,
- Turing Test: The Turing Test is a test to evaluate whether an artificial intelligence can think like a human. The test compares whether a human and a computer answer the same questions. If the computer can answer the same questions as a human, it is considered to be thinking like a human. For more information, please see “Conversation and AI (Turing Test Considerations).
Reference books on Turing’s theory of computation
An introductory reference book on Turing’s theory of computation is Turing’s Introduction to the Theory of Computation.
The English mathematician Turing came up with the idea of the “Turing machine,” a mathematical model of a universal computer, to solve Hilbert’s “decision problem. This “Turing machine” became the mathematical basis for guaranteeing the universal applicability of computers.
Using the “Turing Machine,” Turing thoroughly examined the act of computation. He showed that showing a procedure and being able to compute are the same thing. The procedure is called an algorithm, which is now called software.
This book explains the Turing machine as a principle of computers, as well as the famous “Turing machine halting problem,” which solved the decision problem, in an easy-to-understand manner. Furthermore, computational complexity and one of the seven most difficult problems, the P=NP problem, are also explained in an easy-to-understand manner.”
Introduction to Turing's Theory of Computation
Preface
Chapter 1 Computation for Humans
Computation is a Human Activity
One Tokyo Tower is Enough (Concept of Number)
Summarizing Numbers
The Concept of Zero
Zero does not appear when numbers are expressed in kanji
Addition
Subtraction
Multiplication and division
Adding and Subtracting Numbers Together
Adding or Subtracting Change? Subtracting?
Steps to Calculate Change
There are always steps involved in performing a calculation.
Procedures are combined to form complex procedures
Basic elements of a procedure
Sequence
Branching(if)
Repetition
What is computation for humans?
When in a certain state, a decision is made based on external stimuli, and then the process moves to the next state.
Calculation
What is calculation?
To measure and count the quantity of things
count
Cash up
To derive a numerical value according to a formula, such as addition, subtraction, multiplication, etc.
calculate
To predict the result or outcome to some extent and replace it with a part of the schedule
calculate
Human judgment and prediction
Check if there are any delays in trains and buses
If there are no delays, go to work on the normal course
Finish
If there is a delay
Check if there is time to eat breakfast lua
If there is time, eat as usual
End
If there is no time, commute without eating
End
Actions such as "judgment" and "prediction" can also be called "calculation
Chapter 2: Attempts to Make Machines Do the Computing
Calculation for computers
computer
Latin computeare
Calculation
Addition of two numbers
com (together) + putare (think)
A computer cannot think for itself.
Given a history or a set of conditions as input
It calculates them silently "according to a predetermined procedure.
Data is input and the result of a certain calculation is output.
Does the computer think?
There are limits to the computing power of computers.
Algorithm - a representation of a computational procedure
When a computer performs an action, it has a "problem to solve" first, and then it performs the necessary steps one at a time.
It can't just do it for the time being like a human being.
It needs to be given instructions.
Must include everything that needs to be done
There must be an end point.
Can be done by anyone with written instructions
Good and Bad Algorithms
There are multiple algorithms to solve a problem
I want to divide the ribbon into 8 equal parts
Measure it with a tape measure, divide by 8, and cut it with scissors while measuring its length.
Fold it in two and cut the middle with scissors, fold it in two more and cut the middle with scissors, fold it in two more and cut the middle with scissors
To compare multiple algorithms, compare the amount of work (computation)
This is true for all calculations.
Computer computation is "a state of affairs that is changed by external stimuli, and the state of affairs changes
Structure of computer computation procedures
Basic structure of procedures in computer calculations
Sequential
Branching
Iteration
Analog and digital computers
Number table
Calculate with gears
Pascal's Gear Calculator
Pasqualine
Addition and subtraction
Leibniz
Multiply and divide to decimals
Steam-powered calculator
Charles Babbage
Automatically creates error-free number tables
Calculates according to certain rules
gradient engine
Multifunctional calculator
Pascal and Leibniz's opportunity can only support numbers from the outside
Babbage's opportunity supports calculation and numerical values from the outside and determines the calculation procedure by itself
Leibniz predicted Turing
Gottfried Wilhelm Leibniz, a player in symbolic logic
Launched the concept of a "universal language"
Binary system
Only two symbols are needed to understand that "computation" can be replaced by mechanical work
Roots in the Chinese I Ching (Yin-Yang)
Two symbols are enough to code all communication
Francis Bacon (1623)
To calculate is to count the sum of many things added together, or to know what you get when you take one thing out of another
Inference is the same as addition or subtraction
The Development of Mathematics in the Late 19th Century
Chapter 3: Automata and Turing Machines
Decision Problem
A computational model is a model that represents an algorithm
Turing Machine
Is it possible to check whether something is provable or unprovable by a mechanical procedure?
Mechanical procedure" → Algorithm
Is it possible to write down a procedure that computes (checks) whether something is provable or not?
Turing's paper
Computable numbers and their application to decision problems
Turing machine as a guarantee of computer versatility
Proof of impossibility
3-1 Automaton
Would you like a hamburger? (State)
Computation" is "a change of state by a change of a certain state by an external stimulus.
What is "state"?
The state of a person or thing at a given point in time
What is the point of a game?
The game itself is an automaton
Automaton
rock, paper, scissors
The machine of the automaton
Automaton is one way to show an algorithm
Vending machine
Air conditioner
Relationship between automaton and computation
Automaton: A term used in Europe to describe an automatic machine or puppet based on a variety of ideas from long ago.
Software is an algorithm "programmed" using a programming language
All software is an automaton
When a computer makes a decision, it has a "state" of things and a set of rules that indicate what it should do when it receives an input in each state, and it makes a decision according to those rules and changes its state as a result.
It is possible to express the rules of processing by the computer" = "it is possible to express how the state changes}".
3-2 Turing's theory of computation
Appearance of Turing
A computational model in which the input/output of an automaton is extended to leave the result in the form of a tape, based on the idea of "using an infinite number of tapes".
Structure of Turing machine
Is there a mechanical procedure (algorithm) to check whether a computation is possible or not?
Mathematical proof of the above
How does a human do the computation?
Replace human with "a machine that can take several states
Example: Calculate (10+2)x3
(1) Write "10" on a piece of paper
(2) Add 2 to the number written in (1) (on the paper, add "+2" and probably write "10+2=12")
(3) Multiply the result of (2) by 3 (on the paper, add "x 3" and probably write "12x3=36")
(4) End
Turing machine
Stimuli from outside (tape and head)
The rule table supports the movement of the head and the reading and writing there
The head can only move right or left one square at a time (only 3 pans of movement (left/right) and no movement).
The squares are not numbered.
If the head moves 3 pans to the right, it moves to the right 3 times.
Head movement and tape read/write rules
Expression of the rule table
If the symbol of a square is 0, write 1 in that square, then move the head to the right
0, P1, R
If you don't know the state, you're in trouble.
If the symbol of a square is 0 in state 1, write 1 in that square, then move the head to the right
State 1 : 0, P1, R
Simple Turing machine
Let's try 3+2
Turing machine that alternates between 0 and 1
Turing machine doing multiplication
Why is it so hard to compute a Turing machine?
Given a formula (something to be proved), can you mechanically determine whether it can be proved or not?
Given a formula (something to prove), is there an algorithm to compute it?
Can it be computed
Can it be written in an algorithm?
Can be described by a Turing machine
What can be described by a Turing machine is an algorithm
What can be described by a Turing machine is called an algorithm
An algorithm that can be executed by a human (or a computer) can be executed by a Turing machine
Church-Turing's proposal
What can be described by a Turing machine is "computable
Infinite yet finite!
Algorithm that computes one-third
Computable means
It is not the ability to perform four arithmetic operations.
It means that a state of affairs can be described in a finite number of steps by changing the state of affairs due to external stimuli.
How many Turing machines are there?
What does it mean to express an algorithm as an integer?
In order to count algorithms, the table representing Turing machines is transformed to represent them as integers.
Since we can represent an algorithm as an integer, we should be able to count it
It can be computed.
Cannot be computed means that the algorithm cannot be numbered as an integer
Algorithms are not in the list of algorithms
Future software can be counted
Why distinguish between doable and uncountable?
Turing machines are software
Is a computer a Turing machine?
A Turing machine with one purpose is software, not today's computers
Computers are not "single-purpose Turing Machines" but "universal Turing Machines
Chapter 4: Decision Problem
Computable, not computable
Computable (computable) = can be described by an algorithm
Incomputable = no algorithm exists to solve the problem
Yes or No?
Decision Problem
Yes or No decision problem
If an algorithm exists to solve a problem that requires only Yes or No as an answer, then the problem can be answered with Yes or No
To determine if a problem is computable, it is possible to transform the problem into a decision problem with a final Yes or No answer.
Is there a Turing machine that never stops?
The mathematicians of Hilbert's time sought formulas that "if it can be expressed in terms of a certain pattern of formulas, there is nothing that cannot be expressed within that pattern of formulas."
If it is proven that "whatever mathematical world you create, there is something that cannot be expressed within that world," then the hypothesis that "you can create a mathematical world that does not contradict itself" is wrong.
The Liar's Paradox
The Cretans are liars," said the Cretan.
We don't know what doesn't stop.
Stoppage-determination Turing machines cannot be built
The haltingness determination problem is incalculable
We finally got there.
Five years before Turing (1931), Goeter also showed with his Incompleteness Theorem that "there are propositions that can neither be proved nor disproved.
Similar to Goeter's approach to Goeter's Goeter number
Chapter 5: The Universal Turing Machine
Being versatile = being monomaniacal
What is the Universal Turing Machine?
How the Turing Machine works
The Seeds of Imitation
Now it's time to execute by proxy
Is a Computer a Turing Machine?
Let's Write a Turing Machine in Japanese
Let's show the location and movement of the head
Conditional branching
To write a program neatly
To put together a fixed process
Delete
Compare
mark up
Note: Use all of the verbs to define CISC?
Please also see options. Don't call it an "implicit."
Don't make a function infinite by using different function arguments
To realize a universal Turing machine
The smallest elements that make up a universal Turing machine
Basic Functions
Search for characters
Erase
copy
rewrite
compare
Base function
A function that combines a set of processes into one
Order
Conditional branching
Iteration
All calculation models are the same
Church's model
Λ-calculus
Everything that can be said to be computable can be expressed concretely in a λ-calculus
Kleene's "inductive function
Other models
Recursive functions
Random Access Machine
Programmable RAM
Markov Algorithm
Chomsky's phrase structure syntax
Chapter 6: Computational Complexity
Procedures for searching
Robot search engines
Collect data from web pages
Extract keywords and register them in a database for each keyword
Display search results according to user information
Calculate 1+2=3
Define the program
How to determine if a calculation can or cannot be performed
Check by having it run pseudo-automatically in a calculation model using an automaton or Turing machine
Amount of computation
Santa Claus' dirty socks
Computer Science Unplugged (Computer Science Education)
Proposed by Dr. Tim Bell of New Zealand
Search among 1024 pieces
Problem to determine if there are the same number of integers
Given 4 integers, determine if all integers are different
Calculate the time required for execution
Represent the above procedure in text and diagrams
If all numbers are different
Time Calculation
What affects the time required for execution?
How to express the time complexity
Order (Is it an order? No, it is not)
Time complexity: Order O
Can't know tomorrow's forecast tomorrow?
Doubling does not necessarily mean doubling
Good Algorithm Order
Bad Algorithm Order
Let's compute the order
Memory required for execution
Grouping of solvable problems
Class P
Polynomial Time Computable Class
Can't help or not?
Deterministic Algorithm
Choose the best one among many combinations
Algorithm to choose only one understanding
Non-deterministic algorithm
Checking after the best guess
Class NP
Non-deterministic Polynomial
No polynomial-order algorithm has been found to find the best answer, but there is a polynomial-order algorithm that uses a nondeterministic algorithm to find the answer and then checks whether it satisfies the conditions of the problem.
Characteristics of nondeterministic algorithms
Review of P and NP
Relationship between P and NP
P=NP?
Deterministic Algorithm: Searching in a vacuum
Non-deterministic Algorithm: Find several candidates that satisfy the problem and check later if they fit the problem
Prime Factorization
NP and therefore secure ciphers
What is the meaning of the distinction between NP and P?
NP-complete
First NP-complete problem
NP-hard
Memory computational complexity of P and NP
Chapter 7: The Road to Computers
Review of Turing's Theory of Computation (Essence)
Making decisions, predicting, and reasoning
What can be described by a Turing machine is an algorithm
A program is what describes an algorithm
Theory that connects logic and computation - Pooled Algebra
Physical realization of a Turing machine is a computer
Logical expressions
"If it were ~, then it would be ~"
Pooled Algebra
Replace logical expressions with calculations so that they can be handled mechanically
Genius Shannon's inspiration
Shannon's Circuit Realization of Pooled Algebra
A Symbolic Analysis of Relay and Switching Circuits
Every algorithm can be converted into a logical computation by Poole algebra
Furthermore, Poole algebras can be mechanically computable as Cairo.
Leibniz's dream and the number of pooled units
Leibniz envisioned a digital computer with binary computation
Descartes' symbolic representation by letters
And the computer was completed
Completion of the actual computer by von Neumann
Non-von Neumann type computer
Different realization from the von Neumann type of Turing machine
Why do computers use binary numbers?
Binary numbers reduce variations in processing
Four Playing Cards? (How Binary Numbers Work)
Addition of Binary Numbers
Logic operations
Factual Propositions
AND (logical conjunction)
OR (logical OR)
XOR (exclusive disjunction)
NOT(Negation)
Turing Machines and Logic Circuits
If you buy AND, OR, XOR, and Mira, all logic can be expressed by operations
Afterword
A more historical stream of events is “The Universal Computer: The Path from Lampnitz to Turing”.
Pre-Computer HistoryThe genealogy of mathematical logic from Leibniz to Turing forms the theoretical backbone of computers and even foreshadows the advent of AI. The struggles of the logicians who devoted themselves to the construction of a symbolic system that would encompass the entire range of human thought through the symbolic representation of algebra are described, incorporating the background of the times. In addition, the personalities of the seven logicians who make up the book are described based on a wealth of episodes. The mathematical explanations, which would be too verbose if incorporated into the text, are incorporated into the original notes to create a semi-independent structure. Because the book is written in a relatively simple manner, it is a must for readers of high school age and above who are interested in the origins of computer logic, as well as for readers interested in the origins of logic in artificial intelligence.”
The Universal Computer From Lampnitz to Turing Martin Davis
Introduction
Chapter 1: The Leibnizian Dream
Leibniz's "brilliant idea
To stay in Paris
Later Life in Hanover
An Attempt at a Universal Symbol
Chapter 2: Poole Converts Logic into Algebra
Poole's life of tribulations
Poole's Logic Algebra
Poole and the "Leibniz Dream
Chapter 3: Frege: From Breakthrough Achievement to Despair
Frege's Conceptual Notation
Frege, the Founder of Formal Syntax
Why Russell's letter was a devastating blow
Frege and the Philosophy of Language
Frege and the "Leibniz Dream
Chapter 4: Cantor, a Tour of the Infinite
Engineer or mathematician?
The discovery of infinite sets of different sizes
Cantor's search for transfinite numbers
Diagonal Argument
Depression and Tragedy
Toward a Deterministic Question?
Chapter 5: Hilbert's Rescue Program
Young Hilbert's Mathematical Success
Toward a New Century
The Ghost of Kronecker
Supermathematics
Catastrophe
Chapter 6: Goethel overthrows Hilbert's plan
A Hidden Curse: Kronecker's Ghost
Undecidable propositions
Goeter as a Programmer
The Meeting in Königsberg
In the throes of love and hate
Hilbert's Aphorisms
The Sad End of a Strange Man
Appendix: Goethel's Undecidable Propositions
Chapter 7: Turing Envisions the General Purpose Computer
The poster child of the British Empire
Hilbert's "Decision Problem
Turing's Analysis of the Computational Process
Operation of Turing's machine
Turing's use of diagonal argument
Algorithmically unsolvable problems
Turing's Universal Machine
Turing's stay in Princeton
The World War for Alan Turing
Chapter 8: The Universal Computer Realized
Who Invented the Computer?
Von Neumann and the Moore School Group
Alan Turing's ACE
Eckert, von Neumann, and Turing
The Rewards of a Gracious Nation to Heroes
Chapter 9: Beyond Leibniz's Dream.
Computers, Brains, and Minds
Final Chapter
Neural Turing machine
Neural Turing machine refers to a computational model that combines a neural network and a Turing machine.
Ordinary neural networks treat input data as numerical data and perform calculations based on numerical operations, while Turing machines perform calculations based on symbolic operations. Neural Turing machines combine both of these to achieve more advanced computation.
In a neural Turing machine, input data is treated as a sequence of symbols, which are then processed by a neural network. In the process of processing, the neural network can learn patterns of symbol sequences and generate symbol sequences. By incorporating the function of a Turing machine, the Turing machine can be executed with the symbol sequence generated by the neural network as input. This allows the neural Turing machine to perform more complex computations than conventional neural networks.
Neural Turing Machines have attracted attention as a particularly useful computational model in fields such as artificial intelligence and natural language processing, but at present, the implementation of Neural Turing Machines is still in the research stage due to technical difficulties.
コメント