-3

Imagine a non-halting Turing machine that repeats the same calculation forever.

Let us assume that each time it runs its algorithm it increments a loop counter.

Surely such a machine is conceivable in principle?

Now imagine that each time the calculation is performed the Turing machine "wakes up" and finds itself in one of an infinite set of identical conscious moments.

Let us assume that during each moment the Turing machine asks itself the question:

What is the probability that the loop counter currently has some particular value n?

Now the Turing machine's current moment is just one moment in an infinite ensemble of identical moments each with a different loop counter value.

Therefore the probability that the current moment's loop counter value has some particular value n is 1/infinity which is zero.

This reasoning holds true for all loop counter values n.

Thus the probability that the Turing machine finds itself in a moment with any loop counter value must be zero.

But the current moment must have some loop counter value.

It seems that we have a contradiction.

Thus, while a non-halting Turing machine that repeats the same calculation is conceivable in principle, the above argument suggests that a conscious version of such a machine is not.

I think that the problem is with the assumption that a Turing machine can produce conscious awareness by implementing an algorithm.

Improve this question
3
  • 1
    Your argument would seem to apply just as well in the situation where it was the conscious machine operator who was "waking up" and asking himself what value the counter might now show.
    – JDH
    Commented Dec 9, 2013 at 16:50
  • I find it difficult to assume a human operator could live forever even in principle.
    – John Eastmond
    Commented Dec 9, 2013 at 17:04
  • However one can imagine a Turing machine running forever simply by enclosing its algorithm in an unconditional loop.
    – John Eastmond
    Commented Dec 9, 2013 at 17:30

3 Answers 3

Reset to default
3

The crux of the apparent contradiction is the statement:

"Thus the probability that the Turing machine finds itself in a moment with any counter value must be zero."

This statement is false.

The probability of "any state" is the sum of the probabilities for each state; this always sums to one; Mathematically, for any N number of states; the probability of each state is 1/N, but there are N so the net probability is Nx(1/N)=1. Then you can take the limit as N goes to infinity; but the result is still that the net probability is 1.

Another way to reach the same limit is to take a Geometric distribution (which is always defined over an infinite number of states) and take the limit as p goes to 0.

Improve this answer
4
  • I don't think you can have a uniform probability distribution over an infinite set of states.
    – John Eastmond
    Commented Dec 9, 2013 at 17:15
  • 1
    Can you have a uniform distribution over a bounded continuous variable (e.g. the uniform distribution between 0 and 1)? I'd say that you can, and that it involves an infinite number of states.
    – Dave
    Commented Dec 9, 2013 at 17:37
  • The idea in use of the word "limit" is that you can construct a perfectly sensible probability distribution that is arbitrarily close to any way that you would define a "uniform" distribution.
    – Dave
    Commented Dec 9, 2013 at 17:39
  • You can have a uniform probability density over an uncountable infinity of real numbers but I don't think you can have a uniform probability distribution over a countable infinity of integers.
    – John Eastmond
    Commented Dec 9, 2013 at 18:09
2

This question has nothing to do with Turing machines, it's more about Measure Theory. It's well-known that it's not possible to define uniform finite measure on infinite countable sets such as integers. There are 2 common ways around it:

First method: define a set of measures on a filter and take a limit. In your example fix N, assume probability 1/N for each value. Then calculate whatever probability you want to calculate. Then take limit of your result for N->infinity.

Second method: define non-uniform measure that sums up to a finite number. In your example for each value n assume probability C/A^n, for some fixed value A, and C is a fixed normalizing coefficient that would make the whole series converge to 1. Then compute whatever probability you need in this non-uniform measure. Then take limit A->1.

EDIT: A small (not-too-rigorous, but essentially right) demonstration how the second method of dealing with probabilities over infinite countable sets works.

A question: let N be a "random" positive integer. What is the "probability" that N has no multiple prime factors? That is, what's the probability that N does not divide a complete square other than 1?

The difficulty: the set of integers is an infinite countable set, therefore one cannot assign equal measure to all integers.

The idea: assign to every integer N measure 1/N^s for some parameter s. Then compute the "probability" in that measure. Then take a limit s->0. Since 1/N^0=1 for any N that would correspond in the limit to the uniform measure that cannot be assigned directly.

A sketch of the core of the solution: the sum 1/N^s is of course the Riemann zeta-function \zeta(s). Rewrite the expression according to Euler's product formula. Write down Euler product with single prime factors. Divide the 2nd expression by the 1st one. Get the answer 1/\zeta(2s).

The method in question at work: take the limit s->0. Arrive to the answer 1/\zeta(2). This is possible for technical reasons, due to the singularity at \zeta(1).

The answer: 1/\zeta(2), which happens to be 6/\pi^2.

The confirmation: take first 1000000 integers and count how many of them don't divide a complete square. Observe that the proportion is approximately 6/\pi^2.

The conclusion: assigning non-uniform probabilities and taking the limit works rather well.

Improve this answer
7
  • Imagine all the rational numbers between 0 and 1. Assume that each one has equal probability. In order to specify a particular rational number one could say whether it is in the bottom half or the top half of the interval. One could then continue this binary process for each subsequent smaller interval. One would need an infinite bit string to specify a rational number by this method. But there are an uncountable infinity of such bit strings and only a countable infinity of rational numbers. Thus we can't assign a uniform probability over a countable infinite set.
    – John Eastmond
    Commented Dec 9, 2013 at 21:27
  • @JohnEastmond, yes, as both you stated in your question and I mentioned in the answer, it's not possible to assign uniform probability to elements of an infinite countable set. It is, however, possible to perform meaningful calculations by first assigning non-uniform probability, with non-uniformity depending on a parameter, and then taking the limit of the answer as the parameter approaches the value that would make the probability uniform. Give me a min, I'll add an example to this answer.
    – Michael
    Commented Dec 9, 2013 at 21:36
  • The "correct weight" for a positive integer N is 1/N, not 1 as you suggest in your explanation. So the limit should be s->1 instead of s->0.
    – Thomas Klimpel
    Commented Dec 9, 2013 at 23:31
  • @ThomasKlimpel: \zeta function has a singularity at s=1. After properly removing the singularity the resulting \ksi function becomes symmetrical over the "critical line" x=1/2. More about \zeta function here. In particular, notice that s->1 corresponds to looking only at first N integers and giving them the same weight 1/N; s->0 corresponds to looking at all integers and giving them the same weight 1 (leading to infinite total probability); miraculously the results coincide.
    – Michael
    Commented Dec 9, 2013 at 23:51
  • Why should I care about a singularity of the \zeta function as s=1, if I want to compute the limit of 1/\zeta(2s) for s->1? And how should removing singularities of the \zeta function help fix up "incorrect weights" for the positive integers? (1/N^s)/\zeta(s) only defines a probability measure for real s>1, hence the limit s->0 is not helpful, even if 1 were the "correct weight" for a positive integer N.
    – Thomas Klimpel
    Commented Dec 10, 2013 at 0:47
1

Imagine a non-halting Turing machine that repeats the same calculation forever.

Let's make this concrete.

Assume the turing machine starts with an integer n on the tape, plus it's program which does this:

find j, construct a monomial which has the same value as the number of digits in n.. eg a sequence of 1's

find y, change base of j. multiply the monomial j * 9

compute, divide n / y

eg. 25/99

the program will never halt.

what is the probability that it will halt?

I say that it is infinitely close to zero but never equal to zero.

Is that a contradiction?

Therefore the probability that the current moment's loop counter value has some particular value n is 1/infinity which is zero.

That is false. It's infinitely close to zero but never equal to zero.

It seems that we have a contradiction.

For a given epsilon. it's not shown that a smaller epsilon would not result in a contradiction.

My argument is the same as that of the Pythagoreans in that the world can be represented through rational numbers.

Thus, while a non-halting Turing machine that repeats the same calculation is conceivable in principle, the above argument suggests that a conscious version of such a machine is not.

I think that the problem is with the assumption that a Turing machine can produce conscious awareness by implementing an algorithm.

I don't think that's the problem.

Rephrasing your question, do rocks have consciousness? While most people might scoff, it's traditional to assume that the earth is conscious.

If you think this is pointless I would appeal to the argument of ask someone 100 years ago how much data you could fit on the head of pin, then ask someone today. That's the true meaning of epsilon.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .