Hello, we are three students doing an assignment (around 60-100 pages). We are struggling with the synopsis and we would really appreciate if someone here...
... Your synopsis seems both adequate and unexceptionable. My personal view, and experience, is that your assignment is likely to disproportionately influence,...
Hello, thank you very much for your reply. We will try to get as many of the papers that you refereced as possible. It's always nice to get some perspective on...
Definition Computable Number: "A number which can be computed to any number of digits desired by a Turing machine." The computable numbers are countable since...
... You need an algorithm to enumerate the computable numbers, which means an algorithm to enumerate these Turing machines that for each input n, terminate...
... How so? I think that you're thinking of this 'Given an arbitrary TM, does it halt with a number on its tape' but it seems that we're talking about ...
... How are you going to enumerate the computable numbers. by enumerating the turing machines ? In that case it is not correct to assume that you can compute...
Hello, Thanks for the reply. You have shown that a TM that enumerates every possible TM in lexicographic order and executes that TM will never halt. I didn't...
Hi, You were asking about computable numbers... ... Okay up to this point. You've used diagonalization to define a new number which is evidently not...
Kurt, I agree that the number is not computable. But the reason that it is not computable is that IF it WERE computable, then there'd be a computable number...
Hi, ... intimidation ... ... compute the ... Proof by intimidation? Hmmm, not sure what that is. The proof that the number you defined is uncomputable is that...
My god, did you even read my last email? You just repeated what I said and then explained how I don't understand it. The proof that the diag-comp is...
... Okay... I'll try to describe how to prove that NO algorithm can compute your number: 1) As you pointed out, the set of all computable numbers is ...
Let me rephrase your definition of computable numbers: Defn: A real number $r$ is computable if there exists a recursive language $L \subseteq \{1\}^*$ and a...
... The above proof works fine for languages but one has to be carefull when dealing with numbers. This is because a number can have more than one binary...
... KS == Perhaps, nothing! Here is another way of looking at it. Standard interpretations of Cantor's diagonal argument - of which the Halting argument you...
Hello, I only have one question. I am in a bit of hurry so I only skimmed through your arguments. My appolgies if what I say is already answered (but I have a...
What do you mean by 'instantaneous tape description'? If you mean the TM will halt if it sees a previously encountered configuration: Imagine that this TM...
I must say, even though you're specifics are not sound - I agree that 'resolving' Richard's Paradox by saying that 'a string of characters defines a real...
... From: Kevin L Stern To: comp-sci-theory@yahoogroups.com Sent: Sunday, March 14, 2004 9:13 AM Subject: Re: [comp-sci-theory] Re: Computable Number What do...
That was my point with the TM below, Michael ... How would the algorithm that looks for repeated configs detect the difference between a 1 being down the tape...
... Piotr === No, of course not. The argument that I gave was, essentially, given by Turing in his 1936 paper "On computable numbers...", in the section titled...
... Kevin ==== Sorry. I was being pedantic. The definition I had in mind was from Elliott Mendelson, Introduction to Mathematical Logic, 1964ed., Van ...
Please don't apologize ... I had never heard the term "instantaneous tape description" ... I see what you meant now. Either way, I thought you were claiming...
... From: Kevin L Stern To: comp-sci-theory@yahoogroups.com Sent: Sunday, March 14, 2004 8:18 PM Subject: Re: [comp-sci-theory] Re: Computable Number That was...
... Apologies, I was wrong. I thought of a config as being the current state along with the currently scanned symbol. In light of recent understandings, I...
I think that you two have lost perspective and need to refocus on what's really important, that is Computer Science Theory. Sometimes our intelligence levels...
... From: Kevin L Stern To: comp-sci-theory@yahoogroups.com Sent: Monday, March 15, 2004 10:37 PM Subject: Re: [comp-sci-theory] Re: Computable Number ... ...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
