Turing machines

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
Firnagzen
Posts: 198
Joined: Wed Jan 16, 2008 9:29 am UTC

Turing machines

Postby Firnagzen » Mon Nov 09, 2009 9:41 am UTC

So I read a couple of articles about turing machines. I understand how they work, and can very, very slowly work out simple programs and decipher programs, but it's hideously inefficient. (Basically me actually carrying out the program like that guy in comic 505, only far less awesome.)

I'm vaguely interested in learning more, so could someone point me at a decent resource that doesn't require much background to understand? More pertinently, how exactly do people design turing machines to carry out specific computations, and how you decipher it? (I'm thinking there's better methods than brute forcing it.)
Life may suck, but there's nothing else to do.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: Turing machines

Postby makc » Mon Nov 09, 2009 10:30 am UTC

Firnagzen wrote:how exactly do people design turing machines to carry out specific computations
if we knew how people program things, we could write a program to do that :)

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Turing machines

Postby Berengal » Mon Nov 09, 2009 4:24 pm UTC

We don't program turing machines, we program turing complete machines. There's a huge difference, in that many things are turing complete, and they don't neccessarily have to look anything like a turing machine. This means we can add things such as registers, "stateless" operations, random access memory etc. etc. that make things much easier to work with and reason about (for programmers. For mathematicians, the simplicity of turing machines might be easier to reason about when proving various properties about them, which are valid for every other turing complete machine as well).

Some turing complete systems don't even look like machines at all. For example, lambda calculus is also turing complete, but doesn't have state, symbols or even memory, just variables and variable binding.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

octonion
Posts: 22
Joined: Mon Nov 09, 2009 9:24 pm UTC

Alternatively, try lambda calculus

Postby octonion » Mon Nov 09, 2009 10:33 pm UTC

As Berengal mentioned, there are several different "fundamental" systems of computation, all equally powerful. (That is, you can write an interpreter for any of the systems using any other system.) Personally, I find Turing machines very confusing and prefer the lambda calculus. If Turing machines are imperative programming taken to extremes, lambda calculus is functional programming gone wild: everything is a function, even numbers and booleans.

There's an awesome book by Benjamin Pierce called Types and Programming Languages that shows how you can build up full programming languages by extending the lambda calculus. It's a graduate textbook, so not for general audiences at all, but Pierce is a very good writer. It's the book that inspired Audrey Tang to write pugs. If you're serious about programming language theory and fundamentals it's worth checking out, especially if you can get a library copy. An early chapter also discusses how to do real programming using just the pure lambda calculus with no extensions, which is basically what you're talking about.

Oh, you might also want to take a look at Brainf*ck. It's the closest programming language I know of to a raw Turing machine, and people have figured out to how to write non-trivial programs in it. (Well, sort of non-trivial anyway.)

User avatar
Firnagzen
Posts: 198
Joined: Wed Jan 16, 2008 9:29 am UTC

Re: Turing machines

Postby Firnagzen » Tue Nov 10, 2009 1:01 am UTC

I see. So no one actually uses turing machines in their 'pure' form except as thought experiments? Ah, well. i'd figured that since they were among the simplest possible computing devices, they might be fun to mess with.

Also, makc, we know how people speak. We can list out rules of grammar. Go on, program a machine to carry out an intelligent conversation. :wink:

EDIT: Here's a thought. What other kind of turing complete system can I construct with standard CMOS functions? (Logic gates, memory cells etc.)
Life may suck, but there's nothing else to do.

poohat
Posts: 230
Joined: Mon Apr 07, 2008 6:21 am UTC

Re: Turing machines

Postby poohat » Tue Nov 10, 2009 3:28 am UTC

The Turing Machine is an abstract construct used to study the theory of computation, you wouldnt actually write a program for one in practice (other than to help you learn the basic idea of what theyre doing). All modern programmings are turing complete, which means that they can implement any program which can run on a turing machine.

A good resource which isnt too technical is the first couple of chapters of Roger Penrose's "Emperors New Mine".

Firnagzen wrote:I see. So no one actually uses turing machines in their 'pure' form except as thought experiments? Ah, well. i'd figured that since they were among the simplest possible computing devices, they might be fun to mess with.
Not just thought experiments, mathematical proofs. And you could write a program for one if you wanted.

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Turing machines

Postby 0xBADFEED » Tue Nov 10, 2009 7:32 pm UTC

Firnagzen wrote:Also, makc, we know how people speak. We can list out rules of grammar. Go on, program a machine to carry out an intelligent conversation. :wink:

Your analogy is incorrect.

You're assuming that grammatically correct implies intelligible, which is completely untrue. For example, My purple obfuscates the elevator is both grammatically correct and unintelligible. It's trivial to construct a computer program that always produces grammatically correct sentences. There is much more to intelligent speech than grammar, e.g. the semantics of a sentence. If there were a formal method for determining and representing the semantics of natural language, then we could construct a computer to hold an intelligent conversation. Much like if there were a formal system that accurately modeled human reasoning and insight we could also build a computer to do that.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Turing machines

Postby headprogrammingczar » Tue Nov 10, 2009 8:27 pm UTC

0xBADFEED wrote:My purple obfuscates the elevator

That makes perfect sense! Also, I think you need to take your sarcasm detector in for repairs.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Turing machines

Postby 0xBADFEED » Tue Nov 10, 2009 9:05 pm UTC

headprogrammingczar wrote:Also, I think you need to take your sarcasm detector in for repairs.

I knew that Firnagzen's reply was tongue-in-cheek.

I was just saying his logic didn't follow and that there was more truth in makc's response than he seemed to pick up on.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: Turing machines

Postby makc » Tue Nov 10, 2009 10:19 pm UTC

0xBADFEED wrote:Your analogy is incorrect.
^^what he said.

no really, you asked "how exactly do people design turing machines to carry out specific computations" not "how turing machines work".

User avatar
Firnagzen
Posts: 198
Joined: Wed Jan 16, 2008 9:29 am UTC

Re: Turing machines

Postby Firnagzen » Wed Nov 11, 2009 10:01 am UTC

Actually, I think my analogy was fine. There are general guidelines that don't necessarily dictate that a sentence makes sense, but are helpful/necessary to be able to do things efficiently. Similarly, there might be guidelines that help in programming. Right? In programming, there might not be hard and fast rules to program, but there might well be rough outlines, handy snippets of commonly used code etc.
Life may suck, but there's nothing else to do.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: Turing machines

Postby makc » Wed Nov 11, 2009 10:40 am UTC

There are general guidelines that don't necessarily dictate that a sentence makes sense, but are helpful/necessary to be able to do things efficiently. Similarly,...
similarly you can "generate" a program following syntax rules that does compile yet doesnt work. Easiest example I can think of is (in pseudocode)

Code: Select all

var x = 1 / 0;
then, even if it does work with no run-time errors, it will likely output random garbage. I talk about real-life programs here, but this is equally applicable to turing machines.

Speaking about "turing", the fact that turing test prize is not claimed yet proves, again, the wrong with your analogy.

there might well be rough outlines, handy snippets of commonly used code etc.
that's a different question, isn't it. it is like asking for a bunch of english text when you try to learn english, but not for an explanation how to talk.

edit: sorry for trolling, however, I do not have link to such resources :)

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Turing machines

Postby Xanthir » Wed Nov 11, 2009 3:49 pm UTC

makc wrote:
There are general guidelines that don't necessarily dictate that a sentence makes sense, but are helpful/necessary to be able to do things efficiently. Similarly,...
similarly you can "generate" a program following syntax rules that does compile yet doesnt work. Easiest example I can think of is (in pseudocode)

Code: Select all

var x = 1 / 0;
then, even if it does work with no run-time errors, it will likely output random garbage. I talk about real-life programs here, but this is equally applicable to turing machines.

In any halfway-decent language that will output "Infinity" or something similar.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: Turing machines

Postby makc » Wed Nov 11, 2009 3:57 pm UTC

perhaps one could write meaningful program generator that generates programs creating real art? using, for example, turtle graphics and random set of rules... on the other hand, that would be no different from generating the end result in postscript format.

p.s. again, we need a turing test here: have judges running the program and deciding if it was written by human :)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Turing machines

Postby Yakk » Thu Nov 12, 2009 3:00 am UTC

The Turing Machine is not supposed to be all that useful a computational model for doing computation.

Nor is it supposed to be obviously sufficiently powerful.

Instead, it is about how simple and pared down the thing is, yet it is sufficient to run any algorithm.

To show that some other form of computation can do anything the Turing Machine can do, you just have to toss together a tiny Universal Turing Machine implementation on it. And you have proven your computation form to be Turing-Complete.

For the most part, we just assume your computational model is Turing-computable if we have even a physical approximation of it; but doing the other way (demonstrating that a Turing machine, or something that is run by a Turing machine, can run your computational model) is also important.

Once we have done this, we have reached the Turing Tar-Pit; we have proven that the two computational models are equivalent (they can compute the same things). This does not mean that they are just as efficient as each other; efficiency can vary widely.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

webb.am
Posts: 41
Joined: Wed Feb 24, 2010 1:09 pm UTC

Re: Turing machines

Postby webb.am » Wed Feb 24, 2010 8:09 pm UTC

As others have said, Turing machines aren't supposed to be practical computers. But they have very simple rules and anything that is computable is Turing computable.

The really significant thing about Turing machines is that they brought about the concept of Universal Turing Machines. Until a certain point people thought of programs as being hardware. With a UTM, the program is a representation of a Turing Machine, which the UTM then simulates. Thinking of programs as data seems obvious to us, but it was a big step. It led to the stored-program computer.

What's really fascinating is just how many different universal computation models there are (that is, models that are Turing-complete). Some people have mentioned lambda calculus. Modern programming languages (combined with a computer to run them on) are essentially Turing-complete (though they don't have infinite memory...).

A truly interesting computational model I've come across recently is the idea of tile-sets as Turing machines. It's possible (and actually relatively easy) to convert the description of a Turing machine into a set of 2D polygonal tiles in such a way that it's only possible to tile the infinite plane with those tiles if the Turing machine never stops. If the Turing machine has an accepting state then the tiling reaches a point where no more tiles can be placed and the configuration represents the output.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests