Turing’s Theory of Computation Overview and Reference Books and Neural Turing Machines

Machine Learning Technology Artificial Intelligence Technology Natural Language Processing Technology Probabilistic Generative Models Algorithm ICT Technology Computer Architecture IT Infrastructure Technology Digital Transformation Technology Deep Learning Mathematics Technology Miscellaneous  Navigation of this blog
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.

コメント

Exit mobile version
タイトルとURLをコピーしました