Exercise idea: Turing Machines

[Average-user]

The idea is that when implementing a Turing machine you are also proving the turing completeness of the language in use. It may also help people understand a little about how mathematical models of computations are conceived.

[ErikSchierboom]

I like the idea! Turing machines are a fundamental CS topic, so to have them represented in some way on Exercism would be nice.

[Average-user]

Should we discuss the specific definition of a Turing machine? My personal recommendation would be to define it as a four elements tuple like (Initial State, Halt State, Rules, blank symbol). To keep it simple I think we should admit just a single Initial and Halt state and the allowed set of symbols should be the allowed characters by the language I think. About the blank symbol being variable I'm not sure, but I'd leave it like that.

And rules should be a set of tuples like: (ActivationState, ActivationSymbol, NewSymbol, Direction, NewState). Where Direction should have right, left and stay as options.

For a example a rule like: (A,1,0,right,B), should be read as: If you are instate A and see a 1 replace it for a 0 move right, and change to state B

[omer-g]

I think this is a great idea for an exercise!

Perhaps it would be useful to include an alphabet in the tuple that defines the machine? The idea that the machine runs on any set of symbols supplied to it is interesting and seeing a specific alphabet in the tests may help users better understand the problem. I think it is somewhat easier to implement a Turing machine with a binary alphabet in mind (as is often done in textbooks). A well implemented machine would then work for larger alphabets as well.

As a bonus, I think it would be easier to make and maintain simple and clear tests with a binary alphabet, and perhaps add just a few more tests with larger alphabets.

I would be happy to hear what you think.

EDIT: This would also allow defining the blank as a character and make it clearer that blank is a symbol in the (tape) alphabet.

(a slightly more complex version could include two sets of alphabets for input and tape)

[Average-user]

@omer-g

Perhaps it would be useful to include an alphabet in the tuple that defines the machine?

Mhh, I think your right, now that I think about it more, is probably better to specify the alphabet.

I think that the next step is to think of what machines to implement in the test cases. There are some classics like busy beaver. Meanwhile I'll make a demo of description.md

[Average-user]

Turing Machines

Turing machines are the most know mathematical model of computation. It was first purposed by Alan Turing in 1937. It is thought that every computation that can be performed, can be performed with a Turing machine.

A Turing machines models a mechanical process that operates on a tape. This tape is composed by a sequence of symbols, the machine is able to read and write symbols one at a time. This replacement is fully determinated by a finite set of functions, or rules. The machine, also keeps record of the current state which is likely to change during a computation.

Formal definition

There are many definitions for a Turing Machine, but here we will define it as a five element tuple M = (A,b,I,F,R) where

• A Is a non empty finite state of symbols called the alphabet,
• b Is a symbol member of A that fills the entire tape, as the blank symbols.
• I Is the initial state.
• F Is the halting state, the state that if its reached, the computation stops.
• R Is a finite sequence of rules that determinate what does the machine do when its looking at a symbol. If at some point no rule can be applied the machine will halt. It is a sequence because the order matters since we are implementing a deterministic version, just the first rule that matches is used.

Lets give an example of a famous Turing Machine called Busy Beaver.

A = {0,1}
b = 0
I = A
F = HALT
R = [ (A, 0, 1, R, B)
    , (A, 1, 1, L, C)
    , (B, 0, 1, L, A)
    , (B, 1, 1, R, B)
    , (C, 0, 1, L, B)
    , (C, 1, 1, R, HALT)
    ]

The rule (A, 0, 1, R, B) should be read as: If the current state is A and the machine is looking a 0, then replace it by 1, move one symbol to the right and change to state B. -------------------------------------------------------------------- Here is a first attempt, but as you may notice English is not my native language, so if you want, you are more than welcome to make improvements.

[SleeplessByte]

I like the idea of the exercise, but I'd remove the left and right concept at least for the initial exercise. The way it's written right now, if a student has not had state machines (theory of computation) in real life, I doubt it will be clear.

Most regular expressions without recursion or capture groups that are matched later can be turned into valid state machines. That might be a better way to connect the theory with exercise.

I.e.

/^ab(c)+(a|b)$/

initial state A ^
A -> a -> B
B -> b -> C
C -> c -> D
D -> d -> D
D -> a -> HALT
D -> b -> HALT

I don't know how to turn this into an exercise. The left right concept is great but doesn't help us much when applying it to real life implementations oft turning machines, right?

P.S. there are not many definitions of a Turing machine and I would not put that in the formal definition, again see theory of computation