9,750 Pages

# Googology Noob

My favorite wikis
• ## Simulating Sigma(2) with a Turing Machine

January 9, 2016 by Googology Noob

On the Turing golf page I saw an interesting challenge: compute BB(2) with a Turing machine. I believe it is quite possible to do and shouldn't take more than 1000 states (probably much, much less), and that's what I'm planning to do here.

The first stage is obviously letting a Turing machine having its input as a set of instructions for a smaller TM (namely, for two states and two symbols). It so happens that I tried to do this a while ago with bigger TMs (5 states and 5 symbols took me 369 lines of instructions on this simulator), so this was the easy part for me. Full code as follows:

; A: Moves to the right and checks what the current symbol is (encodes it as "s"). 0 * * r 0 0 x x r 1 1 x x r 1 1 _ s l pp0b 1 1 s l pp01 ; B: Moves left …
• ## Turing Machines

January 7, 2016 by Googology Noob

Here are some of my Turing machines.

Here are my Hardy Hierarchy machines. n|a=H_a(n), where n is a string of ones. w=$$\omega$$.

Ordinals are connected by addition by placing them consecutively. Accepts 1's and w's.

0 * * r 0 0 _ _ l 1 1 1 _ l 2 1 | _ l halt 1 w _ l 3 2 * * l 2 2 _ 1 r 0 3 * * l 3 3 i 1 r 4 3 _ _ r 4 4 1 i r 5 4 | | r 0 5 * * r 5 5 _ 1 l 3

Here H_0(n)=n+1, H_a+1(n)=H_a(n+1), H_a(n)=H_a[n+1](n+1).

0 * * r 0 0 _ _ l 1 1 1 _ l 2 1 | 1 l halt 1 w 1 l 3 2 * * l 2 2 _ 1 r 0 3 * * l 3 3 i 1 r 4 3 _ 1 r 4 4 1 i r 5 4 | | r 0 5 * * r 5 5 _ 1 l 5

I haven't looked completely at everything here, but from what I can see: H_0(n)=n+2, H_a+1(n)=?, H_a(n)=H_a[n+3](n+2).

0 * * r 0 0 _ 1 l 1 1 1 _ l 2 1 | 1 l halt 1 w 1 l 3 2 * * l 2 2 _ 1 r 0 3 …

• ## Question Mark Notation

January 2, 2016 by Googology Noob

Here's a new function I thought up a few days ago. I believe that it reaches so far up to epsilon_w. Here's something I've been playing around with for a while.

Let's introduce the question mark: "?". The "?" is essentially an extension to the hyperoperators. Let's start small: a[?]b=a^b. You'll notice that the ? is inside a pair of square brackets, and you'll soon see why. a[?][?]b=a[?]a[?]a[?]...[?]a with b a's. In general, a[?][?][?]...[?][?]b=a[?][?][?]...[?][?]a[?][?][?]...[?]a[?][?][?]...[?]a...a[?][?][?]...[?]a with b a's. That is, a[?][?]b=a^^b,a[?][?][?]=a^^^b, and in general: a[?][?][?]...[?]b with n [?]'s=a^nb. Nothing new so far. What happens however, if we put the question marks together, inside the brackets?

Clearly, what we ne…

• ## GoogolX - Seperators

December 26, 2015 by Googology Noob

I have decided to change the format of my notation to a[X{a,b,c}]b. The previous form is not completely incorrect, but I prefer this.

First, let's make a[X{x[0]y}]b = a[X{x,x,x...x}]b with y entries. That's the very first and basic separator. Now, before we think about the next separator, we have to think how multiple [0] separators would react. For example, what would this solve to: 9[X{3[0]2[0]3}3 = 9[X{3[0]2,2,2}]3. We have a few options.

1. Weak option. 9[X{3[0]2,2,2}]3 = 9[X{3,3,2,2}]3. I think it's pretty obvious why this is lame.
2. Medium option. 9[X{3[0]2,2,2}]3 = 9[X{3[0]9[X{2,2,2}]3}]3. This is way stronger but still rather weak.
3. Strong option. This is a bit more complex, and the option I chose. 9[X{3[0]2,2,2}]3 = 9[X{3[0]2,9[X{3[0]2,9[X.…

• ## SuperJedi's X Function

December 25, 2015 by Googology Noob

I recently stumbles upon a pretty cool uncomputable function defined by SuperJedi224. You are allowed to use digits, the successor function (Sn=n+1), addition, multiplication, exponentiation, commas, parentheses and letters of the alphabet (no ellipses!). Commas and parentheses do not count as symbols (line breaks do). X(n) is the maximal output using n symbols. Here I will post some general bounds.

Here I will post some general bounds I have found.

The hyperoperators are very basic, and should be easy to define. Let's try!

U(a,b,1)=a^b
U(a,1,c)=a
U(a,Sb,Sc)=U(a,U(a,b,Sc),c)

That was 31 symbols. If we wanted to define a number we'd need to use 5 more symbols: O(9,9,9) and a line break. So I've proved that X(36) > f_w(9). How is that a general bo…