Difference between revisions of "2453: Excel Lambda"

Explain xkcd: It's 'cause you're dumb.
Jump to: navigation, search
(Transcript: typo)
(Explanation)
Line 13: Line 13:
  
 
A classical [https://en.wikipedia.org/wiki/Turing_machine Turing machine] uses an infinitely long strip of tape as its memory. The large column acts as the "tape".
 
A classical [https://en.wikipedia.org/wiki/Turing_machine Turing machine] uses an infinitely long strip of tape as its memory. The large column acts as the "tape".
 +
 +
The [https://en.wikipedia.org/wiki/Church-Turing_thesis Church-Turing_thesis] is a hypothesis says that a function can be computed by executing a series of instructions if and only if that function is computable by a Turing Machine. All ways of computing are therefor "equally wrong" since, according to this thesis, they can all be translated to a Turing Machine.
  
 
The [https://en.wikipedia.org/wiki/Halting_problem halting problem] is a counter-example that proves that you cannot predict whether Turing machines will halt.
 
The [https://en.wikipedia.org/wiki/Halting_problem halting problem] is a counter-example that proves that you cannot predict whether Turing machines will halt.

Revision as of 05:59, 22 April 2021

Excel Lambda
Extremely rude how Turing's later formulations of the halting problem called me out by name specifically.
Title text: Extremely rude how Turing's later formulations of the halting problem called me out by name specifically.

Explanation

Ambox notice.png This explanation may be incomplete or incorrect: Created by a SPREADSHEET. Please mention here why this explanation isn't complete. Do NOT delete this tag too soon.
If you can address this issue, please edit the page! Thanks.

Cueball is computing and Ponytail has opinions.

A classical Turing machine uses an infinitely long strip of tape as its memory. The large column acts as the "tape".

The Church-Turing_thesis is a hypothesis says that a function can be computed by executing a series of instructions if and only if that function is computable by a Turing Machine. All ways of computing are therefor "equally wrong" since, according to this thesis, they can all be translated to a Turing Machine.

The halting problem is a counter-example that proves that you cannot predict whether Turing machines will halt.

Transcript

Ambox notice.png This transcript is incomplete. Please help editing it! Thanks.
[In a narrow panel, Ponytail is walking in from the left, looking down at her phone]
Ponytail: Oh cool, Excel is adding a lambda function, so you can recursively define functions.
[Ponytail, holding her phone to her side, talks to Cueball, who is working on a laptop. He has turned around to face her.]
Cueball: Seems unnecessary.
Cueball: When I need to do arbitrary computation, I just add a giant block of columns to the side of my sheet and have a Turing machine traverse down it.
[Ponytail still talking to Cueball, who has resumed working on his laptop.]
Ponytail: I think you're doing computing wrong.
Cueball: The Church-Turing thesis says that all ways of computing are equally wrong.
[Ponytail talking to Cueball, who has his finger raised in the air. Cueball's head has a visible sketch layer which has not been erased.]
Ponytail: I think if Turing saw your spreadsheets, he'd change his mind.
Cueball: He can ask me to stop making them, but not prove whether I will!


comment.png add a comment! ⋅ comment.png add a topic (use sparingly)! ⋅ Icons-mini-action refresh blue.gif refresh comments!

Discussion

Another ghost cueball comic! You can see it in the last panel. 108.162.216.54 06:03, 22 April 2021 (UTC)

Is that something that has happened before? First time noticing it. Is it just a remnant of the sketching? Of doest it mean something? 162.158.93.213 13:21, 22 April 2021 (UTC)
It has happened, and is now mentioned in the trivia section. --Kynde (talk) 16:43, 23 April 2021 (UTC)
Randall seems to have update the comic to remove the ghost head. Someone should update it here too. (I don't know how). DrPumpkinz (talk) 00:07, 23 April 2021 (UTC)

Someone needs to add an explanation of the Lambda, and possibly how Excel is implementing it. (I suppose it would immediately be useful for cutting down common re-use within a formula line, though =IF(ISERR(FIND(":",A1)),A1,RIGHT(A1,LEN(A1)-FIND(":",A1))) is a trivial repeat of the FIND, once to check, then again to do, I often need to do far more nested things, check for being a value, repeat the FIND to deal with the LEFT, etc.) But it has the smell of being effectively a Macro in this instance. Which already seems to me to be the only way to run a proper Turing Machine in an Excel column without hitting Circular Reference issues.


Would it be a stretch to say that Turing's inability to prove if Cueball will stop is actually equivalent to the halting problem, except it is for Cueball and not an arbitrary Turing machine? I thought that was pretty funny. xTheBHox (talk) 11:30, 22 April 2021 (UTC)


Microsoft themselves claim that the addition of LAMBDA makes Excel turing-comlpete (see here: https://techcommunity.microsoft.com/t5/excel-blog/announcing-lambda-turn-excel-formulas-into-custom-functions/ba-p/1925546). Based on this comic, I would argue that it already was... 162.158.159.36 12:55, 22 April 2021 (UTC)

Someone has already made Conway's game of life in excel (http://dailydoseofexcel.com/archives/2011/04/06/conways-game-of-life-simulation-in-excel) and game of life has been shown to be Turing complete. Kvarts314 (talk) 13:28, 22 April 2021 (UTC)
Since Excel has a way to store and do math on numbers, and also a way to 'point' to a certain cell, it is Turing-complete. A lambda function is not necessary for Turing-completeness (e.x. a turing machine does not have one.) 162.158.255.250 15:14, 22 April 2021 (UTC)

it should probably be mentioned that the number of excel rows is emphatically *not* infinite, so only simple turing machines could be implemented this way. 162.158.93.15 17:20, 22 April 2021 (UTC)

In fact, it technically isn't Turing complete, as it has only a finite amount of data. It might be a finite-state-machine or the like, though. --108.162.219.218 20:22, 22 April 2021 (UTC)
Turing completeness is a qualilty of a model of computing, not a particular physical implementation. There's no inherent limit to the size of a spreadsheet, so it's as Turing-complete as any programming language. Any actual implementation of a Turing Machine only has a finite tape, not an infinite tape like the theoretical model. Barmar (talk) 15:39, 23 April 2021 (UTC)
It may be worth citing this work. https://gotocon.com/amsterdam-2016/presentation/Pure%20Functional%20Programming%20in%20Excel Noehp (talk) 00:02, 23 April 2021 (UTC)

Zerothly, why is almost everyone here using weird 'indents', or maybe new-contributor-starts-here methods, in this article's Talk comments? Is this some lambdaesque in-joke being carried in here from some script/code dialect I'm not aware of? Primarily, though, I just wanted to say that the (external) explanations of how Lambda works in Python look a lot to me like a nuanced Eval-like process, rather than a typical Anonymous Function that becomes sequestered away as a code-chunk at the end of a loose-pointer, internally. Python's one of the languages I've not yet bothered to learn to write (just sufficiently understand to get the gist and flow), so maybe I'm reading the Lies-To-Children explanations for n00bs. Should we get some other languages represented here, either within the C-family or off into the clans of code that might have an even more interesting implementation? Nothing too esoteric, but a distinct grammar difference would be an interesting comparison.162.158.159.104 11:22, 23 April 2021 (UTC)

Fixed the indents. PoolloverNathan[stalk the blue seas]UTSc 14:01, 21 May 2021 (UTC)

Now if only someone would find examples of creative loop variable abuse (I guess that'd be optimal solutions in lots of Code Golf or Code Olympics problems) that demonstrate the imperative style of code to its full glory. The corresponding solution in λ code is probably rife with applicative functors and monads i.e. ugly and awkward to anyone not familiar with these concepts. The Python example here merely looks like anonymous function sprinkled into an imperative style so not very helpful. 172.70.98.89 04:15, 18 October 2021 (UTC)

I removed a lot of interesting but irrelevant material about the details of lambda functions and how they're implemented in Python, with apologies to everyone who spent time crafting it, since this comic is about Excel. If anyone has time to explain how lambda functions are implemented in Excel formulas specifically, please feel free to add. Jkshapiro (talk) 15:04, 10 April 2022 (UTC)

Also I wasn't sure about the phrase "fundamental mathematical structure", so left it in. Usually when people talk about mathematical structures they're referring to things like rings and fields, and I don't know what a fundamental mathematical structure even is, but that could well be my own ignorance showing. Jkshapiro (talk) 15:04, 10 April 2022 (UTC)