Countability: Philosophy Forums

Countability
Effective Procedure

Page: 1 2

Countability

kingoftsr
Aspirant

Usergroup: Members
Joined: Oct 25, 2009

Total Topics: 21
Total Posts: 40

Posted 02/06/10 - 11:49 AM: Subject: Countability	#1
So any effective procedure (i.e. automatic/mechanical algorithm that terminates in a finite time) must be able to be written by a finite string of sentences in some language. Give an argument that the set of effective procedures is countable.. would appreciate any help thanks

Timothy
Robo-Procrastinator

Usergroup: Moderators
Joined: Dec 18, 2004
Location: Grad School

Total Topics: 91
Total Posts: 2313

Posted 02/06/10 - 12:22 PM:	#2
A set is countable iff it is either finite or denumerable. A set is denumerable if there's a 1-1 correspondence between it and the set of the natural numbers N If the set of effective methods were uncountable, what would happen?
Passed with Honors the Turing Test. Tendency to Halt.

kingoftsr
Aspirant

Usergroup: Members
Joined: Oct 25, 2009

Total Topics: 21
Total Posts: 40

Posted 02/06/10 - 01:47 PM:	#3
If the set of effective methods were uncountable then there would be no one to one mapping to the set of natural numbers. I just don't see how I'm meant to use the fact I'm given (that any effective method must be able to be written by a finite string of sentences) to prove this.. Thanks for your help!

Jean Francoise
Protege of Being

Usergroup: Members
Joined: Feb 04, 2009

Total Topics: 11
Total Posts: 180

Posted 02/07/10 - 04:48 AM:	#4
Seems that Timothy already gave you a sufficient hint. Here's another one which is more like a sketch of the proof: An algorithm (effective procedure) proceeds in n steps, before it halts i.e. spits out an answer on the (n+1)th step. Hence the algorithm must contain an n finite number of steps, otherwise it would never halt (infinite loop of some sort). So if each algorithm is finite, take the longest one L which contains all possible n steps. The power set of L is the set of all possible algorithms, which is also finite. i.e \|P(L)\| = 2^\|L\| , but \|L\| is finite, so 2^\|L\| is also finite QED Correction: This is not actually the precise number of algorithms, since in a computational process order is relevant, so for each element x of P(L) we count the number of n permutations (where n=\|x\|). So for each x we have \|x\|^\|x\| as the number of all of its intrinsic length permutations. For each such x element of P(L), \|x\|^\|x\| is finite. Next we sum all of those, which is also finite. Now this last sum is the number of all algorithms that halt i.e. sum of all effective procedures. Edited by Jean Francoise on 02/07/10 - 06:50 AM
Emptiness whispers in riddles.

MoeBlee
aka I. Kabruob

Usergroup: Members
Joined: May 19, 2005

Total Topics: 8
Total Posts: 1299

Posted 02/08/10 - 11:45 AM:	#5
kingoftsr wrote: So any effective procedure (i.e. automatic/mechanical algorithm that terminates in a finite time) must be able to be written by a finite string of sentences in some language. Give an argument that the set of effective procedures is countable. The key points are: The language is countable (has only countably many symbols). Each algorithm is coded by a finite string of symbols from said countable language. The set of finite strings in a countable language is a countable set. It is the last point that will have been proven either prior to this proof or in the course of this proof, depending on the context.

MoeBlee
aka I. Kabruob

Usergroup: Members
Joined: May 19, 2005

Total Topics: 8
Total Posts: 1299

Posted 02/08/10 - 11:47 AM:	#6
Jean Francoise wrote: So if each algorithm is finite, take the longest one Wrong. There is no longest one. Each algorithm is finite, but there is no finite upper bound on the lengths of algorithms. There are algorithms of EVERY finite length, so there is no longest algortithm.

kingoftsr
Aspirant

Usergroup: Members
Joined: Oct 25, 2009

Total Topics: 21
Total Posts: 40

Posted 02/08/10 - 03:38 PM:	#7
Timothy wrote: A set is countable iff it is either finite or denumerable. A set is denumerable if there's a 1-1 correspondence between it and the set of the natural numbers N If the set of effective methods were uncountable, what would happen? If it were uncountable, there would be no 1-1 correspondence between the set of effective methods and the set of natural numbers..but I don't see how this leads to a contradiction..? Thanks

kingoftsr
Aspirant

Usergroup: Members
Joined: Oct 25, 2009

Total Topics: 21
Total Posts: 40

Posted 02/08/10 - 03:40 PM:	#8
MoeBlee wrote: The key points are: The language is countable (has only countably many symbols). Each algorithm is coded by a finite string of symbols from said countable language. The set of finite strings in a countable language is a countable set. It is the last point that will have been proven either prior to this proof or in the course of this proof, depending on the context. Thanks, but all you seem to have done is re-articulate the question. My question is how this proof is to be carried out! thanks

MoeBlee
aka I. Kabruob

Usergroup: Members
Joined: May 19, 2005

Total Topics: 8
Total Posts: 1299

Posted 02/08/10 - 04:03 PM:	#9
kingoftsr wrote: Thanks, but all you seem to have done is re-articulate the question. What I did was give an outline that points to where the meat of the proof is: Showing that the set of finite strings on a countable alphabet is countable. There are different ways of showing that. One way is to use the fundamental theorem of arithmetic. First, we have the alphabet 1-1 with the set of natural numbers. So each symbol is mapped to a natural number. So for any finite string of symbols, match it to the number whose prime factorization has the exponents as in the finite string. For example, for the finite string that is: the 8th symbol followed by the 3rd symbol followed by the fifteenth symbol, we map to [here '' stands for multiplication and '^' stands for exponenitation]: 2^8 3^3 * 5^15 And there are other methods, though any method is going to depend on previously proven theorems. It's a question of what you considered previously proven in your studies.

Jean Francoise
Protege of Being

Usergroup: Members
Joined: Feb 04, 2009

Total Topics: 11
Total Posts: 180

Posted 02/08/10 - 05:35 PM:	#10
MoeBlee wrote: Wrong. There is no longest one. Each algorithm is finite, but there is no finite upper bound on the lengths of algorithms. There are algorithms of EVERY finite length, so there is no longest algortithm. I stand corrected. I fumbled "arbitrarily long" with "finite". Edited by Jean Francoise on 02/08/10 - 06:09 PM
Emptiness whispers in riddles.

Page: 1 2

Sorry, you don't have permission to post. Log in, or register if you haven't yet.