![Model_of_a_Turing_machine[1].jpg](https://i.imgur.com/rfT1FuP.jpg "Model_of_a_Turing_machine[1].jpg")
How much math do I need to understand Turing machines?
Necessary bump
>>8193491
Depends what you mean by understand.
You can look up the definition and basic properties with no prerequisites at all.
>>8193491
next to none
But you need math to be a good programmer
>>8193491
Naive set theory. Math doesn't get much easier than that.
Typically you study classes of machines <=> abstract languages of greater and greater complexity before you study Turing machines, such as finite-state automata <=> regular expressions, push-down automata <=> context-free grammar, etc. so you can appreciate better what a Turing machine "is" and can "do".
The concept of a Turing machine is not difficult to grasp, but I would recommend going through the motions for studying the other classes of machines first.
Hopcroft-Ullman is a good book for it.
Warning! Although the definitions aren't hard to grasp, this is pure Computer Science, and is very mathematical.
>>8193491
Basic arithmetic would help, I guess. If you can do long division, that's a pretty good example of a recursive algorithm based on symbol manipulation.
The kind of math needed to understand Turing machines is largely orthogonal to the math you learn in school; it's more a matter of abstract logic and reasoning than anything to do with numbers.
>>8193491
You need to become gay
Turing machines are much worse pedagogically than other equivalent models of computation.
>>8193491
a good grasp of math thats needed in compsci. Think binary arithemtic, logic (NOT,AND, OR) and how variables work then think about comparisons between those and instructions to point to reference labels. Then you have everything to make NAND gates and program it. You will be able to make a simple 4 bit turing complete system within a few days as a hobby project. It's not much but you'll understand the underlying concepts.
To understand how to use a non-universal Turing machine (basically a particular kind of function between two small finite sets that can be represented as a drawing like pic related) you need only be capable of understanding board games.
Running it means moving a cursor over the board.
The curser starts at q1.
Where you go is determined by the input string.
The strings may contain the symbols ▹,0, 1,◻ and optionally more.
Pic related is a represents a Turing machine/function/program that tells you if a string at hand (it may be five or one million symbols long) has the length 2^n for some n.
You’ll get it by an example:
* Is „0“ of length of power of two?
▹ 0(q1) ◻
Overwrite as ◻ and go right.
▹ ◻ ◻(q2)
Go right.
ACCEPTED!
* Is „00“ a power of two?
▹ 0(q1) 0 ◻
Overwrite as ◻ and go right.
▹ ◻ 0(q2) ◻
Overwrite as x and go right.
▹ ◻ x ◻(q3)
Go left.
▹ ◻ x(q5) ◻
Go left.
▹ ◻(q5) x ◻
Go right
▹ ◻ x(q5) ◻
Go right.
▹ ◻ x ◻(q5)
ACCEPTED!
* Is „000“ a power of two?
▹ 0(q1) 0 0 ◻
Overwrite as ◻ and go right.
▹ ◻ 0(q2) 0 ◻
Overwrite as x and go right.
▹ ◻ x 0(q3) ◻
Go right.
▹ ◻ x 0 ◻(q4)
REJECTED!
* Is „0000“ a power of two?
▹ 0(q1) 0 0 0 ◻
Overwrite as ◻ and go right.
▹ ◻ 0(q2) 0 0 ◻
Overwrite as x and go right.
▹ ◻ x 0(q3) 0 ◻
Go right.
▹ ◻ x 0 0(q4) ◻
Overwrite as x and go right.
▹ ◻ x 0 x ◻(q3)
Go left.
▹ ◻ x 0 x(q5) ◻
Go left.
▹ ◻ x 0(q5) x ◻
Go left.
▹ ◻ x(q5) 0 x ◻
Go left.
▹ ◻(q5) x 0 x ◻
Go right.
▹ ◻ x(q2) 0 x ◻
Go right.
▹ ◻ x 0(q2) x ◻
Overwrite as x and go right.
▹ ◻ x x x(q3) ◻
Go right
▹ ◻ x x x ◻(q3)
…from here you run one to the left ◻ and back to the left and then…
ACCEPTED
>>8193592
(here "x" used instead of "1", obviously, it's from Sipsers book)
