My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Closed Thread
 
LinkBack Thread Tools Display Modes
June 28th, 2013, 03:13 AM   #1
Senior Member
 
Joined: Nov 2011

Posts: 599
Thanks: 0

Turing Machine

Turing Machines

Let the tape be Ai. Ai can be a finite sequence of reals. Ai can be an infinitely large sequence of reals. It is up to the person running the turing machine.

I only express reals as infinitely large sequences and work in binary. For my purposes, 0.1 would have to be expressed as 0.0111.... I also only use reals greater than 0 and less than or equal to 1. Assume these notations and preferences are used throughout. To be clear, let the set I equal the reals, expressed using my preferences, that are greater than 0 and less than or equal to one.

Define Ai = i1, i2, i3, ..., i_n


Define Turing Machine #1

The machine will read the tape Ai and perform mechanically the same operation for each element of Ai.

The first operation is to take each element of Ai and create a set by mapping out its bit strings where each bit string is equal to the dyadic rational formed by taking the nth 1 of each real in Ai. I am only using infinintely large sequences, so the first operation results with:

Operation 1

Input --> output
i1 --> i1d = { i11, i12, i13, i1n, ..., }
i2 --> i2d = { i21, i22, i23, i2n, ..., }
i3 --> i3d = { i31, i32, i33, i3n, ..., }
...
Examples:
0.111... --> { 0.1, 0.11, 0.111, ... }
0.1101... ??> { 0.1, 0.11, 0.1101, ... }
0.10101... ??> { 0.1, 0.101, 0.10101, ... }
...

Each output will be an infinitely large set of dyadic rationals. Each output will be unique for every possible element of Ai.

The first touring machine allows for the definition of the set RI. If we let Ai equal I itself, the output would be all elements of RI.




Question1: Can Ai be replaced with I itself if using a turing machine? The output is unique for each element of I.

Question2: For any finite sequence Ai, does the order of the sequence matter when considering the union of all sets ind?

Question3: Is the union of all sets ind for any finite Ai a unique set?

Question4: If the first turing machine halts when all dyadic rationals have been included in at least one ind, then the first turing machine halts at precisely the moment that there exists an ix such that the union of all i(n <= x)d is equal to the set of dyadic rationals greater than 0 and less than 1, expressed in binary notation?
krausebj0 is offline  
 
June 28th, 2013, 04:01 AM   #2
Senior Member
 
Joined: Nov 2011

Posts: 599
Thanks: 0

Re: Turing Machine

By the way, the answer to the first question seems obvious if you are familiar with Cantor's Theorem, but it is not that simple guys... Actually proving that Ai cannot be replaced with I itself is going to take a lot more than just Cantor's Theorem.

Answer #2: no

Answer #3: yes

Answer #4: yes (this result is stunning)
krausebj0 is offline  
Closed Thread

  My Math Forum > College Math Forum > Number Theory

Tags
machine, turing



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Turing machine jenifer Applied Math 1 December 28th, 2011 11:08 AM
Turing machine 2 jenifer Applied Math 0 November 2nd, 2011 07:50 AM
Turing Machine Problem... Help please ikurwa Applied Math 0 April 16th, 2011 10:37 PM
Help On Turing Machine Problems Please Christi123 Applied Math 1 April 14th, 2008 04:33 AM
A Turing Machine Question Christi123 Applied Math 0 March 22nd, 2008 03:25 PM





Copyright © 2019 My Math Forum. All rights reserved.