Here is the expansion process for 3→3→N→2:

3→3→1→2 = 27 = c3(1)

3→3→2→2 = 3→3→(3→3→1→2) = 3→3→c3(1) = hy(3,c3(1),3) = c3(2)

3→3→3→2 = 3→3→(3→3→2→2) = 3→3→c3(2) = hy(3,c3(2),3) = c3(3)

and in general,

3→3→N→2 = c3(N)

Now note that:

c3(1) << gn(1) << c3(2)

c3(2) = hy(3, c3(1), 3) << hy(3, gn(1)+2, 3) = gn(2) << c3(2)

and in general

c3(N) = hy(3, c3(N-1), 3) << hy(3, gn(N-1)+2, 3) = gn(N) << c3(N+1)

therefore,

c3(64) = 3→3→64→2 << gn(64) = Graham's number << 3→3→65→2 = c3(65)

A reader asked me how 3→3→3→3 compares to these:

3→3→3→3
= 3→3→(3→3→2→3)→2
= 3→3→(3→3→(3→3→1→3)→2)→2
= 3→3→(3→3→27→2)→2
= 3→3→c3(27)→2
= c3(c3(27))

therefore 3→3→3→3 is much bigger than Graham's Number.

What Turing and Church Did Not Prove

Turing is often credited with having proven that there are limits to what can be computed by computers, including all conceivable designs of real-world computers. This actually depends a lot on what you mean by computer. Here are some types of computers that a Turing machine cannot emulate:

• Ideal analog computers. This is a computer that manipulates real numbers in the form of analog quantities (like voltages) rather than digits. In an "ideal" analog computer, the quantity being represented is represented exactly, without any error. An example is a circuit that calculates square roots: If you put 2.0 volts on the input wire, it produces 1.4142135... volts on the output.

• Actual analog computers: Any real-world analog computer is subject to various sources of error, including fundamental limits of physics such as the brownian motion of molecules, the quantization of electric charge, and the uncertainty principle (Planck limits).

• Quantum computers: A quantum computer (ideal or actual) exploits properties of quantum mechanics, including most especially the ability for a "particle" such as a photon to be in a state that is indeterminate until that particle interacts with another particle. The conditions of the interaction and the original conditions of the indeterminate state's creation then determine what is observed. It appears that such interactions can be used to perform a soft of massively parallel computation.

• Non-deterministic computers: A nondeterministic computer incorporates some type of phenomenon that is not predictable, in the sense that no amount of advance knowledge can completely predict what the result of a computation will be. Sometimes such phenomena are deliberately exploited, such as a random number generator device based on a Geiger counter (and deriving its randomness from the unpredictable timing of radioactive decay events)

Each of these has one or more properties that make Turing's argument inapplicable. Usually this is some form of unpredictability on a fundamental level. For the ideal analog computers, Turing's argument does not apply because of the cardinality of the reals It is known that Turing planned to create a limits-to-computability proof for such computers, but that he never did (I suspect it was not because such computers are actually without limit!)

Notes on Busy Beaver Function

In 1964 Milton Green developed a lower bound for the Busy Beaver function that was published in the proceedings of the 1964 IEEE symposium on switching circuit theory and logical design. Heiner Marxen and Juergen Buntrock described it as "a non-trivial (not primitive recursive) lower bound". This lower bound can be calculated but is too complex to state as a single expression in terms of n. When n=8 the method gives

BB(8) >= 3 × (7 × 3⁹² - 1) / 2 ≅ 8.248×10⁴⁴

Ray Kurzweil, in his 1999 book The Age of Spiritual Machines, discusses the Busy Beaver function in a footnote. I believe he was quoting the results of Green or Marxen and Buntrock, because his description is suggestive of the Ackermann function and because of the near-agreement of the values for BB(8). Kurzweil states that a 6-state Turing machine "can add" and BB(6) is 35; that a 7-state machine can multiply and BB(7) is 22961, and that an 8-state machine can exponentiate and BB(8) is "about 10⁴³". Then he goes on to say that BB(10) requires a notation in which the height of a stack of exponents is given by another stack of exponents whose height is given by... and so on; this might be equivalent to the generalized hyper operator. Presumably BB(9) is something in between like hyper4 or hyper5. He says that BB(12) requires an "even more exotic notation", and that the limits of human intelligence are reached well before BB(100).

It has since been shown that at least one possible BB(6) candidate performs iterated exponentiation, the equivalent of hyper4.

The direct approach to finding actual values of the busy beaver function is to simulate Turing machines with a computer program, trying each possible set of rules to see what it does. The first impediment to this is that the number of machines to test grows so quickly. Lin and Rado give the forumla (2N-1)4N^2N-2, which incorporates some of the rules listed below:

N (2N-1) 4N^2N-2
1: 1
2: 192
3: 103680
4: 117440512
5: 230400000000
6: 697437190619136
7: 3018837446159761408
8: 17708874310761169551360
etc.

To actually implement a complete test of all Turing machines of a given state, you have to deal with many different types of cases. Many are easy to deal with and many are very difficult.

(If your browser supports Java you can run any of the Turing machines given here on this simulator. If you have Linux, you can use my own simulator written in perl

Since the tape is symmetrical, left and right can be interchanged. These two programs differ only in the directions of the arrows, so one can be ignored:

1,_:   2,1,>     1,1:   2,1,<
2,_:   1,1,<     2,1:   H,1,>

1,_:   2,1,<     1,1:   2,1,>
2,_:   1,1,>     2,1:   H,1,<

the latter program is skipped by setting as a rule that the "1,_" state always moves to the right.

If the "1,_" state writes a "_" and moves to state N, the machine will find itself in state N with a completely empty tape. Such a machine is identical to a machine in which states 1 and N are switched, except that it takes one extra step. Thus, for the purpose of the Busy Beaver problem, the first machine can be ignored. This is accomplished by setting a rule that the "1,_" state should always write a 1.

If the "1,_" state moves to state N, and if N is greater than 2, states N and 2 can be swapped and the resulting machine is equivalent, and as a result one of these two machines can be ignored. This is accomplished by setting a rule that the "1,_" state always proceeds to state 1 or 2.

If the "1,_" state goes to state 1, then the machine will stay in state 1 forever and write 1's forever, and therefore will never halt. Thus, such machines can be skipped. Combined with the previous rules, this completely defines the actions for the "1,_" state: It should be "1,_: 2,1,>".

The aforegoing rules establish that the "2,_" action will be the second to execute. Therefore it should not halt: if it did the machine would never use the "1,1" action, which could be used by having the "2,_" action perform "1,1,<".

Furthermore, if the "2,_" action goes to state 1 or state 2, it should not move to the right because if it did it would create an infinite-loop machine (such a machine would continually move right, either staying in state 2 or alternating between states 1 and 2.).

No state should have both of its actions go to itself (i.e. not change state) because that would result in an infinite loop as soon as that state is entered. An example of this is if the "3,_" action and the "3,1" action both went to state 3.

Except for state 1 (which is by definition the starting state) and state 2 (which, if using the aforegoing rules, is the state entered from the "1,_" state), all the other states can be renumbered in arbitrary order, and the resulting machines all have the same behavior. This is important for machines with 4 or more states and allows lots of programs to be eliminated quickly.

If the program doesn't have any states that contain a HALT action, we know it will never halt and it can be skipped.

Programs containing two or more HALT actions can be skipped because only one of the HALTs will ever be used (whichever one it gets to first) and the other HALTs would be superfluous.

If the HALT writes a 0, the same machine with a HALT that writes a 1 will be at least as good or better; thus the 0-writing version can be ignored.

A machine that moves left when HALTing is the same as a machine that moves right when HALTing, thus only one of these two possibilities needs to be looked at. This is accomplished by setting a rule that the HALT always moves to the right.

Some programs contain unused states. For example:

1,_:   1,1,>     1,1:   1,1,<
2,_:   2,1,>     2,1:   H,1,>

State 1 always goes to state 1, so state 2 is never reached. Programs like this can be skipped because there is always a way to modify the program so that it uses the extra state and produces at least as much output.

A similar example is:

1,_:   2,1,>     1,1:   2,1,<
2,_:   1,1,<     2,1:   1,1,<
3,_:   4,1,>     3,1:   4,1,<
4,_:   H,1,>     4,1:   3,1,<

There is no way to get past states 1 and 2. Such machines are eliminated by looking for loops in the state graph.

Some programs halt very quickly, for example:

1,_:   2,1,>     1,1:   2,1,<
2,_:   3,1,>     2,1:   3,1,<
3,_:   4,1,>     3,1:   4,1,<
4,_:   H,1,>     4,1:   H,1,>

This program halts quickly because each state goes to a higher-numbered state, and the highest state (state 4) always halts. Based on that alone you know it will run for only 4 steps. (However, it doesn't hurt much to run such machines because they don't take long to run)

Based on all these examples, it seems as though it ought to be easy to search for the busy beaver using brute force. The trouble is in the programs that have to be run to determine what happens. Some exhibit very complex behavior. Only the simplest behaviors can be detected automatically.

If a program is simulated, and the simulation shows that the program halts before it has used all of its rules, then the unused rules are irrelevant and we know right away that all other programs that differ only in these unused rules will have the same behavior. This allows those other programs to be skipped.

Any programs that don't halt real quickly have to be analyzed in some way, usually by human inspection.

The simplest behaviors are like this trivial example:

1,_:   2,1,>     1,1:   2,1,<
2,_:   1,1,>     2,1:   H,1,>

which will keep writing 1's and moving to the right.

Many programs have similar behavior, writing some continuous pattern and moving steadily and repeatedly either to the left or to the right. Here's a slightly less trivial example — it moves forever to the left in a two steps forward, one step back manner, leaving a trail of alternating 1's and 0's:

1,_:   2,1,>     1,1:   3,1,<
2,_:   3,1,<     2,1:   H,1,>
3,_:   1,_,<     3,1:   3,_,<

Automatically identifying such programs can be difficult, because sometimes the pattern it generates is complex and it takes a large number of steps to repeat each cycle.

Some programs write a fixed number of 1's but never halt, for example:

1,_:   2,1,>     1,1:   H,1,>
2,_:   2,_,>     2,1:   1,1,>

which writes a single 1 and then goes off forever to the right.

Some programs grow forever but don't move steadily in one direction or the other. For example:

1,_:   2,1,>     1,1:   1,1,<
2,_:   3,1,>     2,1:   2,1,>
3,_:   1,_,<     3,1:   H,1,>

It produces an ever-expanding row of 1's in both directions, by moving back and forth. Each time it gets to an end it writes a new 1 and then reverses direction. State 3 is never reached while on a 1, so it never halts. Many programs behave in a similar manner but produce more complicated patterns or move in more complicated ways.

Some programs grow forever without any repeating pattern. The simplest example is this machine:

1,_:   2,1,>     1,1:   1,1,<
2,_:   1,_,<     2,1:   2,_,>
3,_:   1,_,<     3,1:   H,1,>

which is a binary counter. It keeps moving back and forth producing each binary number in sequence. The string of 1's and 0's is always changing, has a pattern that never repeats and grows forever (although, of course, the growth is very slow).

The next example is a little more complicated. It writes a string of 1's to the right, and simultaneously updates a binary number on the left; the binary number tells how many 1's have been written to the right:

1,_:   2,1,>     1,1:   1,1,<
2,_:   3,_,>     2,1:   2,_,>
3,_:   4,1,>     3,1:   3,1,>
4,_:   5,_,<     4,1:   H,1,>
5,_:   1,_,<     5,1:   5,1,<

Here is another machine (given by Marxen and Buntrock) that works like a binary counter, but produces a more complex pattern. Whenever all the 1's are to the left of the head (which occurs often) the binary value is recognizable. The digits are coded in groups of 3 cells: what would be a "1" digit appears as "111" and what would be a "0" appears as "_11":

1,_:   2,1,>     1,1:   1,1,<
2,_:   1,_,<     2,1:   3,_,>
3,_:   3,_,<     3,1:   4,1,>
4,_:   5,1,>     4,1:   1,_,<
5,_:   2,_,>     5,1:   H,1,>

Many other programs move around erratically, writing seemingly random patterns of 1's and 0's and transitioning between states in a seemingly random order, not moving steadily in any direction. Here's an example, the 5-state machine found by Schult in 1983:

1,_:   2,1,>     1,1:   3,_,<
2,_:   3,1,>     2,1:   4,1,>
3,_:   1,1,<     3,1:   2,_,>
4,_:   5,_,>     4,1:   H,1,>
5,_:   3,1,<     5,1:   1,1,>

This machine was a record-holder for a while in the 5-state "contest". In order to halt it has to be in state 4 with a 1 on the tape. The only way to be in state 4 is coming from state 2 with a 1 on the tape. The only way to be in state 2 is coming from state 1 with a 0 on the tape, or state 3 with a 1 on the tape. All other states lead to states 1 and 3, which is where it spends most of its time. When you run it, it appears to fill the tape with ever longer patterns of "111_111_111_...", then backtrack over those patterns and convert them into "1_1_1_1_1_...", but every time it completes a cycle there is a little difference, like an extra 1 at the left or right end. It runs for 134,467 steps before finally producing just the right pattern of 1's and 0's to lead itself into its HALT state.

There are many programs like this that run for a long time and eventually halt, and many others that have been simulated for a long time without following any type of pattern that anyone has been able to figure out. Such machines resemble this one:

1,_:   2,1,>     1,1:   2,1,<
2,_:   3,1,<     2,1:   5,_,>
3,_:   4,_,<     3,1:   1,_,>
4,_:   1,1,>     4,1:   4,_,<
5,_:   H,1,>     5,1:   3,_,>

Its behavior was sufficiently complex as to elude Marxen and Buntrock, but not their program. Designed to analyze Turing machines and prove that they do or do not halt, the program did manage to create a proof that this machine does not halt. The trouble is, the proof is so complex that it is difficult to check by hand.

Some programs run so long before halting that direct "one-step-at-a-time" simulation isn't fast enough to show how long they run. Many machines can be run to completion with first-order acceleration techniques (skipping through any repeated sequence of states and/or tape cells). However, many others require a combination of different types of acceleration. The current record-holder for 6-state machines, which takes 8,690,333,381,690,951 (over 8×10¹⁵) steps to halt, is a good example. And, when all types of automated acceleration fall short, "maunal" (human) analysis can sometimes be used to prove that a machine halts and calculate the relevant numbers. (An example of this follows the table).

Busy Beavers and BB Candidate Record-Setters

You can run any of these on my turing machine simulator but be warned — the simulator is a command-line-oriented Perl program, certainly not for the faint of heart.

Analysis of the 1997 Marxen-Buntrock BB₆ Record-Setter

This section describes the machine that set the record BB₆ >= 95,524,079. It is a 6-state candidate discovered by Marxen and Buntrock in 1997. (The Oct 2000 record-holder is discussed in the next section)

The machine's operation lends itself easily to analysis, which reveals a beautiful combination of a few simple processes that interact in just the right way. The machine implements an iterated function that grows at an exponential rate and uses a test condition based on a low-probability, deterministic, and statistically random condition to determine when to stop growing. As a result, it grows to a very large size, so large that it takes a really sophisticated Turing machine simulator to show that it halts by brute-force iteration.

Simulation of the first few steps shows that it creates a row of 1's and repeatedly expands it to a row of 1's about 2.5 times longer. The exit condition depends on the number of 1's modulo 4 (the remainder of the number when divided by 4). But the number of 1's increases in a way that also depends in its value modulo 4, with the result that the value modulo 4 changes in a "chaotic" manner. This means that the row of 1's can multiply many times before the machine halts. Furthermore, the process of performing the mod-4 test is combined with the process of performing the division by 2 (which is then followed by a multiplication by 5). This combination of functions — accomplishing two things simultaneously with the same code — is part of what makes this much complexity possible in a Turing machine with only 6 states.

To analyze, we started by finding an example of a simple state that the machine enters over and over again. I call such a state "canonical" because it it has a simple pattern and recurs multiple times during the machine's history. As already implied, the canonical state in this case is a single continuous set of N 1's. In addition we specify that the machine is in state 1 and the head is positioned over any of the 1's. It doesn't matter which of the 1's the head is on, because in all such states the machine just moves to the right, staying in state 1 until it gets to the end of the row of 1's.

This condition occurs at steps 4, 37, 259, and several more times as listed below. After it reaches the right-hand end of the row of 1's, it adds two more 1's to the right and reverses direction, then plows through the rest of the 1's changing them into a "1_1_" pattern (this is easy to see in the machine's state table: it cycles through states 3,4,5,6, each time moving to the left and writing alternating 1 and _). When the head reaches the left end, what happens next depends on the value of N modulo 4. Here is what the tape will end up looking like for each of the 4 possibilities:

N = 0 mod 4 (4, 8, 12, etc.): 1(10)^M11
N = 1 mod 4 (5, 9, 13, etc.): Halts with 1(10)^M11 on the tape
N = 2 mod 4 (6, 10, 14, etc.): 111(10)^M11
N = 3 mod 4 (7, 11, 15, etc.): 111(10)^M11

(Where M is equal to N/2, rounded down.) As you can see, only values of N that are 1 more than a multiple of 4 will result in a halt.

In the remaining cases the machine begins a process that takes about 5 N² / 4 steps, during which it repeatedly shuttles back and forth turning each copy of '1_' into '11' and then appending a '111' to the left, thereby adding a total of 3M 1's to the left. When this is done the tape is once again a single solid row of 1's, with the machine in state 1. The new value of N for this new, longer string of 1's is different for each of the three cases:

N = 0 mod 4: 3 M + 1 + 2 M + 2 = 5 N / 2 + 3 = (1 or 3) mod 4
N = 1 mod 4: (machine will have halted)
N = 2 mod 4: 3 M + 3 + 2 M + 2 = 5 N / 2 + 5 = (0 or 2) mod 4
N = 3 mod 4: 3 M + 3 + 2 M + 2 = 5 (N-1) / 2 + 5 = (0 or 2) mod 4

Notice that the formula for the new N involves a division by 2, and adds either 3 or 5. Because of the division by 2, the new N's mod-4 value depends on the old N's value modulo 8:

N = 0 mod 8: new N = 3 mod 4
N = 1 mod 8: (machine will have halted)
N = 2 mod 8: new N = 2 mod 4
N = 3 mod 8: new N = 2 mod 4
N = 4 mod 8: new N = 1 mod 4
N = 5 mod 8: (machine will have halted)
N = 6 mod 8: new N = 0 mod 4
N = 7 mod 8: new N = 0 mod 4

As you can see, out of the 6 possible cases, only one of them leads to an N=1 mod 4 value (the 'halting' value) for the new N. This is an example of a generalized Collatz mapping¹. (The parameters are: T(x) = floor(m_i^.x / d) + X_i, where d=4, i such that x = i mod d, m_i = {10,0,10,10}, X_i = {3,1,5,3}, and initial value x=3).

A "Collatz mapping" is an iterated function on integers, where at each iteration you perform a modulo test (like the remainder after dividing by 2) and then select from one of a number of linear functions (such as X/2 or 3X+1) based on what the remainder was. The simplest and best-known Collatz mapping is the "3N+1 problem", which states that for any X, the next value of X in the iteration is:

Such iterations are notable for the fact that the behavior of the iteration is very difficult to characterize. Does any value for X cause the iteration to grow forever, or do they all always end up in the cycle 4, 2, 1, 4, 2, 1, ...? Some values of X grow pretty high.

Our Turing machine differs from the standard Collatz mapping in having a "halt" condition as one possible outcome. It also differs from the 3N+1 problem in that all of the linear functions grow, thus there is no question of it ever getting smaller — only how long will it grow before it stops?

Here are all the N values, and for the first 12 cases the step number (found by simulation) at which a row of N 1's is first seen. (The precise number of steps for each N can be calculated using a little more analysis, but it's not important for answering the halting question). Also given are the mod-4 value and the value of M. Notice in particular the fairly erratic pattern of mod-4 values.

It might seem a little disappointing to some readers to note that this machine, a record-setter for the number of 1's produced, actually produces as many as twice that record, only to cut the number almost in half just before halting.

Analysis of the Oct 2000 Marxen-Buntrock BB₆ Record-Setter 'q'

This is a high-level description of an old BB(6) candidate champion, discovered in October 2000 and later surpassed on March 2001. It writes over 6×10⁴⁶² ones before halting. For a more thorough and rigorous analysis read this page.

This machine operates on similar principles to the one just discussed, but instead of iterating a process of multiplying the number of 1's by 5/2, it iterates a process of raising 2 to the power of the number of 1's! Yes, that's right, iterated exponents. Combined with the modulo dependency mechanism (this time on a modulo-3 test rather than modulo-4) it's easy to see how it gets up to 10⁴⁶² ones.

To analyze, we use the same method as before of finding a simple "canonical" state (like a run of 1's) and looking at what it produces when the number of 1's changes. In this case, the simplest such state is when the head is in state 2, positioned on a 0 cell, with N consecutive 1's just to the left of the head, and nothing else. Call such a state C(N).

Looking at the fates of the first few C(N)'s, we find:

C(0) becomes C(10) after 86 steps.
C(1) becomes C(24) after 408 steps.
C(2) halts after 8 steps, leaving 4 1's on the tape.
C(3) becomes C(28) after 544 steps.
C(4) becomes C(56) after 2098 steps.
C(5) halts after 11 steps, leaving 6 1's on the tape.
C(6) becomes C(64) after 2730 steps.
C(7) becomes C(120) after 9548 steps.
C(8) halts after 14 steps, leaving 8 1's on the tape.
C(9) becomes C(136) after 12260 steps.
C(10) becomes C(248) after 40806 steps.
C(11) halts after 17 steps, leaving 10 1's on the tape.
C(12) becomes C(280) after 52030 steps.
C(13) becomes C(504) after 168832 steps.
C(14) halts after 20 steps, leaving 12 1's on the tape.
C(15) becomes C(568) after 214488 steps.

It is clear right away that there is a modulo-3 effect going on. A general formula is only evident for the case of N=2 modulo 3:

C(3N+2) halts after 3N+8 steps, leaving (2(N+1)/3)+2 1's on the tape.

For the others, we have to consider another "canonical" state; this one is a bit more complex. It consists of bunch of groups of 1's separated by single 0's, with the head in state 2 and positioned just to the left of the leftmost 1. I will represent such a state as D(a,b,c,...) where the a, b, c etc. are numbers giving the number of 1's in each group. Each of the C(N)'s above (except the ones that halt) leads to one of these D(...) states, which then passes through one or more additional D(...) states and ultimately becomes another C() state. Here is the first D(...) state for each C() state:

C(0) becomes 111_1 which we call D(3,1)
C(1) becomes 111_1_1 which we call D(3,1,1)

C(3) becomes 1111_1_1 which we call D(4,1,1)
C(4) becomes 111_11_1_1 which we call D(3,2,1,1)

C(6) becomes D(4,2,1,1)
C(7) becomes D(3,2,2,1,1)

C(9) becomes D(4,2,2,1,1)
C(10) becomes D(3,2,2,2,1,1)

C(12) becomes D(4,2,2,2,1,1)
C(13) becomes D(3,2,2,2,2,1,1)

C(15) becomes D(4,2,2,2,2,1,1)

and in general:

C(3N) becomes D(4,X,1,1) where X is a string of N-1 2's in a row
C(3N+1) becomes D(3,X,1,1) where X is a string of N 2's in a row

Then we can look at each of the D's and see what happens:

D(3,1) becomes C(10)

D(3,1,1) becomes D(10,1)
D(10,1) becomes C(24)

D(4,1,1) becomes D(12,1)
D(12,1) becomes C(28)

D(3,2,1,1) becomes D(11,1,1)
D(11,1,1) becomes D(26,1)
D(26,1) becomes C(56)

D(4,2,1,1) becomes D(13,1,1)
D(13,1,1) becomes D(28,1)
D(28,1) becomes C(60)

The pattern that emerges is:

D(N,1) becomes C(2N+4)

D(N,1,1) becomes D(2N+4,1)

D(N,2,1,1) becomes D(2N+5,1,1)

and in general:

D(N,2,X) becomes D(2N+5,X)

where X is any sequence of groups.

So, to figure out how far this machine goes before halting, we have to find the first occurance of a C(N) state, then apply these rules to find each subsequent C(N) state until we get to one with N=2 modulo 3. Since the transition from each C(N) to the next higher C(N) involves approximately N/3 steps iterating 2N+4 or 2N+5 each step, it amounts to calculating (approximately) 2^N/3 each time. If you count each C(N) as a "step", the machine only takes three "steps" to produce the huge number 6×10⁴⁶².

C(1) occurs at step 1 of the machine's operation.

C(1) becomes D(3,1,1) which becomes C(24) at step 409.

C(24) = C(8×3), becomes D(4,2,2,2,2,2,2,2,1,1), which becomes C(4600).

C(4600) = C(1533×3+1), becomes D(3,X,1,1) where "X" is a string of 1533 2's in a row, which becomes C(B) where B is calculated by the following BASIC code: