A quicker algorithm.

Question

Consider an algorithm which essentially counts to a certain number then halts.

Counting Algorithm C

Given any $n \in \Bbb N$

Step 1

$x_0=0$

Step 2

$\text{if} (x_n =n)\ \text{then}(\text{halt}) $

Step 3

$x_n=x_{n-1}+1$

Step 4

$\text{go to Step 2}$

Forgive my poor notation of an algorithm as I am not familiar that much with methods and notations used in computational science and I did not want to simply use c style syntax or something.

Now I ask the question for which the question is to be asked about; "Is there a quicker way to compute C then the obvious?"

Now my questions are these. Does this question even make sense? If in some way it does, is this in a very informal way (I hope you can understand what I mean) analogous to asking if there is a way to determine if a given natural number is prime; that is quicker then the obvious way?

Primes can indeed be solved in a faster way that the obvious (divide by all primes $<$ the square root), here is a reference https://en.wikipedia.org/wiki/AKS_primality_test — James, Jun 24 '15 at 13:08
As the algorithm produces no output and halts for any input, we can replace it with: 1. halt. (Incidentally, many optimzing C compilers might perform such an optimization) — Hagen von Eitzen, Jun 24 '15 at 13:10
@Hagen von Eitzen, thanks and I think that helps me to get along to knowing if the question is even well posed because the question asked about the specifically computing C and to compute C algorithm and so can not be replaced with another, but then there is trivially the answer No to my question's first part as in the definition requires that computation. So kinda trivially it seems the question is made so that to be the case. But then is there an analogy to the notion of computing an natural numbers primness? — marshal craft, Jun 24 '15 at 13:19
It does not have to do anything with primes unless there was a modulo or division operation involved. The question does not make much sense, how did you come up with it? — Wolfgang Brehm, Jun 24 '15 at 13:55
@marshalcraft: Hmm if you don't want to use even pseudo code, then you cannot describe an algorithm! Just by using C syntax does not mean you are using the C compiler, since you already have $n \in \mathbb{N}$ which is not available in any real-world computer. I can try to clarify it and you can see if it matches your real inquiry. — user21820, Jun 24 '15 at 14:59
to it as the primary object of my post. If perhaps a question is not well posed, and one asks to find out if a question is well posed, then the post as a whole should be well posed (unless stackexchange explicitly forbids that and hence a whole pertinent and valid set of mathematical questions). I flagged it but now after thinking I dont mind too much as some comments have provided some help thus far so it had been worth it. I do admit there is probably a way as the 1 answer had said perhaps using Turing machine notation and concept or lambda calculus but I am not familiar with it. — marshal craft, Jun 24 '15 at 15:02
@marshalcraft: If you are simply worried about drawing attention to that line of 'code', I don't think you should because I think people readily understand what you are asking about. The main reason I edited your question was because you did not edit to answer TonyK's question of "repeat what?" That is exactly why we have such a thing as programming languages and pseudo-code, because it is ridiculous to just say "repeat" and expect the meaning to be clear. The C syntax merely serves as a way to convey the meaning of the counting even as you did in your comment. But edit however you wish. — user21820, Jun 24 '15 at 15:08
But I'm not quite sure what you are asking. In computational complexity, when asked the question "is there a faster way to do this?" usually are only interested in the end result. I get the vibe that you view this counting problem as meaning that we should "count to $n$ one-by-one" rather than "count to $n$ any which way we want". — Jyrki Lahtonen, Jun 24 '15 at 21:06
@Jyrki Lahtonen Yes that essentially we are forced to count, or else as Hagen von Eitzen mentioned being as it out puts nothing we could just replace it with one step to just hault. But originally I had named the algorithm C and so the computation requires C be "computed". As user21820 mentioned I think essentially this requires I give some definition to compute. I am now considering deterministic and non deterministic methods like say doing a certain amount of steps so that one could easily calculate the probability that it halted. — marshal craft, Jun 24 '15 at 22:17
but it seems by any traditional sense of computation, that there is no quicker way to count provided you are constrained to count. with out cheating in some way. I had asked that because if I try and remove my intuition perhaps there is? Or at least I consider the possibility that there either is or isn't. Consider godel's incompleteness theorems which use the rather odd godel sentence and diagonalization. It seems to defy at least my institutional logic, a statement which is true yet not able to be proved. But with the creation of a formal theory to be shown inconsistent in another system ... — marshal craft, Jun 24 '15 at 22:23
it kinda starts to make sense at least to me and if only a little. Then there is the other thing to consider, that if there is no other way to count, faster than counting. Is it analogous to finding the primality of a given natural number? Sure there is added computational complexity of determining if a given natural number $n=m*k+r: k,r \in \Bbb N$ as Lykos said. But the part of keeping track of the $m,k$ seems like it must be reducable to the counting question, that is there is no other way. Primality test essentially forces us to count by the very definition of primes which is odd. — marshal craft, Jun 24 '15 at 22:35
Also User218200 did mention something to me in discussion about there being a recent proof that prime testing is somehow related to polynomial time. I'm sure I've misconstrued what he said but I forget what it was exactly. — marshal craft, Jun 24 '15 at 22:37
well maybe not so recent http://www.springer.com/us/book/9783540403449 — marshal craft, Jun 24 '15 at 22:55
Marshal, you seem to have misunderstood primality testing. Those tests answer "Yes" or "No" to the question of whether the input is a prime number or not. The game is then that the designer of the algorithm can be smart and accomplish that task without checking all the potential factors (non-trivial but not exceedingly deep math used there). OTOH your program doesn't output anything. No Y/N-answer, nothing. Therefore the question others have is: Complexity of which task exactly? — Jyrki Lahtonen, Jun 25 '15 at 06:21
@Jyrki Lahtonen well it doesnt need to, if a primality test at some point (please understand the tenuous use here of for loop) uses a for() with some body{} then the for() loop with no body is a subset of the computations being done. Sure at face value it can be considered stupid or naive to try and study the act of counting and exactly what it is, but at face value maybe Faraday could have been viewed as stupid for tinkering with pith balls and cat whiskers. — marshal craft, Jun 25 '15 at 18:04

user21820 · Answer 1 · 2015-06-24T14:52:08.160

The notion of how much time is taken should be defined to be somewhat independent of the machine, otherwise a machine that executes instructions faster would beat a slow machine that executes the same instructions. To do that we usually utilize Big-O notation which you can find on wikipedia. Also, we need a specific model of what instructions are allowed, and typically we use either Turing machines for purely theoretical results or the RAM model for many real-world applications. All these should be covered in a proper computational theory course.

Just for example, if you use a Turing machine, it is very cumbersome and slow to even increment a number stored on the tape by $1$. If the tape can contain at least two symbols (including the blank) then integers can be encoded in essentially binary and incrementing and comparison both will take $O(\log(n))$ steps as $n \to \infty$. So your counting algorithm $C$ would take $O(\log(n))$ steps to execute on a Turing machine. However, in the real-world we use computers that are more similar to RAM machines, where addition and comparison on 64-bit words always takes the same amount of time. Of course this already assumes that $n$ can be stored in $64$ bits, so it would be incorrect to say anything about asymptotic time complexity, but one must choose the model as appropriate. For example it is often said that balanced binary trees give an $O(\log(n))$ traversal from the root to any leaf, but that requires $O(1)$ pointer arithmetic so it is the RAM model that is more suitable than a Turing machine model, since a Turing machine would take linear time just to access each node.

Thank you I've had no course work in purely theoretical computational sciences, though I have had exposure to big O notation and tools in describing computational complexity. I think this remains purely theoretical and so do not wish to consider hardware capabilities. Turing machines both deterministic and non seem to be useful as I guess in order to give meaning to my question a definition of computation is needed and I read that traditionally that is the Turing machine. — marshal craft, Jun 24 '15 at 14:33
@marshalcraft: See my edit, where I give some examples which should tell you that Turing machines are not the ones you should care about in the real world. — user21820, Jun 24 '15 at 14:52

A quicker algorithm.

1 Answers1