WOLFRAM NOTEBOOK

WOLFRAM|DEMONSTRATIONS PROJECT

Collatz Sequence Computed by a Turing Machine

initial condition

steps

show machine head

compressed evolution

The Collatz sequence is formed by an iteration of numbers produced by the following rule: If

is even, then replace

n/2

; if

is odd then replace

3n+1

. This Demonstration implements an 8-state 3-color Turing machine that computes this sequence.

The machine works like this: Write an initial number

in base 2 on the blank tape. The head of the machine is initially located over the least significant byte of the number.

is even, the head erases the digit 0 and moves to the left, so that it lies over the less significant byte of

n/2

is odd, the machine performs the sum

n+2n+1

by adding the number with itself shifted one position to the left plus one. To do this, the head writes 0, saves the digit 0 and the residue 1 and then moves to the left. Now, the head repeatedly adds the current digit plus the saved digit plus the residue saved in the head and saves the residue of the operation and the current digit in the head, then moves to the left. When the addition is done, the head returns to the position of the least significant byte of

3n+1

The computation does not stop at

n=1

. It keeps computing the periodic sequence 1, 2, 4, 1, …, which can be interpreted as stopping.

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.

I understand and wish to continue anyway »