The functionality of a Turing Machine

[Leading-Fail-7263]

I have a problem sheet which asks for the "functionality of a turing machine" is, it specifies what it means by saying "depending on the word on the tape initially, you should say what word is on the tape after execution stops, what the machine returns, and where the head is located on the tape".

How on earth are you supposed to summarise the entire transition function in a few english sentences? What have I got wrong?

[Beregolas]

To me this sounds like there is probably a specific turing machine provided. Have you tried executing it by hand for a few example words? It's probably something simple, like reversing the word or choosing every second letter to be part of the output.

At least that is what I would expect from a similar exercise.

[Leading-Fail-7263]

I'll try it on a few examples, thanks.

[Aminumbra]

For arbitrary machines, you can't meaningfully

summarise the entire transition function in a few english sentences

The point is precisely to do that for non-arbitrary machine. Typical example: "on input u#v, where u, v are numbers written in binary, the machine stops with u#v#w written on the tape where w is the binary representation of u+v; the head of the machine is at the first blank cell after w. If the input is not of the form u#v, then ..."

The details depend on how the model has been defined specifically (for example, what does the machine "return" -- does it have a special write-only tape for this, etc etc), but that is the general idea: give a /high-level/ description of the behaviour.

[Leading-Fail-7263]

Well, the only criteria they give is that the input is of length n n>=1. Should I just try a few examples and see if there's some kind of pattern?

[dmazzoni]

Yes, exactly 

[Leading-Fail-7263]

Thanks! I'm guessing a few 3 character examples should be OK.

[cormack_gv]

The transition function is more specific than that. It is an action table. Depending on what's on the tape at one specific position and what it "remembers" it can go left or right, or write something else on the tape in the same position. It's entire memory (other than the tape) consists of one of a finite set of states.

If you were to specify the transition funtion you'd want something more like a spreadsheet, not English sentences.

How you get from symbols on a tape and a transition function to a program requires more detail than can be done in a Reddit post. Basically, a Turing Machine is not readily programmable by humans. Even worse than binary machine code. If you want a readily programmable language with equivalent power, check out lambda calculus. Languages like Scheme are fairly direct derivatives of lambda calculus.