Turing machine/Turing complete
-
Would an expert, preferably with a nice turn of phrase :), care to explain exactly what "Turing machine" and/or "Turing complete" actually mean, please?
I have done a little reading, maybe I should do more, but often you guys can clarify in a few words ;-)
I know about the infinite tape etc. "General purpose" came up a bit. I think I read about it saying something about "able to read the instructions and emulate any other machine". I believe "machine" can mean "language". So for example I'm thinking that if I can write, say, a Python compiler in C then we know C can fully read and "emulate" Python. Is this relevant, or am I off-track here? Also, does my Turing machine have to "halt", is that a thing?
In an attempted brief conversation about this elsewhere I was offered the following couple of points of wisdom:
Me:
oh, i meant to ask, what sort of languages are NOT Turing machines?
Answers:
iirc single stack is one example
very fun little property that double stack is turing equivalent, and queues are too, but single stacks aren’t
regexps are also not turing completeyou have to be careful how you define regexps, though
"pure implementations of NFAs": not turing complete. the regex implementations included with most programming languages: turing completeWhat is going on here? Am I trying to use a machine/write a language to be fully "general purpose" (able to emulate anything else), and a single stack is not up to it, but a queue is not? Am I trying to write a full C/Python interpreter as a regular expression?
Answers, please, on the back of a postage stamp ;-) Thank you! :)
-
Would an expert, preferably with a nice turn of phrase :), care to explain exactly what "Turing machine" and/or "Turing complete" actually mean, please?
I have done a little reading, maybe I should do more, but often you guys can clarify in a few words ;-)
I know about the infinite tape etc. "General purpose" came up a bit. I think I read about it saying something about "able to read the instructions and emulate any other machine". I believe "machine" can mean "language". So for example I'm thinking that if I can write, say, a Python compiler in C then we know C can fully read and "emulate" Python. Is this relevant, or am I off-track here? Also, does my Turing machine have to "halt", is that a thing?
In an attempted brief conversation about this elsewhere I was offered the following couple of points of wisdom:
Me:
oh, i meant to ask, what sort of languages are NOT Turing machines?
Answers:
iirc single stack is one example
very fun little property that double stack is turing equivalent, and queues are too, but single stacks aren’t
regexps are also not turing completeyou have to be careful how you define regexps, though
"pure implementations of NFAs": not turing complete. the regex implementations included with most programming languages: turing completeWhat is going on here? Am I trying to use a machine/write a language to be fully "general purpose" (able to emulate anything else), and a single stack is not up to it, but a queue is not? Am I trying to write a full C/Python interpreter as a regular expression?
Answers, please, on the back of a postage stamp ;-) Thank you! :)
@JonB It's been a while since my academic days but basically Turing machine is a bag of rules for computation that can be realized by all kinds of stuff - programming languages, physical machines (like a computer), biological (RNA/DNA based) or a minecraft level. There's probably a leaves soaring on the wind based Turing machine somewhere out there :)
You need a string of input, table of rules for output based on each piece of input and... that's pretty much it. The machine takes an input, based on the input writes an output to the same place, moves the string left or right and repeats. One of the possible rules is also to stop.
There are multiple variations on the theme - adding a stack, heap etc., but the basics are just an input string and table of rules for writing, moving the string or stop.Turing complete is a machine that can model itself. An example is your PC because it can emulate a PC. C compiler can be used to write a C compiler. Minecraft can be used to make a computer in which you can program Minecraft etc.
"Halting problem" is a separate thing, but often Turing machines come up when talking about it. A Turing machine does not have to halt. The problem goes along the way of "if you feed your machine some source code and an input stream can it determine if that program will ever reach stop condition".
Sounds simple, but gets hairy quick and you can geek around that pretty much endlessly if you want to.As to pythons, regexps and so on... don't worry about it :) It's mostly theoretical. Why would you want to write python in python? It's slow enough already :D
An example of something that is not Turing complete would be the universe, because there's not enough matter/energy/whatever to model all matter/energy/whatever. To represent everything you need at least everything+1. A more down to earth example would probably be any of the structural description languages like HTML, because the set of rules it provides is too restricted and wouldn't be enough to recreate itself (though admittedly I'm not up to date with the latest, so that might have changed ;)).
I guess you can fit that on a stamp if you use a small enough font :P
-
@JonB It's been a while since my academic days but basically Turing machine is a bag of rules for computation that can be realized by all kinds of stuff - programming languages, physical machines (like a computer), biological (RNA/DNA based) or a minecraft level. There's probably a leaves soaring on the wind based Turing machine somewhere out there :)
You need a string of input, table of rules for output based on each piece of input and... that's pretty much it. The machine takes an input, based on the input writes an output to the same place, moves the string left or right and repeats. One of the possible rules is also to stop.
There are multiple variations on the theme - adding a stack, heap etc., but the basics are just an input string and table of rules for writing, moving the string or stop.Turing complete is a machine that can model itself. An example is your PC because it can emulate a PC. C compiler can be used to write a C compiler. Minecraft can be used to make a computer in which you can program Minecraft etc.
"Halting problem" is a separate thing, but often Turing machines come up when talking about it. A Turing machine does not have to halt. The problem goes along the way of "if you feed your machine some source code and an input stream can it determine if that program will ever reach stop condition".
Sounds simple, but gets hairy quick and you can geek around that pretty much endlessly if you want to.As to pythons, regexps and so on... don't worry about it :) It's mostly theoretical. Why would you want to write python in python? It's slow enough already :D
An example of something that is not Turing complete would be the universe, because there's not enough matter/energy/whatever to model all matter/energy/whatever. To represent everything you need at least everything+1. A more down to earth example would probably be any of the structural description languages like HTML, because the set of rules it provides is too restricted and wouldn't be enough to recreate itself (though admittedly I'm not up to date with the latest, so that might have changed ;)).
I guess you can fit that on a stamp if you use a small enough font :P
@Chris-Kawa
Thanks a lot! I shall study some more.You talk about modelling/emulating itself. I had the impression what I read talking about being able to model/emulate other (Turing?) machines. Maybe that was "a general purpose" Turing machine.
What does it matter so much, what's the deep significance?
And while you're at it, is NFA "Non-deterministic Finite-state Automata"? What's the deal with them? :)
P.S.
Turing was English. Babbage was English. Just saying. Yet the whole world seems to use computers without paying us royalties. Typical :( -
@Chris-Kawa
Thanks a lot! I shall study some more.You talk about modelling/emulating itself. I had the impression what I read talking about being able to model/emulate other (Turing?) machines. Maybe that was "a general purpose" Turing machine.
What does it matter so much, what's the deep significance?
And while you're at it, is NFA "Non-deterministic Finite-state Automata"? What's the deal with them? :)
P.S.
Turing was English. Babbage was English. Just saying. Yet the whole world seems to use computers without paying us royalties. Typical :(You talk about modelling/emulating itself. I had the impression what I read talking about being able to model/emulate other (Turing?) machines.
Any Turing complete machine can emulate any Turing complete machine, self included as a special case.
What does it matter so much
Does it?
what's the deep significance?
Umm, 42 I guess...
"Non-deterministic Finite-state Automata"? What's the deal with them?
NieR: Automata is a better game :)
NFA's just loosen some restrictions. The output and movement of the input string doesn't solely depend on the input via constant table. Can be anything -> nondeterministic. An example would be a self rewiring CPU or something that gets rules from the stream of consciousness.Turing was English. Babbage was English. Just saying.
Turing's Enigma cracker was based on Polish bomba. Battle of Britain was greatly aided by (mostly) Polish squadron 303. You got the victory parade, we got Stalin. Typical ;)
-
You talk about modelling/emulating itself. I had the impression what I read talking about being able to model/emulate other (Turing?) machines.
Any Turing complete machine can emulate any Turing complete machine, self included as a special case.
What does it matter so much
Does it?
what's the deep significance?
Umm, 42 I guess...
"Non-deterministic Finite-state Automata"? What's the deal with them?
NieR: Automata is a better game :)
NFA's just loosen some restrictions. The output and movement of the input string doesn't solely depend on the input via constant table. Can be anything -> nondeterministic. An example would be a self rewiring CPU or something that gets rules from the stream of consciousness.Turing was English. Babbage was English. Just saying.
Turing's Enigma cracker was based on Polish bomba. Battle of Britain was greatly aided by (mostly) Polish squadron 303. You got the victory parade, we got Stalin. Typical ;)
@Chris-Kawa said in Turing machine/Turing complete:
You got the victory parade, we got Stalin. Typical ;)
Well that's your fault for being so far East, you should have thought about that before placing Poland there. Anyway you got Lech Walesa, we got Boris Johnson, how's that fair?
-
@Chris-Kawa said in Turing machine/Turing complete:
You got the victory parade, we got Stalin. Typical ;)
Well that's your fault for being so far East, you should have thought about that before placing Poland there. Anyway you got Lech Walesa, we got Boris Johnson, how's that fair?
The Turing Paper might be interesting for you, if you haven't found it already :)
The fun thing is, before and during Turings study, a "computer" was a human, who computes things and not a machine.
The whole topic caused computability theory and theoretical computer science flashbacks ;D
@JonB said in Turing machine/Turing complete:
Anyway you got Lech Walesa, we got Boris Johnson, how's that fair?
Poland got Krakow sausage, you got Haggis ;-)
If debugging is the process of removing software bugs, then programming must be the process of putting them in.
~E. W. Dijkstra
-
The Turing Paper might be interesting for you, if you haven't found it already :)
The fun thing is, before and during Turings study, a "computer" was a human, who computes things and not a machine.
The whole topic caused computability theory and theoretical computer science flashbacks ;D
@JonB said in Turing machine/Turing complete:
Anyway you got Lech Walesa, we got Boris Johnson, how's that fair?
Poland got Krakow sausage, you got Haggis ;-)
-
@Chris-Kawa
Thanks a lot! I shall study some more.You talk about modelling/emulating itself. I had the impression what I read talking about being able to model/emulate other (Turing?) machines. Maybe that was "a general purpose" Turing machine.
What does it matter so much, what's the deep significance?
And while you're at it, is NFA "Non-deterministic Finite-state Automata"? What's the deal with them? :)
P.S.
Turing was English. Babbage was English. Just saying. Yet the whole world seems to use computers without paying us royalties. Typical :(@JonB said in Turing machine/Turing complete:
Yet the whole world seems to use computers without paying us royalties.
I await with great anticipation the moment when the inventor of the wheel will come out of hiding and claim royalties on... basically everything?
(Z(:^
-
@JonB said in Turing machine/Turing complete:
Yet the whole world seems to use computers without paying us royalties.
I await with great anticipation the moment when the inventor of the wheel will come out of hiding and claim royalties on... basically everything?
-
@JonB said in Turing machine/Turing complete:
@sierdzio Well, he was English too......
Stonehenge is round, you have a strong case there :D
... uh but so is Gobekli Tepe.
-
@Chris-Kawa said in Turing machine/Turing complete:
You got the victory parade, we got Stalin. Typical ;)
Well that's your fault for being so far East, you should have thought about that before placing Poland there. Anyway you got Lech Walesa, we got Boris Johnson, how's that fair?
