You are not logged in.
#1 2005-11-17 07:07:07
- kylekatarn
- Power Member
Offline
Theory of Computation - Prove this!
Try to proof (or find a counter-example) the following statement:
If a problem can be solved in a pure recursive way, does this implies that an iterative solution also exists?
...This is something that came to my mind today during a lesson - Immediately called it the R-I conjecture
Last edited by kylekatarn (2005-11-17 07:13:52)
#2 2005-11-17 08:23:53
- MathsIsFun
- Administrator
Offline
Re: Theory of Computation - Prove this!
In programming the assumption is "yes", but I don't know for sure.
For the purpose of discussion, here are example of each method (NOT written for computer efficiency!)
Task: You want to reverse the order of letters, so that "fred" becomes "derf"
Iterative Approach
reverse(s) {
for (i=length(s), i>0, i--) { // go backwards through s
snew = snew & mid(s,i,1); // extract the letter at that spot
}
return( snew );
}
Recursive Approach
reverse(s) {
if (length(s) > 1) {
// split s into last character and the rest
slast = right(s,1);
sleft = left(s,length(s)-1)
return ( slast & reverse(sleft) ); // then call this function again with shorter s
} else {
return( s );
}
}
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
#3 2005-11-17 12:04:31
- kylekatarn
- Power Member
Offline
Re: Theory of Computation - Prove this!
Another example where my 'conjecture' works
#4 2006-01-01 00:31:47
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
I don't think so.
IPBLE: Increasing Performance By Lowering Expectations.
#5 2006-01-01 00:33:04
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
I'll find a counter-example
IPBLE: Increasing Performance By Lowering Expectations.
#6 2006-01-01 00:35:40
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
Try to calculate
with iterative approach!
Last edited by krassi_holmz (2006-01-01 00:38:22)
IPBLE: Increasing Performance By Lowering Expectations.
#7 2006-01-01 01:05:35
- kylekatarn
- Power Member
Offline
Re: Theory of Computation - Prove this!
What's wrong?
That is computable in a finite number of steps: )
acc := 0
i:=1
while i<n
{
acc:=acc+1/i^k
i:=i+1
}
in the end, return acc
//Edit: corrected the variable that was being incremented
Last edited by kylekatarn (2006-01-01 13:13:12)
#8 2006-01-01 12:19:26
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
Oh,so "iterative" meant this?
Then...
IPBLE: Increasing Performance By Lowering Expectations.
#9 2006-01-01 12:20:59
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
Then R-I conjecture must be true.
IPBLE: Increasing Performance By Lowering Expectations.
#10 2006-01-01 12:28:14
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
First we must define what are the differences between the Iterative and Recursive approach.
IPBLE: Increasing Performance By Lowering Expectations.
#11 2006-01-01 12:30:56
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
kylekatarn wrote:
What's wrong?
That is computable in a finite number of steps: )
acc := 0
k:=1
while i<n
{
acc:=acc+1/i^k
k:=k+1
}
in the end, return acc
You have forgotten one line:
while i<n
{
acc:=acc+1/i^k
k:=k+1
i:=i+1
}
IPBLE: Increasing Performance By Lowering Expectations.
#12 2006-01-01 12:34:23
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
Recursive:
Let use this:
a[i]=F[a[1],a[2],...,a[i-1]] depends of a[1..(i-1)]
We must fund iteractive approach.
IPBLE: Increasing Performance By Lowering Expectations.
#13 2006-01-01 12:41:30
- krassi_holmz
- Real Member
Offline
Re: Theory of Computation - Prove this!
a[1]=const
a[2]=F[a[1]]
a[3]=F[a[1],a[2]]
a[4]=F[a[1],a[2],a[3]]
IPBLE: Increasing Performance By Lowering Expectations.