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? 
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) 

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 