real count

May 2013
94
10
Code:
would you agree that any computer program can be turned into a Turing machine?
if so, i can make a very simple program that generates  
any positive real numbers between 2 and zero.
max = 2.0
min = 0
N = 1.0
while True:
   v = input("higher or lower or stop"+str(N))
   if v == "higher":
      min = N
      N = (max+N)/2
   elif v == "lower":
      max = N
      N = (N+min)/2
   elif v == "stop":
      break
 
Last edited:
Jun 2014
650
54
USA
If you are using Turing machines, then you're more interested in binary sequences than you are the set of real numbers I assume. It's well known that a bijection (a 1-to-1 function) exists between the set of binary sequences and the power set of natural numbers, $\mathcal{P}(\mathbb{N})$. With that in mind, we know that if you can biject the natural numbers onto the set of binary sequences, you can then also biject them onto $\mathcal{P}(\mathbb{N})$.

Cantor's theorem shows there is no bijection (surjection, to be precise) from any set onto its power set.

https://en.wikipedia.org/wiki/Cantor's_theorem

That said, I cannot make sense of your program (I'm not a programmer generally). You could attempt to explain it using general mathematical notation so I could understand. If you were to do so, it would be an exercise for you to practice notation and building your argument. It will not be a trip down a rabbit hole where you think you are going to disprove Cantor and drive yourself nuts trying to do so. I'm quite certain there's no way you've disproved Cantor with that 'little thing' (no offense intended, just a quick reality check here).
 
May 2013
94
10
i'm basically playing the "higher lower game" over the interval from 2 to 0.
for example, if i ask for a whole number 1 to 100, lets say you pick 57.
i guess 50, you say higher. that means the minimum value N can be is 50.
so i guess 75. now you say lower, that means the maximum value n can be is 75. and so on.
 

v8archie

Math Team
Dec 2013
7,709
2,677
Colombia
Code:
would you agree that any computer program can be turned into a Turing machine?
if so, i can make a very simple program that generates  
any positive real numbers between 2 and zero.
max = 2.0
min = 0
N = 1.0
while True:
   v = input("higher or lower or stop"+str(N))
   if v == "higher":
      min = N
      N = (max+N)/2
   elif v == "lower":
      max = N
      N = (N+min)/2
   elif v == "stop":
      break
That program never terminates for non-terminating decimals.
 
Aug 2012
2,464
761
i'm basically playing the "higher lower game" over the interval from 2 to 0.
for example, if i ask for a whole number 1 to 100, lets say you pick 57.
i guess 50, you say higher. that means the minimum value N can be is 50.
so i guess 75. now you say lower, that means the maximum value n can be is 75. and so on.
When you play the over/under game with natural numbers, the process must terminate within finitely many steps.

If you run your real number over/under algorithm for finitely many steps, it will always terminate at a rational number.

If you run it for infinitely many steps it will indeed generate a real number, but that's no different than saying a real number has a binary representation, for example 1/3 = .01010101010101... In fact that's exactly what a binary representation is: Infinitely many choices of nested decreasing intervals converging to a unique value.
 
Last edited:
Jun 2014
650
54
USA
i'm basically playing the "higher lower game" over the interval from 2 to 0.
for example, if i ask for a whole number 1 to 100, lets say you pick 57.
i guess 50, you say higher. that means the minimum value N can be is 50.
so i guess 75. now you say lower, that means the maximum value n can be is 75. and so on.
Guessing implies randomness too, which doesn't really work well if trying to establish a surjection. That is, if you randomly selected infinitely many real numbers 1 by 1 perfectly, you still couldn't manage to select all of the reals on a given interval unless you were allowed uncountably many selections.

Here's my latest attempt at being a Cantor crank: :D

https://math.stackexchange.com/questions/3432667/enumeration-of-a-very-large-ordinal
 
Oct 2009
927
351
Does your program require input from a user? Say somebody behind his computer saying higher/lower? That is not allowed in a turing machine. Neither are things like infinite memory.

Infinite computation time is ok though. It doesn't have to finish in finitely many steps.
 
May 2013
94
10
here would be my code to approximate Chaitin's_constant
Code:
import random
import time
from bitstring import BitArray
success = 0
fail = 0
while j < 10000000:

"""step 1: create a finite but unbound number of states. """

   stateNum = 1
   while True:
      g = random.random(0,1)
      if g < 0.9:
         stateNum += 1
      else:
         break

"""step 2: assign random characteristics to each state."""
   cards = {"H": [0,"H", 1,"H"]}
   letters = 0     
   for i in range(0,stateNum):
       state = ""
       if letters%26+ 65 == 72:
          letters += 1
       state += chr(letters%26 +65) 
       temp = letters
       while temp >25 :
          temp = temp //26
          leta = temp %26
          if leta +65 == 72:
             leta += 1
          state += chr(leta +65)
       direction1 = random.randint(0,1)
       if direction1 == 0:
          direction1 = "L"
       else:
          direction1 = "R"
       direction2 = random.randint(0,1)
       if direction2 == 0:
          direction2 = "L"
       else:
          direction2 = "R"
       gotostate1 = random.randint(0,stateNum-1)
       temp = gotostate1
       gotostate1 = ""
       while temp >26 :
          temp = temp //26
          leta = temp %26
          if leta+65 == 72:
             gotostate1 = "H"
             break
          gotostate1 += chr(leta +65)
       gotostate2 = random.randint(0,stateNum-1)
       temp = gotostate2
       gotostate2 = ""
       while temp >26 :
          temp = temp //26
          leta= temp %26
          if leta+65 == 72:
             gotostate2 = "H"
             break
          gotostate2 += chr(leta +65)
       cards += {state:[random.randin(0,1),direction1,gotostate1, random.randint(0,1), direction2, gotostate2]}
       letters += 1

"""step 3: randomly intialize the tape"""
   tape = BitArray(10000000)
   for i in range(0,len(tape))
      tape[i] = random.randint(0,1)
   startloc = random.randint(0,len(tape)-1)
   StartState = "A"
   t0 = time.time()

""" run the machine untill either it goes off the tape, it takes more than an hour to run, or reaches H """
   while True:
      if tape[startloc] == 0:
         tape[startloc] = card[StartState][0]
         if card[StartState][1] == "L":
            startloc -= 1
         else:
            startloc += 1   
         StartState = card[StartState][2]
      else:
         tape[startloc] = card[StartState][3]
         if card[StartState][4] == "L":
            startloc -= 1
         else:
            startloc += 1   
         StartState = card[StartState][5]
      if StartState = "H":
         success += 1
         break
      if startloc < 0 or startloc > 10000000:
         fail += 1
         break
      if time.time()-t0 > 3600:
         fail += 1
         break
   j+=1
 
Last edited:
Aug 2012
2,464
761
here would be my code to approximate Chaitin's_constant
I don't have to read your code to know it's wrong, if by approximate you mean that you can approximate it to any desired degree of precision. If you could do that with a program then you could solve the Halting problem. Turing proved that impossible in 1938.