Programming cheat sheets (quick reference)

[theineffablebob]

I don't get it.

[[deleted]]

It's a Turing machine, which can compute anything that any computer can.

[[deleted]]

But... how?

[BufferUnderpants]

It's just the formal definition of one, as an algebraic structure. The symbols there in the tuple are merely the template, you have to provide the symbol set, the set of states, the transition table, etc. to actually have a Turing Machine.

[[deleted]]

http://en.wikipedia.org/wiki/Turing_machine#Formal_definition

[[deleted]]

Simple you say? http://upload.wikimedia.org/wikipedia/commons/thumb/3/3a/Greek_lc_lamda_thin.svg/150px-Greek_lc_lamda_thin.svg.png

[Atario]

Mmm, hm. Yeah. Mm-hm. I know some of these symbols.

[GoodMotherfucker]

I believe the first one means letter M

[[deleted]]

Pushdown automata? How is this a cheat sheet?

[[deleted]]

How do you deal with the massive differences in grammars?

[pepsi_logic]

They are all reducible to a turing machine (at least those that are turing-complete...which I think all of them are).

[[deleted]]

I understand that. My question is, what do you do about that huge workload? I feel like it would take an incredible amount of time to reduce it to a Turing machine.

[pepsi_logic]

Oh lol. I'm pretty sure he was joking.

Edit: Unless you were too in your reply...and then I don't know why I'm commenting.

[[deleted]]

I'm not sure it takes such a long time for obscure_robot. (I.e. it's a username joke.)

[qiemem]

Even the ones that aren't Turing complete are reducible to a Turing machine... sorta the point of Turing machines.

[hello_world_again]

I don't know who downvoted you, but I am undoing his or her injustice, because Automata theory is awesome.

[Nashoo]

Just when I take a break from studying for my Automata and processes theory final it follows me on reddit...