Mathematics desk
< February 27	<< Jan \| February \| Mar >>	March 1 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 28

Decidability question

Let S be an infinite set of strings over the alphabet {0,1} and S_k denote the strings in S that have exactly k 1's. Let's say I can prove that for every k, there is a Turing machine T(k) that recognizes exactly the set S_k. The proof might be nonconstructive--that is, I can't necessarily prove that any specific machine M recognizes S_k; I can only prove the existence of such an M. 1) Is it still appropriate to say that each S_k is a decidable set? 2) Is it appropriate at all to say that S itself is a decidable set? 3) is it pretty clear that S is not necessarily a recursive set? Question is motivated by this article which I do not yet understand. Thanks. 76.195.10.34 (talk) 19:18, 28 February 2009 (UTC)[reply]

(1) Yes. A language is decidable if there exists a Turing machine that recognizes that language. (2) No. There exist undecideable languages S such that each

S_{k}

is decideable (though note that it is not possible to explicitly construct Turing machines for all k). (3) Yes. If I understand correctly, "recursive set" is synonymous with "decidable language" (it looks like the former term is used when talking about subsets of natural numbers, and the latter term is used when talking about strings over an alphabet), in which case 2 and 3 are asking the same thing (but negated). Eric. 131.215.158.184 (talk) 21:55, 28 February 2009 (UTC)[reply]

How do you define string here? Are they of infinite length or is there a third token not {0,1} indicating end of string? -- SGBailey (talk) 22:28, 28 February 2009 (UTC)[reply]

Thanks. I will have to read the linked article more carefully to figure out what the author means by decidable then. I first thought he was describing something like S in my example and was using the term "decidable" in an unusual way, but maybe he has something different in mind. 76.195.10.34 (talk) 22:30, 28 February 2009 (UTC)[reply]

I've only given it a quick glance, but that article does indeed seem to be using 'decidable' in a nonstandard fashion; indeed, the proper meaning of 'decidable' is what the article's about. Algebraist 22:36, 28 February 2009 (UTC)[reply]

To me, all strings are finite. The convention I follow is that there exists a "blank" symbol: the input of the Turing machine is guaranteed to be finite and contain no blanks (and everything else on the tape is initially the blank symbol). Eric. 131.215.158.184 (talk) 07:30, 1 March 2009 (UTC)[reply]

Yes, finite strings of course. Delimited by a blank square, or a coded length or whatever. I guess I'm ok with "recursive" and "decidable" meaning two different things: recursive is the usual mathematical term, while "decidable" is less well defined, coming from Hilbert's Entscheidungsproblem (decision problem) which predates recursion theory, Turing machines, and so forth. For example, if T(k)'s existence in the example above is only proved nonconstructively and the number of states in T(k) can be shown to grow faster than any computable function of k, it's pretty difficult to say with a straight face that there's a decision procedure for S_k that would have satisfied Hilbert. Anyway thanks for the responses and I'll keep trying to read that paper. 76.195.10.34 (talk) 10:05, 2 March 2009 (UTC)[reply]

Free 3D graphing Program

I need a 3d graphing program for my personal computer that can graph multiple functions. Does anyone know of a good free one? --omnipotence407 (talk) 23:46, 28 February 2009 (UTC)[reply]

gnuplot ? 207.241.239.70 (talk) 00:10, 1 March 2009 (UTC)[reply]

We have many articles on such programs in Category:Free 3D graphics software, but I am not familiar with any of them. JackSchmidt (talk) 00:42, 1 March 2009 (UTC)[reply]

I use graphing calculator on my PC running under PEAR( Macintosh emulation ).

There is a PC equlivent, its good, but doesn't have a love of the advanced functions.

you can also try this: [[1]] I dont run java...

Let me know what happens LL --67.174.157.126 (talk) 21:50, 2 March 2009 (UTC)[reply]

Factorial with a big twist

Finding the number of possible combinations of things is incredibly easy. For instance 12! = 479,001,16. However let’s say I wanted to actually find every order in which twelve numbers could be placed. What formula could I use? --S.dedalus (talk) 23:47, 28 February 2009 (UTC)[reply]

Those are not combinations; those are permutations. Michael Hardy (talk) 21:56, 3 March 2009 (UTC)[reply]

You wouldn't use a formula, you would just list them. Choose some methodical order and get on with it. "1,2,3,4,5,6,7,8,9,10,11,12" is probably a good place to start, then I would fix the first 10 numbers and list every permutation of the last 2 (there is only one m ore!), then fix the first 9 numbers, change the 10th, and list every permutation again, then fix just the first 8 numbers, list every permutation, and so on and so on. Obviously, you will never actually be able to list them all for 12, try with something smaller. Eg. for 3 you would go "1,2,3", then fix the 1 and change the rest: "1,3,2", then change the 1 to 2 and list the options: "2,1,3", "2,3,1" then change the 1 to a 3: "3,1,2", "3,2,1". And then you're done. For 4 you would do the same thing, just repeating it 4 times with difference 1st digits. --Tango (talk) 23:58, 28 February 2009 (UTC)[reply]

There are some algorithms and source code implementations at permutation#Algorithms to generate permutations. I believe the TAOCP has a fairly definitive discussion on the algorithms. JackSchmidt (talk) 00:40, 1 March 2009 (UTC)[reply]

Am I misunderstanding the permutation#Algorithms to generate permutations Unordered generation algorithm, or is k misused? The way it is written, k is modified on each loop. I would have expected k to remain as initally input and a temporary variable to be needed. IE m:= k/ (j-1); swap s[(m mod j)+ 1] with s[j]; ? -- SGBailey (talk) 09:13, 1 March 2009 (UTC)[reply]

It was correct (see factorial base). I rewrote it a bit. -- BenRG (talk) 12:24, 1 March 2009 (UTC)[reply]

Get Knuth's The Art of Computer Programming volume 4 fascicle 4, which tells you about algorithms generating all permutations. (By the way, you've made a typo in the value of 12!, the correct value is 479,001,600.) – b_jonas 20:28, 5 March 2009 (UTC)[reply]