Turing’s Universal Machine

Perhaps the Intel core i9 of its Time?

i9

Ah, just look at that beauty!

We are back with some new fresh lemons today!

It all starts off from the early 20th century, when a decent chap named as Alan Turin decided to represent his unique invention:

Not a machine, yet an enlightened Theoretical Idea.


 

as always, bio goes first

AT

(1912-1954)

Alan Turing, in full Alan Mathison Turing, (born June 23, 1912, London, England—died June 7, 1954, Wilmslow, Cheshire), British mathematician and logician, who made major contributions to mathematicscryptanalysislogicphilosophy, and mathematical biology and also to the new areas later named computer sciencecognitive scienceartificial intelligence, and artificial life.

Seems a lot to know for a ‘Yankee-caller’ fellow chap from Great Britain, doesn’t it?


 

ok, background conceived, now what?

As mentioned before, a Turin Machine is  not a real machine, it is a theoretical idea which plays an important role in the foundations of mathematics and computer science. Turing Machine’s are useful for studying algorithms, they provide a language for describing certain abstract concepts in a precise way.

TM

Every time man, every time.

Constructive details:

A Turing Machine is capable of writing down a sequence of 0’s and 1’s on an infinite strip of tape. The machine has a scanner; it is “aware” so to speak of only a single square at a time. It’s capable of scanning this square, and of moving the scanner one space left or right.

The machine is also capable of existing in a number of states, and the table of instructions tells the machine what to do next based on what state it is in, and what symbol is being scanned.

The number of possible states of the machine depends on the problem which it is capable of solving. To keep track of what state the machine is in, it makes use of a private strip of tape, which is called the “state register”.

TMS

The “P” in the scheme

In fact, according to some sources, the machine we know today–the indigenous motherboard of all calculating systems–is named as the “Post-Turing Machine” due to its alternative characteristics embedded in its system.

Now, while getting closer and closer to the concept, there are only 7 instructions it can handle:

  1. Print 0
  2. Print 1
  3. Move left one square
  4. Move right one square
  5. If scanned square is 0 move to instruction i
  6. If scanned square is 1 move to instruction j
  7. Stop

As an example, the Post-Turing Machine which writes down the sequence 101010… forever would begin with a strip of tape where each square has a 0 in it, and it would have the following instruction set.

Image result for strip of tape turing machine

  1. [2] Print 1
  2. [4] Move Right
  3. [1] Print 0
  4. [4] Move Right
  5. [510] If scanned square is 0, goto instruction 1

can anyone explain what in the world does the [?] mean?

This, dear readers, recalls to another term in the Turing Machine industry known as the Description Number. The Turing Machine from the previous example has the description number 2414510, you can read the description number from left to right as: do instruction 2 (print 1), do instruction 4 (move right), do instruction 1 (print 0), do instruction 4 (move right); 510 means do instruction 5, which is to check if the scanned square is a 0, and then jump to instruction number 1 if it is. In other words a 0 in the description number acts like a closing parenthesis for a jump instruction.


 

Sounds scientifically cool, yet where was it used?

In general, a Turing Machine is capable of solving perhaps any mathematical problem derived from the mind of a human being, with the notice of ‘unlimited time’ taken into account.

In other words, a Turing Machine can solve any problem for which there is an effective procedure for solving that kind of problem. An effective procedure is an algorithm which is guaranteed to provide a correct solution to a problem of a certain type.

An example of an effective procedure is long division. For any two numbers, there is a Turing Machine which will do long division to calculate the result of the problem.

Image result for long division


A better question would be: what can’t it do?

The amazing fact is that there are some classes of problems for which no algorithm exists to solve the problem in general.

An example of this type of problem is to find an algorithm to decide if a polynomial with rational coefficients can be solved in rational integers.


so as you see, Uniqueness is a broad term and nothing has to be keeping you from being a part of it!

Thanks for reading this article!

Поделиться постом
Written by Shohruh Artaman
A typical writer illustrating typical principles
Have your say!
0 0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>