The prototypical example of a finite field is for a prime number.  We can also construct fields with elements by analogy with the complex numbers.  Choose a non-square and define to be the set of all formal expressions of the form with , together with the addition and multiplication laws  and .  One can easily check that is a field, with the reciprocal of given by , where and.  We can identify with the subfield of .

Here are two basic properties of fields, both of which are usually known as “Lagrange’s Theorem”:

Lagrange #1: A polynomial of degree with coefficients in a field can have at most roots in .  (This is completely false if we replace “field” by “ring”.)  See here for a proof in the special case which generalizes immediately to any field.  We just need the following special case: the only roots of in are .  This follows from the fact that in implies that either or .

Lagrange #2:  Let be a finite field with elements and let denote the nonzero elements of.  Then the order of any (defined as the smallest positive integer such that ) divides .  (This can be viewed as an extension of Fermat’s Little Theorem, the proof is basically the same: multiplication by permutes the elements of , and thus .  Hence .  Writing with integers such that , it follows that and hence .)

The following property of the fields will be crucial in what follows.

Key Lemma: For , we have .

Proof: Since is a quadratic non-residue modulo , Euler’s Criterion tells us that in .  Thus in .  From the binomial theorem, the fact that in , and Fermat’s Little Theorem, it follows that as desired.

In the puzzles, jumps are allowed on both lines, but they can’t overlap. At the final rabbit-sequence doodle at the end of the game, they allow jumps on every line and they can be bracket nested so and [()] is allowed, but ([)] seems to not be allowed.

I will use the following assumptions:

1. The tape starts with input (which is all 0s and 1s) followed by E (blanks)
2. The machine can use any fixed number of lines
3. Left-jumps are allowed on any line (I will use one left jump per line)
4. The machine can write ϵ, 0, and 1.

With these assumptions, the Google Doodle Machine is Turing Complete.

I tried to build an Alan Turing’s Doodle machine configuration that emulates the machine M4described in “Small Turing Machines and generalized busy beaver competition” that has a halting problem that depends on an open (up to my knowledge) Collatz-like problem. The full picture is available here.

… so even if the A.T.’s Doodle is perhaps not Turing complete (due to the non-overlapping left-only jump operator available only in the first row), it is powerful enough to walk the fine line of (un)decidability 😀

I think that even with a single left non-overlapping jump the Turing Doodle is Turing complete!. The (simple) idea is to use the tape itself to store the current state and use multiple cells to represent a larger alphabet.

For example a 2 states 8 symbols TM can be simulated using the following tape representation:

 HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

The Turing doodle can:

1. read s and branch to one of the two different horizontal areas representing STATE A and STATE B;
2. read b2,b1,b0 and branch to a row representing one of the eight symbols;
3. write the next symbol, move the head to the “macro cell” on the left or right, and store on it the next state; in the figure below these operations (that can be done on a sequence of cells using the actions move left/right and write) are called “MW”;
4. finally, transfer the control to the upper row that with a single left jump will bring the control back to step 1.

In the same manner, given a TM with an arbitrary number of states and alphabet symbols we can build an equivalent Turing Doodle machine DM.

For each TM state (except the halting one) we use 3 lines of the GDM. Each line corresponds to a possible input symbol ϵ, 0, or 1. To reach the right state from the top line, we have down-ways, these carry ϵ, 0, or 1 down to the proper line for each TM state. To reach the top again, we have up-ways, these carry 0, or 1 to the top line.

The GDM simulates the TM as follows:

1. Starts at the top left-corner of GDM, which correspond to the control for TM-state 1.
2. If in control corresponding to TM-state j, it reads the input and follows the path to the corresponding GDM line.
3. Upon reach the correct line, the GDM writes ϵ to the tape. This allows the GDM to walk left on the line without snagging any of the up-ways (since those only carry 0s and 1s). There will be no down-ways to snag because of the design.
4. The red box (is actually two boxes) writes down the read letter corresponding to the GDM line we are on (to undo the ϵ-write earlier) and simulates the TM move (left, right, or nothing)
5. The green box simulates the TM write (0 or 1).
6. The yellow box is a left-jump that jumps back to the correct up-way to transition to the next state (based on state-transition function of TM). Since the GDM has to write 0 or 1 in each state the previous step, it has to be carried by the up-way.

Pick your favorite universal TM and implement it in the above procedure to get a universal GDM.

1. one domain is computability, which studies what can be computed, and how in a rather abstract sense: largely what is described in Suresh Venkat’s answer.
2. another is algorithmics, that finds effective means to compute answers to specific problems, with specific constraints. Computability is a theoretical context for algorithmics.
3. semantics (for want of a better name), analyzes the conceptual organization of computational problems, and of algorithms, into higher level concepts, so as to factorize techniques that have proved useful and are often reused, such as the concept of subprogram,data-structures, modules, information hiding. It includes the development of mathematical tools that formalize adequately these concepts to allow high-level reasonning (Scott semantics for example). It also touches on the way this is expressed, thus on the separation and relation between syntax and semantics. Programming languages concepts are part of it (though language design is probably the pratical application of that knowledge). It can also include the relation between proof theory and computation theory, and the modern role of type systems.
4. another topic, which could develop more than it has so far, is the relation between computation and fundamental physics. For example. is there a relation between the limits on computation and the properties of the physical world, such as physical information density or the laws of thermodynamics. Quantum computing may improve a bit our computational prowess; could we hope for more? Some may dispute that this is still TCS, though there are TCS studies on hypercomputation.

1. 3 6 13 27 55 111 ...

All of these types of problems can be answered by a simple polynomial fit:

y=1720∗(−n6+39∗n5−325∗n4+1425∗n3−2194∗n2+2496∗n+720) < p easy if you think about it

first ten elements would be:

1,3,6,13,27,55,111,218,409,727,1224

Alice and Bob are perfectly logical and super intellegent. Their professor decides to play a game with them, and he tells them: “I have chosen two numbers x and y with 2≤y≤x≤100. I will tell Alice the value of their difference d=x−y and Bob the value of their ratio r=x/y. I stress that the ratio ris an integer, too.”

After the professor has told the difference to Alice and the ratio to Bob, the following exchange occurs:

1. Alice: I don’t know the numbers.
2. Alice: You might though. Do you know them?
3. Bob: No, I don’t know them.
4. Alice: Too bad, if you did I would know them too.
5. Alice: I still don’t know them though.
6. Bob: Me neither.
7. Alice: Oh really? Then I do.
8. Bob : Dang it; I still don’t.

What is the value of r?
What are the possible values for x and y?

This is how I reasoned:
There are 382 sets with 2 ≤y≤x≤100 where x/y is an integer.

Statement 1 says Alice doesn’t know the numbers.
This means that we can eliminate all sets that have a difference d that only appears once.
357 remain.

Statements 2 & 3 say that Bob doesn’t know them,
so we can eliminate sets that have a ratio r that only appears once.

Statement 4 however says, if it had been one of those sets, then Alice would know the numbers, because in all those sets, y=2.
So d must be one of the d’s that appeared in one of the sets just eliminated.
Only 49 other sets have one of those d’s.

5: Alice still doesn’t know the numbers, so we can again eliminate sets with a unique d.
46 remain.

6: Bob still doesn’t know, so we can eliminate sets with a unique r.
34 remain.

7: Now, suddenly Alice knows the numbers, so d must be unique among the remaining sets.
Only 4 sets remain:
{x=85, y=17, r=5, d=68}
{x=95, y=19, r=5, d=76}
{x=91, y=13, r=7, d=78}
{x=100, y=4, r=25, d=96}

8: Bob still doesn’t know x and y, so r is still not unique.
Only 2 sets remain:
{x=85, y=17, r=5, d=68}
{x=95, y=19, r=5, d=76}
So r is 5 and x,y is either 85,17 or 95,19. Alice knows, but we don’t.

just some enigmatic partitions of the chemical elements

I have partitioned the chemical elements into two groups based on a certain property that is shared by some of them, but not by the remaining ones.

The following elements have my enigmatic property:

Bismuth, Chlorine, Gold, Helium, Iodine, Mendelevium, Nitrogen, Silver

The following elements do not have my enigmatic property:

Dubnium, Erbium, Nobelium, Terbium, Ytterbium, Yttrium, Zinc, Zirconium

Which of the following elements does have this property?

Aluminium, Fluorine, Francium, Gallium, Lutetium, Neon, Oxygen, Polonium.

property: having a prime atomic number.

first group:

Bismuth 83
Chlorine 17
Gold 79
Helium 2
Iodine 53
Mendelevium 101
Nitrogen 7
Silver 47
All of these atomic numbers are prime.

second group:

Dubnium 105 (divisible by 5)
Erbium 68 (divisible by 2)
Nobelium 102 (divisible by 2)
Terbium 65 (divisible by 5)
Ytterbium 70 (divisible by 5)
Yttrium 39 (divisible by 3)
Zinc 30 (divisible by 5)
Zirconium 40 (divisible by 5)
None of these atomic numbers are prime.

final group:

Aluminum 13 (prime)
Fluorine 9 (divisible by 3)
Francium 87 (divisible by 3)
Gallium 31 (prime)
Lutetium 71 (prime)
Neon 10 (divisible by 5)
Oxygen 8 (divisible by 2)
Polonium 84 (divisible by 2)
Aluminum, Gallium, and Lutetium have the property.

How I solved the Gear Cube Extreme

1. Solve the middle layer
2. Solve the corners
   2.1 Resolve middle layer parity and centers (if there is a problem)
3. Move the edges to the correct layers
4. Move the edges into the correct positions
5. Rotate the edges into the correct orientations

0. Notation

I’m using R, L, B, F to indicate a 180-degree turn of each side. This is because, as you know, you cannot rotate each side except in increments of 180. U, D, however, will refer to 90 degree turns of the upper and lower layers.

If I refer to a corner using three letters, those letters indicate the faces that corner touches. For instance, the UFL corner is the upper front left corner.

1. Solve the middle layer

This step is pretty easy, honestly, and you should be able to do this intuitively using the side moves. However, a couple algorithms that can help if you’re truly stuck on this: use R B R to move the edges to a more understandable position, and R2 or L2 to rotate the middle slice 180 degrees to solve the centers.

2. Solve the corners

For now, keep one hand firmly on two pieces of the center layer, and don’t move it. If you do, you’ll need to restore it, which isn’t a difficult problem, but I’m not going to cover how to do it because it shouldn’t happen. We’ll restore the middle layer at the end of this step.

I solve this in two steps: first, by solving the bottom layer corners; then, by solving the top layer corners.

The algorithm I use to solve bottom layer corners is pretty simple: R U R U' R' This moves the UFL corner into the DFL position without disturbing the other pieces on the bottom layer. The process for solving the bottom layer pieces is simple:

• Find a bottom-layer corner on the top layer, and find where it should go. Use U to place the piece in the UFL position, and use D to place its target location in the DFL position. Then, execute the algorithm.
• Here, ‘target location’ refers to a spot relative to other properly-placed pieces.
• If there are no top-layer pieces on the bottom layer, then just move a piece there for reference.
• If there are no bottom-layer pieces on the top layer, find an incorrectly-positioned piece on the bottom layer and swap it with any top-layer piece.

After this, you’re on to the top layer corners. One algorithm should be sufficient here: R U R U' R' (U' D) R U' R U R'. This swaps the UFL and UBL corners. Executing this strategically should lead you to a solved upper layer.

2.1 Resolve middle layer parity (if it exists)

If the two middle layer pieces you’ve been holding onto are flipped, then execute the following algorithm:D' R D R (D' R)2 D' R' U' D R'. At this point, there will be one yellow corner on the top, and a corresponding purple corner on the bottom. Proceed from the beginning of Step 2 – this shouldn’t take long to complete.

If there’s a problem with a particular center, just rotate an adjacent L/R or F/B slice 180 degrees and check again.

3. Move the edges to the correct layers

This step takes only one algorithm: (R U R' U')5. This swaps the UF and BR edges. Use this as many times as needed, placing an incorrect edge in each place and swapping them.

4. Move the edges into the correct positions

For this, you need two algorithms. These images are courtesy of Ruwix.

Left: R2 U R2 U; Right: R D R U2 R2 U2 R D' R'

This should cover most cases intuitively. Use U and D to move the pieces in position.

If you end up with three pieces on one layer that need to be swapped, then do not solve the middle of the three first and you’ll be alright. To do this, use the second algorithm twice – the first time will flip two edges on the other layer, but the second time will flip them back.

5. Rotate the edges into the correct orientations

Next, you’ll need the following two algorithms:

• (R U)2 (R )4 (U' R')2 (CCW)
• (R U)2 (R')4 (U' R')2 (CW)

These two algorithms will do strange things. They both turn the bottom front edge piece in different directions, which is really the focus of them, but they also turn the UL, UB, and UR edges as well.

The first step is to solve the bottom-layer edges. If the top layer has a solved edge, move it into the UF position. If it doesn’t have one, do so immediately after you solve the first bottom-layer piece. For each unsolved edge on the bottom layer, execute the appropriate algorithm above.

If the cube is not solved, flip it over. Repeat this process for all the edges again.

If the cube is still not solved, flip it over again. Once you repeat the process again, the edges are guaranteed to be solved.