Busier than the Busiest Beaver
25 Aug 2016, 7:20 am
I've managed to define a non-discrete computer which is more versatile than turning machines and thus it's a max sequence grows faster than the corresponding busiest beaver sequence. How much faster, I have no idea, but I defined it so it must bound it at all values.
Introduction
Alan Turning formalized the idea of computability using machine that alters symbols on a tape according the current state of the machine and a rule set connecting the different sets. If a problem can be solved by a Turing machine, than it is said to be computable. Each turing machine has a finite number number of states, and each state can be defined by the operation it performs on the tape, and which state it goes to next depending on what symbol was on the tape. For the sake of this demonstration, we'll say there are only two symbols which can be on the type (black or white), and a state can only perform one of five operations: do nothing, move the tape left, move the tape right, change the symbol to black, or change the symbol to white. Each state is followed by another state depending on whether the symbol was white or black, so that means for a machine with n states, each state can be configured in n*n*5 different ways (if black, if white, and the operation). Each Turning machine must have a non-configurable halting state, so that means there are (n*n*5)^(n-1) possible Turing machines with n states. That might sound like a lot, but the important fact is it's finite.
The Busiest Beaver sequence takes advantage of the fact there is only a finite number of possible Turing machines with a given number of states to assign a value to each number of states, forming the Busiest Beaver sequence. This is done by defining a business value for each Turing machine which halts on a blank tape (meaning it will reach it's halting state after finite number of states when applied to type which is initially white for segments of the tape). Business is defined by how many black symbols are on the tape when it halts. As the tape halts in a finite number of steps and it can only draw one symbol each step, the business of a halting Turing machine is always finite. Non-halting Turing machines can just be ignored. So for a given number n, a set can be constructed from the business of all Turing machines with n states that halt. As there are a finite number of machines which halt, this set will have finite cardinality, and thus one of it's elements will be larger than all the others. The busiest Beaver Sequence is defined as taking that value for the set associated with each n, with n as the number of states.
The Busiest Beaver sequence is notably not only non-computable, but grows faster than any computable sequence. Let's supposed there is a computable sequence S(x), meaning you have Turning machine with n states, and it takes a number x written as a sequence of symbols in binary on the tape as input, and it halts with the end number of symbols as output. Well you could build another machine with that's based around the machine which computes this faster growing sequence, but first it enters out 2n in binary on the tape, which will take less than n more states to generate as each symbol only takes one state to write, but can represent a number up to 2^n. After the sequence outputs, this new machine goes through more states which tack another symbol on the end of output, increasing it by one. We'll ensure this new machine has exactly 2n states. It's business will be S(2n) + k, where k is the number of symbols we could tack on at the end. As k is greater than zero, this will be larger than S(2n), and thus BB(2n) must be larger than S(2n). By defining hypercomputers (mathematical devices which can solve problems Turing machines can't) with a submachine that can solve the halting problem, it's fairly easier to make a hypercomputer which can hypercompute the busiest beaver sequence for Turing machines and then define a faster growing sequence related to this hypercomputers (which wouldn't be computable by those hypercomputers), but I'm going to take a slightly different approach. Instead I'm going to define hypercomputers which are continuous rather than discrete, and I have no idea if they are capable of hypercomputing the busiest beaver sequence, but I do know that using them I can define a sequence which bounds the busiest beaver sequence. My main purpose for doing this is to define a "large number" that neither infinite nor natural.
Defining the machine
So here is how this machine is defined. First, it uses a tape, but unlike the Turing tape it's not divided into discrete segments, but functions more like a number line, with a head at one point. Each point can exist in a continuum from pure white to pure black, with white being zero and black being 1. The head reads the integral of all points one half less than it, and one half greater than it. It can also make all points more black, or more white in it's area, changing their value linearly, but cutting off at pure black or white. Finally the head can move left or right at any speed, and do it while changing the value of points.
Like a Turing machine, a Ganondox machine has a finite number of states which controls the tape head. But it works a bit differently. While there is only a finite number of states, each state can be configured into an infinite number of combinations using real numbers. First, the next state is determined by whatever the head's integral read when the state STARTED, and it will go to the next state after a constant amount of time called one. Now, potentially the state could be configured so that each value between 1 and 0 goes to a different state, but for the sake of this we'll keep it simple and say it can only go two other states, with a single number as a boundary between the black region and the white region. We'll assume the boundary point is part of black region just to keep it simple. The boundary point can be defined with any real number using a single arbitrary continuous monotonic function that maps from all real numbers to the interval (0,1). Each state has two other real numbers associated with it, the derivative of the position of the head relative to time, and the derivative of the points in the head's range. It would seem superfluous that the final real number spans all reals rather than just the interval [0,1], but this distinction is needed because it does make a difference if the head is both moving and writing at the same time. So a state is configured based on those three real numbers, an n determining which state it will go into next if it's starting integral was in the white region, and an n determining which state it will go into next if it's starting integral was in the black region. So there is clearly an infinite number of machines for a given number of states.
Relating it to the Turing machine
For each Turning machine, a single Ganondox machine can be defined which acts identically to it. This is done by associating each configuration of a state of a Turing machine with a state of a Ganondox machine. First, this class of Ganondox machines have been defined as linking to two states from a finite number of states, the same as a Turing machine. So that can easily be linked. Next, we can arbitrarily declare that each of these select Ganondox machines which bijectively map with a Turing machine all have the border point defined by the real number 0, which corresponds to an integral of 1/2. It's arbitrary because we'll define these machines so the integral is always either 0 or 1. So all that's left to tackle is translating the five operations of the Turing machine to the other two real numbers which define a state in a Ganondox machine. This is not hard. Doing nothing obviously corresponds with a 0 for movement and a 0 for changing color. Moving the tape has 0 for changing color and -1 and 1 for movement of the tape head, equivalent to moving the tape right and left respectively. As they are negatives of each other, it ensures moving right then left is the same as staying still, and the speed perfectly divides the tape into segments that don't overlap for more than a single point, which has no effect on the integral. The operations for changing the symbol has the movement variable set to zero, and change in value set to 1 for change to black, and -1 for change to white. Because of the imposed cap, this will ensure that if the head doesn't move all the points in it's integral will be turned pure black or pure white, regardless of what color they were before.
Defining the bounding sequence
The business for a Ganondox machine can be defined in a similar manner to that a Turing machine. A Ganondox machine halts if it reaches it's halting state in a finite amount of time. The business value of a Ganondox machine which halts is defined as being the total integral (from positive infinity to negative infinity) of it's tape. The business will always be finite for a halting machine because the interval of non-zero values will always have finite span as there is some finite top speed for the head to move as described by one of it's states, and the head can only travel a finite distance. Further more, because all the points are capped at one, the max value for the machine's business is the span it covered.
However, there is one major problem that Ganondox machines have that Turing machines don't. There is only a finite number of Turing machines for a given number of states, but there is an infinite number of Ganondox machines. This means there might not be a maximum value for the set of all businesses for all halting Ganondox machines with a certain number of states. In fact, this is true for just one state, as you can define it so it goes at an arbitrarily fast speed while coloring it's wake at an even higher rate and thus create a arbitrarily large business. This will not do at all, otherwise you could just saying the fastest growing sequence is (zero, infinity). So we are going to have to put some artificial bounds on this to define a Bounded Max for Ganondox machines with n states. I feel there is nothing wrong with this, as Busy Beaver does a similar thing by restricting it to only machines that halt.
So let's define a set which does have a finite cardinality and choose a max from there. We found a single Ganondox machine which corresponds with each Turning machine, so we can start from those. Let's consider only the ones which halt, which we'll call the core set. If we take their business, we'll get the exact same results as the Busy Beaver. That technically works, as a function which can technically be said to bound itself if we're going with the greater or equal definition, but we want to create something with at least the potential to be greater than the Busy Beaver. So instead let's define a hyperbusiness for each of those select Ganondox machines. For a given arrangement of states defined by which other states they connect to, a specific Ganondox machine represents a point in a multidimensional space. This corresponds with the fact that for the same arrangement of states, there exists 5^(n-1) possible Turing machines, all the has to be configured is the operation for each state. Likewise with Ganondox machines, a particular machine with a given arrangement is just defined through by the three real numbers associated with each state. That means each arrangement represents a space with 3(n-1) dimensions. This sounds like a lot, but it's ultimately finite...which means the distance formula is defined for that space. If distance is defined, than so is ball, a set of all points within a certain distance of a central. So we'll use that to define hyperbusiness of machine. It can be defined as the maximum business of any machine in a ball of arbitrary radius from the initial machine. As a the center point is always part of any ball centered around it, this ensures the hyperbusiness is at least as much as the business. We can initially set this arbitrary distance to n. However, a ball still has an infinite number of points in it, so it's still possible for there to be no maximum. So we can definite the ball the hyperbusiness is calculated from as being the largest ball with a radius less or equal to n (the last part is important as otherwise the ball can be arbitrarily large and include machines with arbitrarily large business) that has a defined hypermaximum, which for now we assume to the finite maximum business. Even if there are machines with arbitrarily large business arbitrarily close to them, the radius can still be set to zero and then the hyperbisiness is the same as the business. However, there is STILL one last problem with our definition of hyperbusiness, which which is the fact that if there is a limit to infinity within the ball with the limit going outwards than there is NO largest ball with a defined hyperbusiness as the radius can be set arbitrarily close to point the limit reaches. We'll say a ball only has a well defined hypermaximum if it's looser defined hypermaximum is greater than that of any other ball whose radius is within some arbitrary difference of it's own (it's not enough for it merely be a local maximum, otherwise there could be ripple of unbounded local maximums closer and closer to the bound). We'll define that as being 1, and except the balls of radius n and 0 from this rule. While the definition is complicated, the take way is the hyperbusiness of a machine is finite, but greater or equal to it's business.
The Bounded Max for Ganondox machines with n states is defined as being the largest hyperbusiness of all the machines in the core set. As the hyperbusiness of each machine is greater or equal to it's business, that means the Bounded Max is greater to or equal the corresponding Busy Beaver and thus bounds it. The Bounded Max will be greater than the Busy Beaver if a machine whose business is the Busy Beaver value to have a hyperbusiness that is greater than it's business, though it's entirely possible a different machine to have a hyperbusiness which is greater than the Busy Beaver value. The main problem with the Bounded Max is that unlike Busy Beaver there is no guarantee that it is monotonically increasing. This is because when you increase the number of states of a machine all the previous machines are still included, and the business for the machine reminds the same. However, the hyperbusiness may change because n and the number of dimensions changed, which would impact the shape of the ball. I'm pretty sure it would still be monotonically increasing though, but I can't prove it.
Expanding the definition
It should be noted that the scheme of Turing machines used in this demonstration is slightly different than that used in the published Busy Beaver game. The main difference is that in it the original, a single state could both change the symbol on the tape AND move it. It also REQUIRES for the tape to move and change symbol, but we can just ignore that, the only problem is machines that can't be simulated, not ones that can. While the Ganondox machine is also capable of doing this, it doesn't act in the same way as a turning machine due to the fact the intervals at the edges of it's movement will only be partially affected, with the points at either ends of it's movement plus the edge of it's range won't be effected at all, while they would be if the head didn't move. In fact, if the head is on a black segment so it's integral is one, and it moves at speed one and it affects color at the rate of -1, than in the next state the previous segment will be pure "grey", the integral from that position would be 1/2. If the next segment is it moved to was also pure black, it would also be reduced to pure "grey", so this problem can't be fixed simply by increasing the rate at which it affects color; if it's enough to make the last segment white rather than black, it's enough to also make the next segment white rather than black. So here is my solution. Any Turing machine state which both moves the tape and changes the symbol on the tape can be broken down into two separate states, the first changes the symbol, the second moves the tape. As such, any Turing machine that can be written under this scheme in n states can be written under my original scheme in 2n states and we can just deal with that instead. But wait, there are couple other differences I neglected to mention. The first is that it can also invert the symbol in addition to not changing it. The Ganondox machine cannot do this due to it's continuous nature: a function either raises a value, lowers it, or keeps it the same, but to get from 1 to 0 and visa versa 1/2 must be crossed, but 1/2 cannot be both raised and lowered by the same function. The only way to implement this is by changing it so the color value is no longer a real number (whether complex, modular, or discrete), but I'm not going to do that. Instead, it only takes adding another state. If the state was black, we'll turn to white and be done, but if it was white, it will still be white, and it will move to an an extra state that turns it black, then we'll be done. As we already separated the moving operation from the changing operation, this only moves us from 2n to 3n states. Also, they define it so the halting state is not counted as a state, so we have to account for that as well. So the simple solution is to define BttBB(n) as being the Bounded Max for Ganondox machines with 3n + 3 states.
So that covers the official Busy Beaver sequence, but there are still other possible schemes for Turing machines. The most common one is having there be more than two possible symbols. This also means a state can lead to more than two other states. We'll just take off the arbitrary restriction of each state only going to two states we imposed earlier, and instead have there be as many intervals as there are symbols. Each symbol corresponds with an interval. But we still have one last problem, and that is that with the changing operation we can't just go from any state to any other like previously were we could just a define a turn-black or turn-white operation. To do this for when the only possible operations are sending straight to a symbol regardless of what the symbol it only takes one addition state: turn it to black, then turn it to a state that will turn it from black to the symbol that was initially desired. It will only take 3n + 3 states to mimic any such Turing machine, regardless of how many symbols it has. However, if more complex operations are available like inversion, than it will take up to n states to perform the operation. We can break up a single state into n states to solve this problem, just have the initial state turn it black, send it directly on to the next state if it was supposed to turn black, or send it to one of (n-1) intermediate states which then turn it to the correct symbol before passing it onto the next state. This places our formula at (n+1)(m+1) for bounding a scheme with m different symbols. We could however tackle them all at one by defining an n state Ganondox-plus machine as having up to n-1 boundary points, and thus keeping everything bound while eventually growing to have more possible states than any Turing machine. Change the formula to (n+1)^2, and boom, it will bound ANY Turing machine as Turing originally defined it as it will bound the Busy Beaver for any Turing machine with m states after m.
_________________
Cinnamon and sugary
Softly Spoken lies
You never know just how you look
Through other people's eyes
Autism FAQs http://www.wrongplanet.net/postt186115.html
27 Aug 2016, 8:05 pm
Introduction
Alan Turning formalized the idea of computability using machine that alters symbols on a tape according the current state of the machine and a rule set connecting the different sets. If a problem can be solved by a Turing machine, than it is said to be computable. Each turing machine has a finite number number of states, and each state can be defined by the operation it performs on the tape, and which state it goes to next depending on what symbol was on the tape. For the sake of this demonstration, we'll say there are only two symbols which can be on the type (black or white), and a state can only perform one of five operations: do nothing, move the tape left, move the tape right, change the symbol to black, or change the symbol to white. Each state is followed by another state depending on whether the symbol was white or black, so that means for a machine with n states, each state can be configured in n*n*5 different ways (if black, if white, and the operation). Each Turning machine must have a non-configurable halting state, so that means there are (n*n*5)^(n-1) possible Turing machines with n states. That might sound like a lot, but the important fact is it's finite.
The Busiest Beaver sequence takes advantage of the fact there is only a finite number of possible Turing machines with a given number of states to assign a value to each number of states, forming the Busiest Beaver sequence. This is done by defining a business value for each Turing machine which halts on a blank tape (meaning it will reach it's halting state after finite number of states when applied to type which is initially white for segments of the tape). Business is defined by how many black symbols are on the tape when it halts. As the tape halts in a finite number of steps and it can only draw one symbol each step, the business of a halting Turing machine is always finite. Non-halting Turing machines can just be ignored. So for a given number n, a set can be constructed from the business of all Turing machines with n states that halt. As there are a finite number of machines which halt, this set will have finite cardinality, and thus one of it's elements will be larger than all the others. The busiest Beaver Sequence is defined as taking that value for the set associated with each n, with n as the number of states.
The Busiest Beaver sequence is notably not only non-computable, but grows faster than any computable sequence. Let's supposed there is a computable sequence S(x), meaning you have Turning machine with n states, and it takes a number x written as a sequence of symbols in binary on the tape as input, and it halts with the end number of symbols as output. Well you could build another machine with that's based around the machine which computes this faster growing sequence, but first it enters out 2n in binary on the tape, which will take less than n more states to generate as each symbol only takes one state to write, but can represent a number up to 2^n. After the sequence outputs, this new machine goes through more states which tack another symbol on the end of output, increasing it by one. We'll ensure this new machine has exactly 2n states. It's business will be S(2n) + k, where k is the number of symbols we could tack on at the end. As k is greater than zero, this will be larger than S(2n), and thus BB(2n) must be larger than S(2n). By defining hypercomputers (mathematical devices which can solve problems Turing machines can't) with a submachine that can solve the halting problem, it's fairly easier to make a hypercomputer which can hypercompute the busiest beaver sequence for Turing machines and then define a faster growing sequence related to this hypercomputers (which wouldn't be computable by those hypercomputers), but I'm going to take a slightly different approach. Instead I'm going to define hypercomputers which are continuous rather than discrete, and I have no idea if they are capable of hypercomputing the busiest beaver sequence, but I do know that using them I can define a sequence which bounds the busiest beaver sequence. My main purpose for doing this is to define a "large number" that neither infinite nor natural.
Defining the machine
So here is how this machine is defined. First, it uses a tape, but unlike the Turing tape it's not divided into discrete segments, but functions more like a number line, with a head at one point. Each point can exist in a continuum from pure white to pure black, with white being zero and black being 1. The head reads the integral of all points one half less than it, and one half greater than it. It can also make all points more black, or more white in it's area, changing their value linearly, but cutting off at pure black or white. Finally the head can move left or right at any speed, and do it while changing the value of points.
Like a Turing machine, a Ganondox machine has a finite number of states which controls the tape head. But it works a bit differently. While there is only a finite number of states, each state can be configured into an infinite number of combinations using real numbers. First, the next state is determined by whatever the head's integral read when the state STARTED, and it will go to the next state after a constant amount of time called one. Now, potentially the state could be configured so that each value between 1 and 0 goes to a different state, but for the sake of this we'll keep it simple and say it can only go two other states, with a single number as a boundary between the black region and the white region. We'll assume the boundary point is part of black region just to keep it simple. The boundary point can be defined with any real number using a single arbitrary continuous monotonic function that maps from all real numbers to the interval (0,1). Each state has two other real numbers associated with it, the derivative of the position of the head relative to time, and the derivative of the points in the head's range. It would seem superfluous that the final real number spans all reals rather than just the interval [0,1], but this distinction is needed because it does make a difference if the head is both moving and writing at the same time. So a state is configured based on those three real numbers, an n determining which state it will go into next if it's starting integral was in the white region, and an n determining which state it will go into next if it's starting integral was in the black region. So there is clearly an infinite number of machines for a given number of states.
Relating it to the Turing machine
For each Turning machine, a single Ganondox machine can be defined which acts identically to it. This is done by associating each configuration of a state of a Turing machine with a state of a Ganondox machine. First, this class of Ganondox machines have been defined as linking to two states from a finite number of states, the same as a Turing machine. So that can easily be linked. Next, we can arbitrarily declare that each of these select Ganondox machines which bijectively map with a Turing machine all have the border point defined by the real number 0, which corresponds to an integral of 1/2. It's arbitrary because we'll define these machines so the integral is always either 0 or 1. So all that's left to tackle is translating the five operations of the Turing machine to the other two real numbers which define a state in a Ganondox machine. This is not hard. Doing nothing obviously corresponds with a 0 for movement and a 0 for changing color. Moving the tape has 0 for changing color and -1 and 1 for movement of the tape head, equivalent to moving the tape right and left respectively. As they are negatives of each other, it ensures moving right then left is the same as staying still, and the speed perfectly divides the tape into segments that don't overlap for more than a single point, which has no effect on the integral. The operations for changing the symbol has the movement variable set to zero, and change in value set to 1 for change to black, and -1 for change to white. Because of the imposed cap, this will ensure that if the head doesn't move all the points in it's integral will be turned pure black or pure white, regardless of what color they were before.
Defining the bounding sequence
The business for a Ganondox machine can be defined in a similar manner to that a Turing machine. A Ganondox machine halts if it reaches it's halting state in a finite amount of time. The business value of a Ganondox machine which halts is defined as being the total integral (from positive infinity to negative infinity) of it's tape. The business will always be finite for a halting machine because the interval of non-zero values will always have finite span as there is some finite top speed for the head to move as described by one of it's states, and the head can only travel a finite distance. Further more, because all the points are capped at one, the max value for the machine's business is the span it covered.
However, there is one major problem that Ganondox machines have that Turing machines don't. There is only a finite number of Turing machines for a given number of states, but there is an infinite number of Ganondox machines. This means there might not be a maximum value for the set of all businesses for all halting Ganondox machines with a certain number of states. In fact, this is true for just one state, as you can define it so it goes at an arbitrarily fast speed while coloring it's wake at an even higher rate and thus create a arbitrarily large business. This will not do at all, otherwise you could just saying the fastest growing sequence is (zero, infinity). So we are going to have to put some artificial bounds on this to define a Bounded Max for Ganondox machines with n states. I feel there is nothing wrong with this, as Busy Beaver does a similar thing by restricting it to only machines that halt.
So let's define a set which does have a finite cardinality and choose a max from there. We found a single Ganondox machine which corresponds with each Turning machine, so we can start from those. Let's consider only the ones which halt, which we'll call the core set. If we take their business, we'll get the exact same results as the Busy Beaver. That technically works, as a function which can technically be said to bound itself if we're going with the greater or equal definition, but we want to create something with at least the potential to be greater than the Busy Beaver. So instead let's define a hyperbusiness for each of those select Ganondox machines. For a given arrangement of states defined by which other states they connect to, a specific Ganondox machine represents a point in a multidimensional space. This corresponds with the fact that for the same arrangement of states, there exists 5^(n-1) possible Turing machines, all the has to be configured is the operation for each state. Likewise with Ganondox machines, a particular machine with a given arrangement is just defined through by the three real numbers associated with each state. That means each arrangement represents a space with 3(n-1) dimensions. This sounds like a lot, but it's ultimately finite...which means the distance formula is defined for that space. If distance is defined, than so is ball, a set of all points within a certain distance of a central. So we'll use that to define hyperbusiness of machine. It can be defined as the maximum business of any machine in a ball of arbitrary radius from the initial machine. As a the center point is always part of any ball centered around it, this ensures the hyperbusiness is at least as much as the business. We can initially set this arbitrary distance to n. However, a ball still has an infinite number of points in it, so it's still possible for there to be no maximum. So we can definite the ball the hyperbusiness is calculated from as being the largest ball with a radius less or equal to n (the last part is important as otherwise the ball can be arbitrarily large and include machines with arbitrarily large business) that has a defined hypermaximum, which for now we assume to the finite maximum business. Even if there are machines with arbitrarily large business arbitrarily close to them, the radius can still be set to zero and then the hyperbisiness is the same as the business. However, there is STILL one last problem with our definition of hyperbusiness, which which is the fact that if there is a limit to infinity within the ball with the limit going outwards than there is NO largest ball with a defined hyperbusiness as the radius can be set arbitrarily close to point the limit reaches. We'll say a ball only has a well defined hypermaximum if it's looser defined hypermaximum is greater than that of any other ball whose radius is within some arbitrary difference of it's own (it's not enough for it merely be a local maximum, otherwise there could be ripple of unbounded local maximums closer and closer to the bound). We'll define that as being 1, and except the balls of radius n and 0 from this rule. While the definition is complicated, the take way is the hyperbusiness of a machine is finite, but greater or equal to it's business.
The Bounded Max for Ganondox machines with n states is defined as being the largest hyperbusiness of all the machines in the core set. As the hyperbusiness of each machine is greater or equal to it's business, that means the Bounded Max is greater to or equal the corresponding Busy Beaver and thus bounds it. The Bounded Max will be greater than the Busy Beaver if a machine whose business is the Busy Beaver value to have a hyperbusiness that is greater than it's business, though it's entirely possible a different machine to have a hyperbusiness which is greater than the Busy Beaver value. The main problem with the Bounded Max is that unlike Busy Beaver there is no guarantee that it is monotonically increasing. This is because when you increase the number of states of a machine all the previous machines are still included, and the business for the machine reminds the same. However, the hyperbusiness may change because n and the number of dimensions changed, which would impact the shape of the ball. I'm pretty sure it would still be monotonically increasing though, but I can't prove it.
Expanding the definition
It should be noted that the scheme of Turing machines used in this demonstration is slightly different than that used in the published Busy Beaver game. The main difference is that in it the original, a single state could both change the symbol on the tape AND move it. It also REQUIRES for the tape to move and change symbol, but we can just ignore that, the only problem is machines that can't be simulated, not ones that can. While the Ganondox machine is also capable of doing this, it doesn't act in the same way as a turning machine due to the fact the intervals at the edges of it's movement will only be partially affected, with the points at either ends of it's movement plus the edge of it's range won't be effected at all, while they would be if the head didn't move. In fact, if the head is on a black segment so it's integral is one, and it moves at speed one and it affects color at the rate of -1, than in the next state the previous segment will be pure "grey", the integral from that position would be 1/2. If the next segment is it moved to was also pure black, it would also be reduced to pure "grey", so this problem can't be fixed simply by increasing the rate at which it affects color; if it's enough to make the last segment white rather than black, it's enough to also make the next segment white rather than black. So here is my solution. Any Turing machine state which both moves the tape and changes the symbol on the tape can be broken down into two separate states, the first changes the symbol, the second moves the tape. As such, any Turing machine that can be written under this scheme in n states can be written under my original scheme in 2n states and we can just deal with that instead. But wait, there are couple other differences I neglected to mention. The first is that it can also invert the symbol in addition to not changing it. The Ganondox machine cannot do this due to it's continuous nature: a function either raises a value, lowers it, or keeps it the same, but to get from 1 to 0 and visa versa 1/2 must be crossed, but 1/2 cannot be both raised and lowered by the same function. The only way to implement this is by changing it so the color value is no longer a real number (whether complex, modular, or discrete), but I'm not going to do that. Instead, it only takes adding another state. If the state was black, we'll turn to white and be done, but if it was white, it will still be white, and it will move to an an extra state that turns it black, then we'll be done. As we already separated the moving operation from the changing operation, this only moves us from 2n to 3n states. Also, they define it so the halting state is not counted as a state, so we have to account for that as well. So the simple solution is to define BttBB(n) as being the Bounded Max for Ganondox machines with 3n + 3 states.
So that covers the official Busy Beaver sequence, but there are still other possible schemes for Turing machines. The most common one is having there be more than two possible symbols. This also means a state can lead to more than two other states. We'll just take off the arbitrary restriction of each state only going to two states we imposed earlier, and instead have there be as many intervals as there are symbols. Each symbol corresponds with an interval. But we still have one last problem, and that is that with the changing operation we can't just go from any state to any other like previously were we could just a define a turn-black or turn-white operation. To do this for when the only possible operations are sending straight to a symbol regardless of what the symbol it only takes one addition state: turn it to black, then turn it to a state that will turn it from black to the symbol that was initially desired. It will only take 3n + 3 states to mimic any such Turing machine, regardless of how many symbols it has. However, if more complex operations are available like inversion, than it will take up to n states to perform the operation. We can break up a single state into n states to solve this problem, just have the initial state turn it black, send it directly on to the next state if it was supposed to turn black, or send it to one of (n-1) intermediate states which then turn it to the correct symbol before passing it onto the next state. This places our formula at (n+1)(m+1) for bounding a scheme with m different symbols. We could however tackle them all at one by defining an n state Ganondox-plus machine as having up to n-1 boundary points, and thus keeping everything bound while eventually growing to have more possible states than any Turing machine. Change the formula to (n+1)^2, and boom, it will bound ANY Turing machine as Turing originally defined it as it will bound the Busy Beaver for any Turing machine with m states after m.
All of these models define the same class of functions.
See https://en.wikipedia.org/wiki/Church%E2 ... ing_thesis
Have a look at the Ackermann Function. https://en.wikipedia.org/wiki/Ackermann_function
There is not a computer on earth than can calculated A(6,6)
_________________
Socrates' Last Words: I drank what!! !?????
29 Aug 2016, 8:04 pm
All of these models define the same class of functions.
See https://en.wikipedia.org/wiki/Church%E2 ... ing_thesis
Have a look at the Ackermann Function. https://en.wikipedia.org/wiki/Ackermann_function
There is not a computer on earth than can calculated A(6,6)
Did you even read what I wrote? The model I gave is NOT covered by the Church-Turing Thesis as it does not use natural numbers, and I mentioned the implications of such earlier. Anyway, while no computer has enough memory to calculate A(6,6), it is still COMPUTABLE and thus grows much slower than what is being discussed here.
_________________
Cinnamon and sugary
Softly Spoken lies
You never know just how you look
Through other people's eyes
Autism FAQs http://www.wrongplanet.net/postt186115.html
06 Sep 2016, 5:51 am
1. I don't freaking care if it is or is not, this is about math, not engineering. The busiest beaver function isn't physically realizable either. 2. Actually, it is theoretically possible to construct in a continuous world. Going about constructing such a device is another problem because all our known means for manipulating matter are computable and thus can't create arbitrarily precise real numbers, but it's still theoretically possible depending on exactly how physics works. Of all the models for hypercomputers, ones like this are the most likely to actually be possible to construct. 3. Now get out of my threads because you never have something valuable to contribute, you're just a contrarian with not real understanding of the subjects being discussed, and I despise your materialism.
_________________
Cinnamon and sugary
Softly Spoken lies
You never know just how you look
Through other people's eyes
Autism FAQs http://www.wrongplanet.net/postt186115.html
06 Sep 2016, 7:52 am
1. I don't freaking care if it is or is not, this is about math, not engineering. The busiest beaver function isn't physically realizable either. 2. Actually, it is theoretically possible to construct in a continuous world. Going about constructing such a device is another problem because all our known means for manipulating matter are computable and thus can't create arbitrarily precise real numbers, but it's still theoretically possible depending on exactly how physics works. Of all the models for hypercomputers, ones like this are the most likely to actually be possible to construct. 3. Now get out of my threads because you never have something valuable to contribute, you're just a contrarian with not real understanding of the subjects being discussed, and I despise your materialism.
The world is NOT continuous. Quantum theory was invented 117 years ago and is experimentally corroborated. The world is NOT continuous. The smallest pieces are measured in Planck units.
Furthermore your construct will not yield finitary algorithms. An algorithm must (in principle) produce its result in a finite number of steps. Computability and continuity are at odds with each other. So your construct exists in a world that does not exist. It does not sound very useful.
Go back to basics. Only a countable number of real values is Turing computable. If this set of reals is topologically dense in the metric space of real numbers then at least any real number could be the limit of a sequence of computable reals. Your best bet would be to demonstrate that the set of computable real numbers is dense in the set of reals. Or I will do it for you. A rational number is computable. Any real number is the limit of a Cauchy sequence of rationals QED. That means you can approximate any real to any degree of closeness by means of a Turing computable sequence of computable numbers.
For actual computations forget about continuity and compactness. They don't apply.
_________________
Socrates' Last Words: I drank what!! !?????
06 Sep 2016, 10:59 am
Steady on people!
However passionately held clashing ideas about hypothetical computing machines may be, the general rules still apply.
Please avoid personal attacks
viewtopic.php?t=73832
This includes insinuation, ridicule and personal insults, regardless of whether direct or indirect. Attacking an opinion, belief or philosophy is acceptable, but attacking the person making the comments is not.
Thanks!
_________________
Don't believe the gender note under my avatar. A WP bug means I can't fix it.
06 Sep 2016, 8:42 pm
Stop derailing my thread. Absolutely nothing you've said has anything to do with the topic of conversation, which is about a defined class of mathematical objects and an associated sequence, not a physical computer.
1. I don't freaking care if it is or is not, this is about math, not engineering. The busiest beaver function isn't physically realizable either. 2. Actually, it is theoretically possible to construct in a continuous world. Going about constructing such a device is another problem because all our known means for manipulating matter are computable and thus can't create arbitrarily precise real numbers, but it's still theoretically possible depending on exactly how physics works. Of all the models for hypercomputers, ones like this are the most likely to actually be possible to construct. 3. Now get out of my threads because you never have something valuable to contribute, you're just a contrarian with not real understanding of the subjects being discussed, and I despise your materialism.
The world is NOT continuous. Quantum theory was invented 117 years ago and is experimentally corroborated. The world is NOT continuous. The smallest pieces are measured in Planck units.
1. So what if quantum THEORY says the world is discrete? It's impossible to tell if such a theory is true through the scientific method as any discrete universe could be simulated in a continuous one. 2. General relativity is as experimentally collaborated as quantum mechanics are, but the two theories directly contradict each other. They can't both be right. Again, so what about quantum mechanics? 3. Actually, quantum mechanics DOESN'T say the word is discrete. While any value based on quantums is discrete, the wave functions quantum mechanics use are continuous, and thus the fundamental assumption of reality is that it's continuous. Also, you completely misused the definition of Plank's constant. It has actually has no practical value in the theory, it's just a unit based the ratio of various physical constants. It's not like the cells in Conway's Game of wave where they are the fundamental unit on which computations are performed. 4. It doesn't matter if this universe is continuous or not as there is no implication the computer should actually be represented with a physical machine. A Turing machine can't be physically realized either because it's impossible to build an infinitely long tape. That doesn't mean we can't discuss it, all these computers can be theoretically described using mathematics and language.
Your definition of computability is wrong. Use this as reference: https://en.wikipedia.org/wiki/Computation Notice how it says "that follows a well-defined model understood and expressed as, for example, an algorithm." It doesn't HAVE to use algorithms, it just has to be a well defined model. This is a well defined model. It's not Turing computable, but that's a given, otherwise it wouldn't be a hypercomputer. But, it actually DOES produce algorithms for any machine that halts, as the machine still has a finite number of states, and each state is a step in an algorithm which could be constructed. It's just that the operations performed by the steps in the algorithm have uncountable configurations, and thus it describes an uncountable number of algorithms. By your reasoning, the Turing machine isn't a valid model either because it doesn't always halt, and thus doesn't always produce an actual algorithm. It's actually impossible to define a model which can be configured to create every Turing computable algorithm, as all expressible sentences in a language are enumerable, but enumerability results in paradox when it's assumed every computable function is enumerable and every enumeration corresponds with a total function as a computable function could be constructed from the enumeration, but then it would have to include itself, and that would imply the existence of a function that contradicts itself. Therefor, you are being absurd.
The whole point of this is that is is NOT Turing computable. How do you not understand that? And being the limit of a sequence of computable reals means NOTHING as the actual sequence for organizing those reals so they have such a limit is uncomputable. It doesn't matter if you can compute it arbitrarily close, it's still just an approximation and thus not close enough. This is an obvious result from the uncountability of real numbers.
_________________
Cinnamon and sugary
Softly Spoken lies
You never know just how you look
Through other people's eyes
Autism FAQs http://www.wrongplanet.net/postt186115.html
07 Sep 2016, 3:02 pm
1. I don't freaking care if it is or is not, this is about math, not engineering. The busiest beaver function isn't physically realizable either. 2. Actually, it is theoretically possible to construct in a continuous world. Going about constructing such a device is another problem because all our known means for manipulating matter are computable and thus can't create arbitrarily precise real numbers, but it's still theoretically possible depending on exactly how physics works. Of all the models for hypercomputers, ones like this are the most likely to actually be possible to construct. 3. Now get out of my threads because you never have something valuable to contribute, you're just a contrarian with not real understanding of the subjects being discussed, and I despise your materialism.
The world is NOT continuous. Quantum theory was invented 117 years ago and is experimentally corroborated. The world is NOT continuous. The smallest pieces are measured in Planck units.
1. So what if quantum THEORY says the world is discrete? It's impossible to tell if such a theory is true through the scientific method as any discrete universe could be simulated in a continuous one. 2. General relativity is as experimentally collaborated as quantum mechanics are, but the two theories directly contradict each other. They can't both be right. Again, so what about quantum mechanics? 3. Actually, quantum mechanics DOESN'T say the word is discrete. While any value based on quantums is discrete, the wave functions quantum mechanics use are continuous, and thus the fundamental assumption of reality is that it's continuous. Also, you completely misused the definition of Plank's constant. It has actually has no practical value in the theory, it's just a unit based the ratio of various physical constants. It's not like the cells in Conway's Game of wave where they are the fundamental unit on which computations are performed. 4. It doesn't matter if this universe is continuous or not as there is no implication the computer should actually be represented with a physical machine. A Turing machine can't be physically realized either because it's impossible to build an infinitely long tape. That doesn't mean we can't discuss it, all these computers can be theoretically described using mathematics and language.
Your definition of computability is wrong. Use this as reference: https://en.wikipedia.org/wiki/Computation Notice how it says "that follows a well-defined model understood and expressed as, for example, an algorithm." It doesn't HAVE to use algorithms, it just has to be a well defined model. This is a well defined model. It's not Turing computable, but that's a given, otherwise it wouldn't be a hypercomputer. But, it actually DOES produce algorithms for any machine that halts, as the machine still has a finite number of states, and each state is a step in an algorithm which could be constructed. It's just that the operations performed by the steps in the algorithm have uncountable configurations, and thus it describes an uncountable number of algorithms. By your reasoning, the Turing machine isn't a valid model either because it doesn't always halt, and thus doesn't always produce an actual algorithm. It's actually impossible to define a model which can be configured to create every Turing computable algorithm, as all expressible sentences in a language are enumerable, but enumerability results in paradox when it's assumed every computable function is enumerable and every enumeration corresponds with a total function as a computable function could be constructed from the enumeration, but then it would have to include itself, and that would imply the existence of a function that contradicts itself. Therefor, you are being absurd.
The whole point of this is that is is NOT Turing computable. How do you not understand that? And being the limit of a sequence of computable reals means NOTHING as the actual sequence for organizing those reals so they have such a limit is uncomputable. It doesn't matter if you can compute it arbitrarily close, it's still just an approximation and thus not close enough. This is an obvious result from the uncountability of real numbers.
Quantum Theory is the most thoroughly tested physical theory ever. It has not been falsified or refuted empirically in 115 years. The worst that can be said about it is that it might not be complete....
_________________
Socrates' Last Words: I drank what!! !?????
07 Sep 2016, 9:41 pm
1. I don't freaking care if it is or is not, this is about math, not engineering. The busiest beaver function isn't physically realizable either. 2. Actually, it is theoretically possible to construct in a continuous world. Going about constructing such a device is another problem because all our known means for manipulating matter are computable and thus can't create arbitrarily precise real numbers, but it's still theoretically possible depending on exactly how physics works. Of all the models for hypercomputers, ones like this are the most likely to actually be possible to construct. 3. Now get out of my threads because you never have something valuable to contribute, you're just a contrarian with not real understanding of the subjects being discussed, and I despise your materialism.
The world is NOT continuous. Quantum theory was invented 117 years ago and is experimentally corroborated. The world is NOT continuous. The smallest pieces are measured in Planck units.
1. So what if quantum THEORY says the world is discrete? It's impossible to tell if such a theory is true through the scientific method as any discrete universe could be simulated in a continuous one. 2. General relativity is as experimentally collaborated as quantum mechanics are, but the two theories directly contradict each other. They can't both be right. Again, so what about quantum mechanics? 3. Actually, quantum mechanics DOESN'T say the word is discrete. While any value based on quantums is discrete, the wave functions quantum mechanics use are continuous, and thus the fundamental assumption of reality is that it's continuous. Also, you completely misused the definition of Plank's constant. It has actually has no practical value in the theory, it's just a unit based the ratio of various physical constants. It's not like the cells in Conway's Game of wave where they are the fundamental unit on which computations are performed. 4. It doesn't matter if this universe is continuous or not as there is no implication the computer should actually be represented with a physical machine. A Turing machine can't be physically realized either because it's impossible to build an infinitely long tape. That doesn't mean we can't discuss it, all these computers can be theoretically described using mathematics and language.
Your definition of computability is wrong. Use this as reference: https://en.wikipedia.org/wiki/Computation Notice how it says "that follows a well-defined model understood and expressed as, for example, an algorithm." It doesn't HAVE to use algorithms, it just has to be a well defined model. This is a well defined model. It's not Turing computable, but that's a given, otherwise it wouldn't be a hypercomputer. But, it actually DOES produce algorithms for any machine that halts, as the machine still has a finite number of states, and each state is a step in an algorithm which could be constructed. It's just that the operations performed by the steps in the algorithm have uncountable configurations, and thus it describes an uncountable number of algorithms. By your reasoning, the Turing machine isn't a valid model either because it doesn't always halt, and thus doesn't always produce an actual algorithm. It's actually impossible to define a model which can be configured to create every Turing computable algorithm, as all expressible sentences in a language are enumerable, but enumerability results in paradox when it's assumed every computable function is enumerable and every enumeration corresponds with a total function as a computable function could be constructed from the enumeration, but then it would have to include itself, and that would imply the existence of a function that contradicts itself. Therefor, you are being absurd.
The whole point of this is that is is NOT Turing computable. How do you not understand that? And being the limit of a sequence of computable reals means NOTHING as the actual sequence for organizing those reals so they have such a limit is uncomputable. It doesn't matter if you can compute it arbitrarily close, it's still just an approximation and thus not close enough. This is an obvious result from the uncountability of real numbers.
Quantum Theory is the most thoroughly tested physical theory ever. It has not been falsified or refuted empirically in 115 years. The worst that can be said about it is that it might not be complete....
That is utter nonsense. So what it hasn't been falsified in 115 years? Most physical theories are much older than that. Anyway, this is off topic, so STOP IT.
_________________
Cinnamon and sugary
Softly Spoken lies
You never know just how you look
Through other people's eyes
Autism FAQs http://www.wrongplanet.net/postt186115.html
