LinuxQuestions.org
Visit Jeremy's Blog.
Home Forums Tutorials Articles Register
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > General
User Name
Password
General This forum is for non-technical general discussion which can include both Linux and non-Linux topics. Have fun!

Notices


Reply
  Search this Thread
Old 02-22-2023, 04:50 PM   #1
kernelhead
Member
 
Registered: Jun 2022
Posts: 247

Rep: Reputation: 5
Turing machine question


Tell me something, is a Turing machine real or imaginary? I know Turing himself invented a machine during the War to decipher the German secret code, but didn't know if it was a Turing machine or not ???

Also, are there any program on modern desktop computer, even in Linux, to run as being a Tuering machine?

Last edited by kernelhead; 02-22-2023 at 05:00 PM.
 
Old 02-22-2023, 05:49 PM   #2
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,780

Rep: Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081Reputation: 2081
Quote:
Originally Posted by kernelhead View Post
Tell me something, is a Turing machine real or imaginary?
It's imaginary. More specifically, it's a mathematical construct that's useful for proving things about computation in general. One characteristic of a Turing machine is that it has infinite tape (storage), which is obviously impossible to construct in the real world.

Quote:
Also, are there any program on modern desktop computer, even in Linux, to run as being a Tuering machine?
For example https://turingmachinesimulator.com/
 
Old 02-22-2023, 07:27 PM   #3
kernelhead
Member
 
Registered: Jun 2022
Posts: 247

Original Poster
Rep: Reputation: 5
Quote:
Originally Posted by ntubski View Post
It's imaginary. More specifically, it's a mathematical construct that's useful for proving things about computation in general. One characteristic of a Turing machine is that it has infinite tape (storage), which is obviously impossible to construct in the real world.



For example https://turingmachinesimulator.com/
Kewl. & thanks for the link!
 
Old 02-22-2023, 11:22 PM   #4
jailbait
LQ Guru
 
Registered: Feb 2003
Location: Virginia, USA
Distribution: Debian 12
Posts: 8,336

Rep: Reputation: 548Reputation: 548Reputation: 548Reputation: 548Reputation: 548Reputation: 548
During the 1930s Alan Turing was a mathematics professor in England. He wrote a theoretical paper on a set of rules that you could use to instruct a computer as to how to perform a particular computing task. In those days a computer was a person who computed. The was no such thing as a computing machine. Turing also proved that his rule system was a valid mathematical system. Thus when modern machine languages or modern programming languages are created some graduate student in math or computer science will prove that the new language is "Turing complete" which is an exercise in theoretical math. Turing also added an explanation in his paper which illustrated a theoretical machine which could do the same thing as a human computer.

As a prelude to WWII the Germans invented an encryption/decryption device which the British later called "Enigma". It takes time to encode and decode a message. It takes much longer to break the code. The more complex the code the longer all three tasks take. With the Enigma machines the Germans sped up the encryption and decryption times while making the encoding scheme so complex that it greatly increased the time it took to break the code. The Germans knew that any code could be broken but with Enigma it would take so long to break the code that the message would become irrelevant by the time it was broken. The Germans also changed all their codes on a monthly basis.

The first country to break the Enigma code was Poland. In 1938 or thereabout the Poles broke the code by having all of the math graduate students at the University of Warsaw work on the problem for six months. The Poles could then read all of the encrypted messages from that one month six months ago but nothing since.

After Poland fell the Polish, French, and British code breakers set up shop in Paris. When France fell the code breaking effort moved to England. They had rooms full of women who were mathematically adept working on breaking Enigma encoded messages. Somebody had the bright idea to call in the expert on computing procedures, Alan Turing, to see if he could speed up the code breakers to where the messages were still relevant after being broken.

Alan Turing looked at the problem. Then he designed a electro-mechanical machine to do most of the grunt work, ordered the parts, built the first computer, wrote the first computer programs, and began decrypting Enigma messages. It took a tremendous effort by management to get Turing to spend the time to teach other people what he was doing. Thus the computer was born.

Last edited by jailbait; 02-23-2023 at 11:00 AM.
 
Old 02-23-2023, 07:20 AM   #5
hazel
LQ Guru
 
Registered: Mar 2016
Location: Harrow, UK
Distribution: LFS, AntiX, Slackware
Posts: 7,567
Blog Entries: 19

Rep: Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447Reputation: 4447
Quote:
Originally Posted by jailbait View Post
Alan Turing looked at the problem. Then he designed a electro-mechanical machine to do most of the grunt work, ordered the parts, built the first computer, wrote the first computer programs, and began decrypting Enigma messages. It took a tremendous effort by management to get Turing to spend the time to teach other people what he was doing. Thus the computer was born.
And look how his grateful country repaid him! They arrested him for being gay, chemically castrated him and drove him to suicide.
 
Old 02-23-2023, 12:41 PM   #6
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,649
Blog Entries: 4

Rep: Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934
As for me, I personally suspect that there is actually much more in the wings than just this "brute-force solution."

Even before the war broke out, a gentleman known as Konrad Zuse had already invented an electromechanical programmable computer, and was trying to commercially exploit it. To me, it is therefore utterly impossible to consider that the Bletchley Park (and USA) codebreakers did not know of this, and were not advancing in very similar directions.

We are very-simply invited to presume that "this utterly brute-force break (the Bombe ...) was the only 'break' that they knew of," and that all of the subsequent work in order to fully exploit that 'break' had to be performed by humans.

To me, "this is nonsense." To me, this indicates "yet another Secret of Bletchley Park™" which is yet to be officially revealed.

Given that you had to know about Herr Zuse's innovations, it is utterly impossible to consider that you did not fully exploit them. Even a very-simple programmable device, such as Zuse's, could have completely avoided almost all of "the Bombe machines."

Therefore, why are we now to presume? "This is the official story, yes ..." Bletchley Park remains(!) "a Hall of Mysteries."

Last edited by sundialsvcs; 02-23-2023 at 12:54 PM.
 
Old 02-23-2023, 01:21 PM   #7
jailbait
LQ Guru
 
Registered: Feb 2003
Location: Virginia, USA
Distribution: Debian 12
Posts: 8,336

Rep: Reputation: 548Reputation: 548Reputation: 548Reputation: 548Reputation: 548Reputation: 548
Quote:
Originally Posted by sundialsvcs View Post
As for me, I personally suspect that there is actually much more in the wings than just this "brute-force solution."

Even before the war broke out, a gentleman known as Konrad Zuse had already invented an electromechanical programmable computer, and was trying to commercially exploit it. To me, it is therefore utterly impossible to consider that the Bletchley Park (and USA) codebreakers did not know of this, and were not advancing in very similar directions.
During WWII computers were independently invented in Britain, Germany, and the United States. Because of strict wartime secrecy in all the belligerent countries none of the developers knew of the other countries' efforts. Some people at the highest levels in the U.S. government knew of the Bletchley Park computers and the U.S. contributed some vacuum tubes (valves in British) to Bletchley Park but because of "need to know" the Americans who invented a computer to calculate artillery aiming tables never heard of the British efforts until well after WWII was over.

The British invented a computer to speed up breaking the Enigma code.

The Germans invented a computer to speed up solving partial differential equations by approximation to calculate the airflow over jet airplane wings.

The United States invented a computer to speed up calculating aiming tables for artillery.
 
Old 02-24-2023, 08:37 AM   #8
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,649
Blog Entries: 4

Rep: Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934
I don't think that ENIAC was actually built to "calculate artillery firing tables." I suspect that it was a code-breaking machine.

But, I also suspect that programmability was actually "a thing," long before the now-published "official histories," which quite conspicuously never refer to it. The only thing which they reference is "quite-brutish 'brute force.'" And so, I suspect that there is actually a wartime secret still hidden there. Given that "programmable" devices had already begun to be built even before war broke out, I cannot believe that they did not pursue this – somewhere in some "hut."

I suspect that it may well be that the algorithms are the real secret.

Last edited by sundialsvcs; 02-24-2023 at 08:39 AM.
 
Old 02-24-2023, 11:13 AM   #9
leclerc78
Member
 
Registered: Dec 2020
Posts: 169

Rep: Reputation: Disabled
Users (German soldiers) behavior also contributed to the downfall of Enigma. Language repetitive pattern like 'Heil Hitler', 'Fuch' ... proved fatal.

One of the article about Bletchley Park.
 
Old 02-25-2023, 10:32 AM   #10
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,649
Blog Entries: 4

Rep: Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934
To my way of thinking, "the 'official' history" always consisted of brute-force machines.

However, I do not believe that "this [primitive ...] level of equipment" could have actually ever achieved the levels of "consistent, everyday success" that we know they actually achieved. Faced with this deluge of traffic, "somehow they managed to break all of it, every day, by 10:00 AM each morning."

It is very easy to recognize that an algorithm could accomplish the same feat that those "mechanically rotating bombes" could have done, in very much less time. So, it is necessary to conclude that there are still "secrets" out there which they are not telling us.

Last edited by sundialsvcs; 02-25-2023 at 10:36 AM.
 
Old 02-25-2023, 11:17 AM   #11
rknichols
Senior Member
 
Registered: Aug 2009
Distribution: Rocky Linux
Posts: 4,776

Rep: Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212Reputation: 2212
It was only ever necessary to "break" one message each day. Doing that yielded the settings for the day, and all that day's messages could then be simply decoded using those settings. Yes, each message required a unique initial position for the rotors, but that position was transmitted, in the clear, three times at the beginning of the message.
 
Old 02-25-2023, 11:56 AM   #12
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,649
Blog Entries: 4

Rep: Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934Reputation: 3934
Yes, but nonetheless, I suspect that there were many more "secrets" out there which have yet been officially publicized.
 
Old 03-02-2023, 09:59 PM   #13
chrism01
LQ Guru
 
Registered: Aug 2004
Location: Sydney
Distribution: Rocky 9.2
Posts: 18,356

Rep: Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751Reputation: 2751
Another crib used by Bletchley was "the weather forecast, which was written in the same format each day." and Enigma allowed letters to be encoded by themselves.
The Germans also tended to use fixed formats for std msgs like weather reports for efficiency, but ofc this simplified the task for Bletchley.

They also used 'Gardening' https://en.wikipedia.org/wiki/Gardening_(cryptanalysis) as another way of persuading the Germans to generate a msg for which they 'knew' some of what the plaintext would be.
 
  


Reply



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
LXer: Geeks visit Bletchley Park, birthplace of the Turing machine LXer Syndicated Linux News 0 11-25-2015 10:15 PM
LXer: Prime Minister apologises over death of Alan Turing LXer Syndicated Linux News 0 09-11-2009 12:00 PM
LXer: Happy Birthday, Turing's Universal Machine LXer Syndicated Linux News 0 11-20-2008 06:20 PM
LXer: First female Turing Award winner named LXer Syndicated Linux News 0 02-22-2007 05:01 PM
Programming turing vexer Programming 3 04-25-2003 03:56 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > General

All times are GMT -5. The time now is 04:47 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration