My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Number Theory (http://mymathforum.com/number-theory/)
-   -   Turing Machine (http://mymathforum.com/number-theory/36797-turing-machine.html)

krausebj0 June 28th, 2013 04:13 AM

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 June 28th, 2013 05:01 AM

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)


All times are GMT -8. The time now is 09:15 PM.

Copyright © 2019 My Math Forum. All rights reserved.