Number Specifications And Turing Machines

Response 2: Turing machines allow uncountable specifications

[Alistair asks for clarification then factors out the mess :)] [true, indeed, and that's because I couldn't see that it was relevant. by putting it back in, you've helped me see the relevance :-). Now I refactored it again to try to clean it up some more... I think you can delete large sections of the following -AC] [That must be right since we're specifically discussing finite definitions. -- vk]

If you allow definitions (specifications) to be of countable length instead of merely finite length then the set of all sentences is an uncountable infinity. The power set of all sentences is then of cardinality aleph_2 instead of merely aleph_1. In other words, while letting the sentences in your language be of infinite length lets you specify all the reals, it also lets you generate a set of new numbers which are then unspecifiable. In mathematical logic, there is a natural association between the nature of the definitions and the nature of the numbers you want to specify. Not so with Turing machines where the restriction of finiteness on valid programs and output seems arbitrary.

This sort of recursive thing applies to the Halting problem. You can't use a Turing machine to solve the halting problem for all Turing machines. However, if the universe is not a Turing machine but a more powerful continuum based machine then it can solve the halting problem for all Turing machines. Of course, this just creates a new problem which requires a still more powerful machine to solve.

This recursion again occurs in Goedel's Second Incompleteness Theorem which proves something like that in order to decide a sentence in a formal system, the axiomatic system must be at least as powerful as the sentence itself. There's an example with proving the reals are the reals using arithmetic but I can't recall the details.

This is exactly why using Turing machines is a bad idea. If you move it back to mathematical logic, the issues are much clearer. The question of whether the machine halts or not becomes irrelevant. -- RichardKulisz [Can we stick to the subject, please?]

If this page has a goal, I think it's as a springboard for exploration of the concept of mathematical truth. We shouldn't be too reductionistic on this page. In the above, I'm trying to explain a general pattern I perceive. It's this pattern that causes my reaction to be 'Huh, that's nice.' instead of 'Wow!' It's the context of a concept that lets people get a handle on it. When I first learned about infinities in high school, they were unfathomable. It's only after learning about transfinite numbers that I got a handle on them. -- RichardKulisz

Richard asserts that there are an uncountable number of Turing machine programs (of countable length), and so once again the set of specifiable reals is uncountable. Let's separate those two, and how about if you two (Vicki / Richard) please moderate / refactor your sections since you know what you're up to.

Umm Alistair, my point is actually that each definition of a 'valid program' is naturally associated with a set of numbers most of which are unspecifiable. The set of programs of finite length is associated with the reals, most of which are unspecifiable using finite programs. The set of programs of countable length is associated with the set of all functions, most of which are unspecifiable using countable programs. And so on.

Try to get JoshuaGrosse and GarethMcCaughan to contribute, they know a lot more than I do. -- RichardKulisz

[I think most of the following FSM/Turing discussion is subsumed by the above paragraphs. Can these be deleted?]

'About Turing Machines and Specifications: (Can anyone write a resultant synopsis of the following? I think it all simply boils down to programs are finite in length, run in discrete steps, and so can only produce countable number of outputs. Pi is well specified already, as the ratio between a circle's circumference and diameter, so it is already taken care of.)

If you only mean to talk about finite specifications, you should drop all references to Turing Machines and talk only about Finite State Machines, which are very different. Or at least, this is the way it all seems to me. I'm probably off-base somewhere and in that case, I'm merely pointing the way to where arguments can be clarified.'' -- RichardKulisz

First we need some conventions to deal with infinite precision in bounded space. Clearly no Machine can print out all of Pi, because there are infinitely many digits. What we can do instead is provide a machine which reads a number, N, and prints out Pi to N digits - for any N.

: Or, on the other hand, we could generate a machine which prints out 'all' the digits of Pi, but which doesn't halt. I doubt that it makes much difference whether we define "a program that prints Pi" as the machine that accepts N as input and prints the first N digits of Pi then halts, or the machine that never halts and just keeps printing out digits of Pi until you pull the plug. I lean toward the latter simply because the state machine is somewhat easier to design.
: Nono. The first idea here was correct. To formalize the suggestion of the previous paragraph, "A program which prints a number is defined as a program which never outputs anything except the digits of that number, in sequence, and does not halt as long as digits remain that it has not printed." What if I write a program which prints the first 500 digits of Pi - suppose that it has them hardcoded - and then goes into an infinite loop of doing nothing? This meets that definition. Saying "X will be done, forever" doesn't work too well; that's why limits are defined in the "any precision one might request, can be provided" method. A workable definition is, "A program which prints a number is defined as a program which accepts a quantity N, prints the first N digits of that number and nothing else, and halts." --DanielKnapp

The number of states we need to do this will depend on N - which means no Finite State Machine will suffice for all N. In general, we'll need a Turing Machine. And since any Turing Machine can be emulated by some canonical Universal Turing Machine, we might as well define our machines to be programs for UTMs. -- DaveHarris Agreed. -- MichaelChermside

"A program that counts an arbitrary number of parenthesis pairs in some sentence" is often given as an example of the need for Turing Machines. In the case of computing pi, either the input is infinite or the output is not pi; 'pi to the nth digit' is not pi. You only need to bring in Turing Machines if you're considering input of infinite complexity and saying "takes any input" is just another way of saying that it can take input of infinite complexity. If you're talking about a class of inputs of ever increasing complexity, what's to stop you from just taking a class of Finite State Machines of matching complexity? Nobody ever said that it has to be one machine that can handle any program. Using TMs allows sneaking infinity through the back door; it doesn't seem like the use of TMs is justified to me; it's simpler but it also leads to mistakes getting unnoticed. In any case, there seems to be a lot of sleight of hand done with infinity on this page and when you play with magic, most of the answers you get are gonna be wrong. Unless you're in Las Vegas. -- rk

Matching parenthsis can be done with a Push-Down Automaton. It doesn't need a Turing Machine.

Pi - the whole of Pi - cannot be computed by a Turing Machine in the way you want. Sorry. A program which purported to write an infinite amount of data to the tape would never terminate, and we don't read the answer off the tape until after it has terminated, so it would effectively produce nothing. The best we can do is produce Pi to arbitrary precision.

The original theory/proof of this page does not require printing the digits of pi, in decimal or binary.

Writing the word "Pi" or the description "the ratio between the circumference of a circle and its diameter" would be sufficient to show that pi is not an UnknowableNumber?.

"Pi" is knowable -- it's well known, well defined, and in common usage. You can't "print" it in finite time in a decimal notation using a fixed base, but that's another issue. -- JeffGrigg

If you formalize the notion of a "specification", you probably end up with the notion of a program for a UniversalTuringMachine, and thus into issues of uncomputable numbers. [Not quite - a single uncomputable number is easy to define finitely (eg., one that solves the halting problem).]