Problem 623

[hexadoodle]

I think I mostly understand this...
Why is (Lx.(Lx.x)) not listed as a possibility in the table?
Would ((Lx.x)(Lx.x)) be alpha-equivalent to ((Lx.x)(Ly.y))?

[traxex]

Why is (Lx.(Lx.x)) not listed as a possibility in the table?

It's alpha-equivalent to (Lx.(Ly.y)).

Would ((Lx.x)(Lx.x)) be alpha-equivalent to ((Lx.x)(Ly.y))?

Yes.

[hexadoodle]

Why is (Lx.(Lx.x)) not listed as a possibility in the table?

It's alpha-equivalent to (Lx.(Ly.y)).

Hmm. And yet the problem says "(λx.(λy.(xy))) and (λx.(λx.(xx))) are not α-equivalent." To me it seems like a term with two abstractions, each of a different variable, would be considered distinct from a version of the same "structure" in which the variables are all the same. I'm having trouble identifying where I'm going wrong.

Also, is an expression with nested abstractions using the same variable (such as (Lx.(Lx.x)) ) even valid at all? (Disregarding the fact that it's alpha-equivalent to something else valid.)

[traxex]

Scoping in lambda calculus works very much like in C-family languages.

Consider these two lines of pseudo-code:

Code: Select all

{ string x = "foo"; { string y = "bar"; print(x, y); } }
{ string x = "foo"; { string x = "bar"; print(x, x); } }

They are not equivalent, because the first one prints "foo bar" and the second one prints "bar bar".

Now consider these:

Code: Select all

{ string x = "foo"; { string y = "bar"; print(y, y); } }
{ string x = "foo"; { string x = "bar"; print(x, x); } }

Both lines print "bar bar", so they are equivalent. Hiding the outer variable does not change the meaning in this case.

The lambda term (Lx.(Lx.x)) is valid, just like hiding variables in C is allowed.

[Sardaai]

The description of variables as "non-empty alphabetical strings" implies that variables can be more than one letter, but this could create some syntactic ambiguity. E.g. in "(λa.(λc.(λab.(λbc.(abc)))))", the "(abc)" could be interpreted as the application of "ab" to "c", or as the application of "a" to "bc".

This isn't relevant at lower symbol caps, but it should become relevant when the cap is high enough that more than 26 symbols can be defined. How should we handle this? Should we assume that there are inherent delimiters around each variable name?

[traxex]

Should we assume that there are inherent delimiters around each variable name?

Yes, that is one way to put it. The $\Lambda(35)$ value given is also big enough to confirm that two adjacent variables do not cause ambiguity in parsing.

[jpaulson]

I share Sardaai's concern, and I don't think traxex's reply resolves the ambiguity (what is the interpretation of Sardaai's example lambda term?)

Also, are variables allowed to contain uppercase characters? (i.e. I find "alphabetical string" ambiguous)

[MuthuVeerappanR]

Scoping in lambda calculus works very much like in C-family languages.

Consider these two lines of pseudo-code:

Code: Select all

{ string x = "foo"; { string y = "bar"; print(x, y); } }
{ string x = "foo"; { string x = "bar"; print(x, x); } }

They are not equivalent, because the first one prints "foo bar" and the second one prints "bar bar".

Now consider these:

Code: Select all

{ string x = "foo"; { string y = "bar"; print(y, y); } }
{ string x = "foo"; { string x = "bar"; print(x, x); } }

Both lines print "bar bar", so they are equivalent. Hiding the outer variable does not change the meaning in this case.

The lambda term (Lx.(Lx.x)) is valid, just like hiding variables in C is allowed.

Can you please give the lambda-calculus representation for each of the four lines of code?

[mclo]

@Sardaai/jpaulson
For the purpose of this problem, variables are considered to be single symbols/tokens, at the same level of parenthesis/dots/etc. The syntactic representation of a $\lambda$-term is a sequence of symbols, not characters. Hence the ambiguity $(\lambda ab.(\lambda c. (abc)))$ does not really arise because the description of the term should be the symbol sequence

"(","$\lambda$","ab",".","(","$\lambda$","c",".","(","ab","c",")",")",")"

Alternatively, one way to achieve the same result with character strings is to consider that there is a delimiting space between the members of an application: $(\lambda ab. (\lambda c. (ab\;\!c)))$

Finally, the precise format of alphabetical strings (lowercase, uppercase, CamelCase, snake_case, etc...) does not matter since you can rename all variables to fit your favorite format.

[traxex]

Can you please give the lambda-calculus representation for each of the four lines of code?

They were meant to explain why $(\lambda x{.}(\lambda y{.}(xy)))$ and $(\lambda x{.}(\lambda x{.}(xx)))$ are not $\alpha$-equivalent, but $(\lambda x{.}(\lambda y{.}(yy)))$ and $(\lambda x{.}(\lambda x{.}(xx)))$ are.

But perhaps I only caused more confusion.

[hexadoodle]

Can you please give the lambda-calculus representation for each of the four lines of code?

They were meant to explain why $(\lambda x{.}(\lambda y{.}(xy)))$ and $(\lambda x{.}(\lambda x{.}(xx)))$ are not $\alpha$-equivalent, but $(\lambda x{.}(\lambda y{.}(yy)))$ and $(\lambda x{.}(\lambda x{.}(xx)))$ are.

But perhaps I only caused more confusion.

Forgot to say, your explanation helped me understand the problem. Thanks!

[Sardaai]

The syntactic representation of a $\lambda$-term is a sequence of symbols, not characters.

Hm... In many contexts, "symbols" and "characters" have equivalent meaning, which is why I and others were confused. I feel like this could be made clearer in the problem description.

Also, $\Lambda(n)$ is described as the number of distinct $\alpha$-equivalent lambda-terms that can be written using at most $n$ symbols, but it's actually the number of such symbols which are closed. Even though this is obvious from the sample values of $\Lambda$, the description should still be corrected in the problem.

[RobertStanforth]

Also, $\Lambda(n)$ is described as the number of distinct $\alpha$-equivalent lambda-terms that can be written using at most $n$ symbols, but it's actually the number of such symbols which are closed.

Thank you for pointing that out, Sardaai. The description has now been updated to ask for closed lambda-terms.

[jpaulson]

@Sardaai/jpaulson
For the purpose of this problem, variables are considered to be single symbols/tokens, at the same level of parenthesis/dots/etc. The syntactic representation of a $\lambda$-term is a sequence of symbols, not characters. Hence the ambiguity $(\lambda ab.(\lambda c. (abc)))$ does not really arise because the description of the term should be the symbol sequence

"(","$\lambda$","ab",".","(","$\lambda$","c",".","(","ab","c",")",")",")"

Alternatively, one way to achieve the same result with character strings is to consider that there is a delimiting space between the members of an application: $(\lambda ab. (\lambda c. (ab\;\!c)))$

Finally, the precise format of alphabetical strings (lowercase, uppercase, CamelCase, snake_case, etc...) does not matter since you can rename all variables to fit your favorite format.

I missed that variables were atomic "symbols". Thank you!

[jpaulson]

Scoping in lambda calculus works very much like in C-family languages.

Consider these two lines of pseudo-code:

Code: Select all

{ string x = "foo"; { string y = "bar"; print(x, y); } }
{ string x = "foo"; { string x = "bar"; print(x, x); } }

They are not equivalent, because the first one prints "foo bar" and the second one prints "bar bar".

Now consider these:

Code: Select all

{ string x = "foo"; { string y = "bar"; print(y, y); } }
{ string x = "foo"; { string x = "bar"; print(x, x); } }

Both lines print "bar bar", so they are equivalent. Hiding the outer variable does not change the meaning in this case.

The lambda term (Lx.(Lx.x)) is valid, just like hiding variables in C is allowed.

Can you please give the lambda-calculus representation for each of the four lines of code?

Roughly speaking: (lambda calculus doesn't have "print" or builtin strings, but this is the equivalent scoping):
(Lfoo.(Lbar.(foo bar)))
(Lfoo.(Lbar.(bar bar)))
(Lfoo.(Lbar.(bar bar)))
(Lfoo.(Lbar.(bar bar)))

A more exact translation of the first line would be (assuming we have a "print" function defined elsewhere):
((Lx.(Ly.((print x) y))) "foo") "bar"

[MuthuVeerappanR]

Thank you all.. Solved it...

For someone who didn't study computer science, the whole problem seemed very convoluted but fortunately the structure of the problem was quite simple..

Expand

One more thing.. Should the number of solvers be hidden until we solve a problem? At least recently for me, I'm taking hints from the rate at which the problem is solved.. Problem 623 (View Problem) and Problem 619 (View Problem) are two problem I can quote which I thought were hard for me but the number of solvers hinted me that there is a much easier way.. Eventually I solved both which I don't think I would've had I not been aware of number.

Just a thought...

EDIT:ed after seeing the point in hk's reply. I'm not saying it should be hidden all the time. I tried suggesting hiding the number of solvers until a particular user have solved it. But PE being a Educational site rather than a competitive site refutes everything. Thanks.

[hk]

Thank you all.. Solved it...

For someone who didn't study computer science, the whole problem seemed very convoluted but fortunately the structure of the problem was quite simple..

One more thing.. Should the number of solvers be hidden until we solve a problem? At least recently for me, I'm taking hints from the rate at which the problem is solved.. Problem 623 (View Problem) and Problem 619 (View Problem) are two problem I can quote which I thought were hard for me but the number of solvers hinted me that there is a much easier way.. Eventually I solved both which I don't think I would've had I not been aware of number.

Just a thought...

First of all: your post is very much off-topic: this forum is meant for clarifications if you have trouble understanding a problem.
Secondly: Project Euler isn't in the first place a competitive environment but an educational one. I don't think your suggestion is helpful for the general Project Euler member: the solve count is a good measure which problems to try.
And even if it were mainly a competitive environment:
Knowledge of the times performed by your fellow competitors is also important with many sports, like e.g. skating.
I heard many of our medal winners at the games in PyeongChang (and we had a lot of them) for e.g. long track speed skating talk about the times that were reached by their competitors that had done the tasks before them.
I still see some of them sitting on the bench not daring to look what some of the later ones got for timings.

[RobertStanforth]

With regard to the earlier comments in this thread about characters versus symbols for variable names, the problem description has now been amended to specify that a variable is a single letter (drawn from an infinite alphabet). This does not change the answer but should avoid some confusion.
Thank you to those who pointed out the potential ambiguity.

[pjt33]

Also, $\Lambda(n)$ is described as the number of distinct $\alpha$-equivalent lambda-terms that can be written using at most $n$ symbols, but it's actually the number of such symbols which are closed.

Thank you for pointing that out, Sardaai. The description has now been updated to ask for closed lambda-terms.

It would improve the clarity of the question to also update the text before the table of the 20 closed lambda-terms which contribute to $\Lambda(15)$.