Turing Meets Paradoxes (History of Undecidability Part 3) - Computerphile

[@Ivo--]

Professor Brailsford is my favourite computerphile professor.

[@unvergebeneid]

I think he really got better at it. I had my problems with his first few videos but now he's quite enjoyable indeed.

[@georgedavis8831]

This series is a tour de force. I love how Prof Brailsford can weave together theory, practical detail and historical context. To give such a full picture of a problem as complex as undecidability in 40ish minutes of video is just amazing. Many many thanks!

[@edwardowen2]

Rumour has it if you feed this 3 part explanation back into Professor Brailsford, an even more meandering and entropic video explanation of undecidability is produced, it is not known whether this third iteration halts.

[@alvaronavarro4890]

I absolutely loved this series. It's wonderful to realize how fundamentally interconnected mathematics and computation are. It feels very fulfilling indeed.

[@NowhereManForever]

I think this channel has taught me more of the actual subject matter presented than any of Brady's other channels. And I have been a fan of Numberphile, Periodicvideos, and SixtySymbols for years. I had never been interested in programming or computer science much at all even after trying my hand at it, until I watched these videos. Then again, I am much more knowledgeable and interested in math and logic than I was when I last tried programming so that might have some of it.

[@OwenPrescott]

His voice would be perfect for audiobooks.

[@MrJosh6889]

Great series. Anyone interested in programming or computer science should watch this.

[@culwin]

I could listen to this guy all day

[@matthewq2365]

I love these undecidability and recursion segments! I wish Professor B was at my local Westminster college (Fulton MO.) Or if you ever speak here, I will be there!

[@glufull]

Thank you for this series, professor Brailsford!

[@garethreid1753]

This series may be my favourite thing on KZbin

[@Epoch11]

This is a wonderful series and I hope you continue these. I love paradoxes and puzzles in general. If you could create more videos like this it would be much appreciated. Anything dealing with the mysterious or unexpected is something I will definitely watch and show to others.

[@notforwantoftrying1]

Thanks for this lesson Prof, you are clearly a very learned man. I hope to have such an agile mind one day.

[@ThePeaceableKingdom]

Self referential problems are indeed interesting. (and treacherous!) So much so that they have permeated the wider culture outside academia under the rubric "meta"...

[@Sahanie]

Thank you so much for this series of videos! I really enjoyed Professor Brailsford's explanation of Undecidability.

[@amaraojiji]

Thank you! The best series in c/ph.

[@Alorand]

I would love to understand how this relates to Artificial Intelligence in the Singularity-like circumstances where they are analyzing, changing, and writing their own code. What is it about our human brains that allows that deep introspective, self referential, analysis - especially when dealing with questions of Morality? Fuzzy logic? The fact that reconstructing itself, and modifying how the neurons are connected is a basic aspect of how our brains function? Maybe it has something to do with how children mimic the actions of their parents, not understanding the reasons for why things are done a certain way, but doing it anyway, trusting that eventually they will be able to understand?

[@literallybiras]

Alorand It relates a lot, specially if AI are optimizing in therms of themselves instead of like optimizing the way they walk or the way they fly, in the case of drones who uses some Artificial Intelligence and feedback, in essence, trying to optimize themselves, their own code, otherwise would be decidable. From where we are now in understanding computers and the human brain, we can safely say that the moral problems that we've faced for so many years have something of undecidability in them, just like computers, they continue to do the calculations without producing results, more accurately without even knowing if they will ever "halt", if will ever find an answer. And we see just like the workarounds for the barber problem, some moral problems, when you presume some things like the intent or the circumstances of a person, you can justify his acts as being moral, even for killing or thieving, this is exactly the simplification that the professor talks and that prevents you for having an all encompassing moral answer for everything but can have for simpler versions of the problems, fundamentally there will be too many paradoxes. About the neurons, as far as I know they are the cells that do the least repairing in our body, and the repair itself its just biological, it has to have sugar and oxygen and be healthy in order to pass the electrical signal, it doesn't have any information in itself, and most of the time the brain deals with information that is plain simple, information wise, like processing images from the eye, sounds from the ear, smells, flavor, and others, usually the cortex is the part that do most of the functions that allowed us to have conscience and philosophy, etc, its the part that is not linked with body functions, so its power can be focused on "higher" problems, which other animals don't have even though some of them actually have bigger brains, its just that if you have so many senses you might need bigger brains and still no sign of conscience. So, if I would put my bets, I would say that computers will be better in evaluating itself, especially when they hit the exaflop mark 10^15, which the human brain falls, right now they are at the petaflop mark 10^12, they still would have to be wonderfully programmed with robust algorithms, but since they can do specific tasks, they will face this problem without the lens of emotion, or thoughts about mortality, or even Ego. I think the singularity already occur, we just don't have at the moment computers writing his own code, or even with permission to do so, they are producing results for the problems presented, its hard to see this when the best computer account for 1% of the human brain computer power, achieved by heavy parallelism of the cells, but search again in a few years, computers with 200% of human capacity, 1000%, 10000%, I can't even imagine what would be like, certainly we can call a Singularity at that point.

[@un2mensch]

Can't wait for the yacc episode!

[@DanielBeecham]

I agree!

[@najlos]

is it out yet?

[@hrnekbezucha]

Still waiting

[@bruinflight]

Fascinating!!!! Thank you Prof. for making all of these great videos; please do make more! I enjoy listening to you immensely! Best regards :0)

[@namvu4180]

i’d love to have this professor teach me theory of computation 😭😭

[@garethdean6382]

Before I watched this I was totally confident that every problem had a solution, but now.. I don't know, I'm still thinking it over. I'll tell you when I come to a conclusion.

[@MrBeiragua]

the answer is: Maybe no... Awesome!

[@darkmage07070777]

8:00 - I am both terrified and excited at the prospect of being shown an example of this.

[@naimulhaq9626]

An algorithm whose premises involve infinite axioms is decidable. Finite axioms lead to approximation and is undecidable.

[@redstonedreamer6896]

Isn't that the same as feeding the output of a not gate back into itself?

[@CreationTribe]

What then, if you should have a System A, designed specifically to effectively analyze a System B in the same sense that a System B cannot analyze itself without facing off with undecidability, could the System B then be capable of analyzing the System A in the same sense that the System A cannot analyze itself without falling into undecidability? In brief, could you circumvent the halting problem by designing yet another system that can both analyze a computer such that it can solve the halting problem as well as be analyzed by a computer such that any self-referential problems could be solved by conventional computers?

[@noddwyd]

I love Incompleteness! It's so stupid, and yet, it's right! There's always a broader system! It's exactly like the first cause problem in philosophy

[@DustinRodriguez1_0]

+noddwyd Well, the 'first cause' problem in philosophy is, in my opinion, a little easier. Having a 'first cause' relies on an ordering of events in time. Asking what happened 'before' time existed is simply an invalid question, since the definition of 'before' relies upon the existence of time to have any sense.

[@noddwyd]

Yet, to most people, that answer is a cop out. I get what you mean, though. It's an outside context thing.

[@LittlePeng9]

1:09 Not every - it has to be sufficiently strong to derive simple arithmetic truths, and it has to be sufficiently simple - if we take theory Th(N) of all arithmetic truths, then it's necessarilly complete, consistent and sound, however, it's extremely complicated theory.

[@769270865]

To halt or not to halt, that is the question

[@garfieldnate]

I eagerly await the YACC episode! Couldn't find proper info for that online anywhere.

[@AndreiZisu]

This would've made things so much easier last year.

[@FerroNeoBoron]

What Professor Brailsford, what do you think of Parsing Expression Grammars packrat parsers? What about ones without left-recursion and those with hacks to support it?

[@Linux567]

thanks for the knowledge.

[@NoahSpurrier]

The deeper dread about undecidability is that you can’t always prove something is undecidable. Professor Brailsford said that we found out that the parallel line hypothesis is undecidable, but have we actually done that? It may be undecidable, but have we actually proven that it is undecidable? I thought that problem was even more vexing. The Barber Paradox is different because the logical system leads to a paradox, so it’s plainly undecidable within that logical system. That’ seems like a weaker form of undecidability. At least we know it’s undecidable.

[@santerisatama5409]

Euclid's elementa has a kind of 'if-then' flavor, the propositions are dictated by the question and desired conclusion, what is necessary to prove that there are five platonic solids. Stephen Wolfram and his team have made a hypergraph study of of the proof structure of Elementa, which among other things they do, is very interesting development in computation theory. Hypergraphs are kinda analogical to Feynman paths and homotopy. I don't know how allowing curved surfaces affects the provability of five platonic solids, interesting question and maybe that's been already answered in fully satisfactory way, maybe not. Dunno.

[@salvatoreshiggerino6810]

What would a post-Turing machine even do? Can we even begin to imagine it?

[@Madsy9]

Maybe hypercomputation would interest you :) en.wikipedia.org/wiki/Hypercomputation

[@mihai5085]

Finally i think i get it !!! daaaaaam it feels good

[@MrCmon113]

Russels' paradox is about a set of axioms leading to a CONTRADICTION, not it being incomplete. The question whether the barber shaves himself is not undecidable, but both options are clearly wrong.

[@ITR]

What about an extra output saying "Dependable on this output"?

[@TechyBen]

So this is why it took so long to find the shell shock bug! :D

[@SSJHF]

Can anyone link me to the Yacc compiler video?

[@Disthron]

So, I saw Jago's H+ video and I have to say I didn't understand how his example explained anything. Other than it's possible to break something if you put your mind to it.

[@desmondbrown5508]

If the innate issue of the halting problem is that it doesn't solve the "not" problems, then my immediate question is: Is there a way to transform all "not" problems into not "not" problems. In otherwords can the problems be rephrased so that they are not "not" problems anymore.

[@AndreAmorim-AA]

Is it possible that undecidability problem is responsible for 2010 flash crash ?

[@DustinRodriguez1_0]

+Andre Amorim It's not impossible, but it is unlikely. Flash crashes most often happen for very boring reasons - usually the company responsible for the trading software is a typical company and puts decision-making power in the hands of management and permits them to override software engineers. That leads to them using unsafe development practices that eventually result in catastrophe. See the Knight Capital crash for an example of that. They pretended that the management could make better decisions than engineers that would produce a safe, reliable system and it resulted in their total destruction. Another problem that can cause flash crashes is unanticipated interaction between two automated systems. That comes down more to chaos theory and our inability to predict systems interacting in nonlinear ways than strict undecidadbility.

[@juanherrera9521]

These undecidable paradoxes often happens with compilers that have type inference, the quickest workaround is to specify the type manually 😅

[@garetclaborn1399]

Regarding undecidability in web programming at scale, similar issues come up frequently. One example you can think of is event-driven code in javascript. It is not uncommon to have a polling function which calls itself again after a given timeout. This function could end if some event occurs and launch another function. These may, and often do, launch programs on the servers a la AJAX. Not only do we not know if the program will halt, we do not know if another program will start.

[@garetclaborn1399]

+listenwhatisayoh hi as mentioned im drawing similarities not contradictions. recursive algorithms like those in this video terminate conditionally but it is unknown whether that codepath will be taken. similarly, we may spawn processes that could halt but never do because of the uncertainty of user interaction. just like we often prefer to use algorithms with constraints on runtime to ration resources, based on things like complexity class and halting prediction, we use similar priorities deciding how chains of processes should interact

[@garetclaborn1399]

i would agree these are distinct scenarios from each other but i fail to see how the code path issue is any different in terms of algorithm usage and selection. i think the key thing is that i'm importing the undecidablity from user timing rather than input chronological example: 1. user A spawns process P 2. P loops until A triggers some condition(s) 3. A does nothing 4. system process S scans processes to determine looping, determines P as looping 5. A triggers halting conditions 6. S will catch this on a second pass at step 4, we cannot accurately determine whether or not step 5 or 6 will ever happen and may only presume a status of looping if it's currently looping, with no predictive power

[@EwanMarshall]

Also it is not uncommon to have functions that generate a function... Generally in web work, the tasks they are being used for, undecidablity problems in general and the halting problem specifically isn't an issue, but it isn't impossible to end up there.

[@MrCrashDavi]

+

[@JumpingMonkeysGR]

A recent paper proves that the halting problem is solvable in quantum computing, right?

[@FishKungfu]

I hope I pass my Turing Test tomorrow!

[@tylerpowers123]

I really shouldn't have had to search for parts 2 and 3 of this series. You didn't link to 2 from one or 3 from 2, but did link from 3 to 2 and 2 to 1. Are you trying to get people to watch them in reverse?

[@chaostrottel_hdaufdutube8144]

Couldn’t one write a program “h++” that can tell you if a program will terminate, loop forever or that the question is decidable, or would such a theocratical program break as well?

[@LittlePeng9]

6:49 Okay then, I'll define something self-referential - it will be a string of numbers, starting with 1, which has a property, that if we remove the first of them and then divide every other by two, we will get the same string of numbers. This is a self-referential definition, which leads to no problems at all, because it just defines the string 1, 2, 4, 8, 16,...

[@softwarelivre2389]

But where is the *not* in this problem?

There are many more types of programs that analyse or change other programs: antivirus, IDE warnings, npm audit fix, …

[@jimman10000]

here is a paradox, how big do i make my data base so it never need to be rewritten? the answer may surprise you. a=a+1

[@judgeomega]

One of the big problems with paradoxes which is easily resolved is the issue of forcing the paradox into a boolean true/false. A third response is needed for such cases, 'error'. I have created a word for just such a specific error, entrodox.

[@markmcarthur5090]

The one thing I still don't get is why you're running the question of "Can h+ compute h+?" through h+. Isn't h+ an inferior machine to h, because h+ has these random bits added on when h was specifically designed to answer any problem? However, I think it still works because running "Can h+ solve h+?" through h will still create a paradox as h+ creates paradoxes when computing stuff, including when computing itself. Just wondering if I am understanding this correctly.

[@TechyBen]

I agree it's hard to visualise, this video finally put it together for me. The random bits don't help solve the problem, they show the problem continues to exist even if we "pretend" we solved it. "H" is "we have a computer that gives the complete answers", but then if we ask it "do you have a complete answer including yourself" it says "no". So it cannot be able to compute all things. :)

[@murphy54000]

TechyBen "h" specifically, returns true or false to the inquiry, "Given program P, and input I, will this reach a halt state?" Would it not return true, given itself as input? That would be the only logical possibility.

[@TechyBen]

I'm not sure. But either answer puts it in a state that we can confirm breaks the premise.

[@softwarelivre2389]

The thing is that you when feed H+ into H+, you'll feed H+ into H, and then H will give an answer that is incorrect. My theory is that H will just never halt, thus never giving an answer.

[@weewilly2007]

wind in the lowill's

[@quenchize]

You encounter this problem in real world examples all the time with unit tests. And ipso facto it is a problem for everyone that is affected by safety critical systems like cars and aeroplanes.

[@zubariakhan2696]

he is mixing propositions and axioms. A consistent set of axioms is incomplete according to Godel instead of propositions.

[@lievenvv]

Sadly, it is impossible to have a program that always finds all bugs in any code you write.

[@PINGPONGROCKSBRAH]

Let's say we exclude programs that induce a "who shaves the barber" paradox. Will there still be other programs whose halting is undecidable?

[@atomheartother]

If you can determine which programs cause a paradox, then you've solved the halting problem, so your question implies a paradox.

[@PINGPONGROCKSBRAH]

atomheartother Ahhh, I see. So the problem is that it is very difficult to tell which programs contain this kind of paradox?

[@DisRes]

+PINGPONGROCKSBRAH It's undecidable to tell which programs contain a paradox. :)

[@sugarfrosted2005]

+PINGPONGROCKSBRAH There is something called the index theorem. Basically you can't select just the programs with a given non-trivial property. Being able to do so would always result in you being able to decide the halting set. The two exceptions to this are all the programs and no programs (trivial index sets).

[@PINGPONGROCKSBRAH]

sugarfrosted Interesting! Thanks for the info.

[@rkpetry]

Classic answers for The Barber Shaves Nonshavers: 1. The Barber is a beardless male (or female barber-ess); 2. The Barber is always too-busy to shave everyone promptly; 3. The Barber leaves a hair (Heisenberg Uncertainty), hare (Zeno paradox), heir; 4. Chin to the shaver, Does he or doesn't he-"Only [his] hairdresser knows for sure."

[@jamez6398]

Oh cool...

[@mightyNosewings]

Prof. Brailsford is confusing "undecidability' with "axiomatic independence." The parallel postulate is axiomatically independent of the first four postulates of Euclidean geometry. It is not undecidable, because it is not a decision problem. Also, most computer programmers use computer programs that analyze other computer programs every day. They're called type checkers.

[@Vulcapyro]

"Undecidable" and "independent" are _synonyms._ This is not the same as when considering decision problems.

[@mightyNosewings]

I've certainly never heard "undecidable" used as a synonym for "axiomatically independent" before. In any case, Prof. Brailsford calls the halting problem "undecidable," apparently in the same sense. But the halting problem isn't "axiomatically independent" -- it is a decision problem with no answer.

[@Vulcapyro]

mightyNosewings It's actually pretty common. Being in CS and having a math background I fully agree that it's confusing to have the same term in two closely related fields. I'm not going to say he never made a mistake in confusing them, but along with the above, the halting problem is still fairly well related to undecidability in decision theory as well. It's extra confusing this way.

[@lievenvv]

Sadly, it is impossible to have a program that always finds all bugs in any code you write.

[@mightyNosewings]

@@lievenvv Not true -- as long as you're willing to write in a language that isn't Turing-complete (and there are no bugs in your specifications).

[@Dextromethasone]

Ok, I'm sure this has been posited before but I'm too lazy to look it up, but why can't the barber visit the neighbouring village and get that barber to shave him, then return the favour when the other barber visits him? Likewise, can a pair of H+ machines not check each other?

[@jazzpi]

If he went to a different town to get shaved, he still wouldn't shave himself. So he'd have to shave himself, in which case he mustn't shave himself.

[@jazzpi]

Scott Wilson The rule is that the barber shaves all men who do not shave themselves. Not all men who aren't shaven... And still, you'd extend the given rules by adding the neighbouring village.

[@tefazDK]

Is it just coincidence that you chose to talk about this now that "The Imitation Game" is coming out?

[@johnvonhorn2942]

Does Yak output, "Yakety, Yak - Don't talk back!" when warning you that this bad boy might get out of hand?

[@reblogo]

Nice try, but it's Yacc

[@zwz.zdenek]

The barber thing is not a paradox, it's a contradiction. It's like saying that X=X^2, trying it for zero and 1 and thinking it's good. The real-life barber makes an implied exception to the rule allowing him to shave or not at will. After all, law makers don't have to abide by the law.

[@DanielPage]

zwz • zdenek The reason why it is called a paradox is because if you consider if it is or it isn't (both), you lead to contradictory results. That's what a paradox is. Liar's Paradox is very similar to the barber's paradox if it is hard to grasp.

[@essellar]

+zwz • zdenek The way the problem is usually stated is that the law in question specifies that all men must be clean-shaven, all men who can shave themselves *must* shave themselves, and that the barber may *only* shave those men who cannot shave themselves. And there is a rather severe penalty attached (beheading, as I recall). (Apparently the social problem being solved by the law is some pervasive combination of slovenliness and laziness.) In that form, if the barber is a man and is capable of shaving himself he must do so, but he is prohibited from shaving himself because he would be shaving somebody who can shave himself.

[@lowmax4431]

Damn don't jump into this video without watching the first two parts. lol

[@unvergebeneid]

I wouldn't trust a computer scientist so uninterested in their own field that they don't even care about such fundamental problems. Not even with maintaining a website.

[@owenmcgrath1127]

ERROR: this website could not be loaded because your browser does not support the latest javascript uncertainty plugin.

[@jazzpi]

If you're a computer *scientist* and are maintaining a website, I think you did something wrong. I'd trust an engineer to build a car for me even if he wasn't interested in Special Relativity.

[@unvergebeneid]

xXjazzpiXx I think that totally depends on the website.

[@unvergebeneid]

Celrador Indeed, but independent of the language, it's not like the majority of university-level computer scientists anywhere are actually doing anything resembling science later on.

[@Celrador]

Penny Lane Well... in some sense. They are rather applying it, than making use of the scientific method. In that sense a plumber is also doing science. And I like that interpretation of it, to be honest. ;) Edit: I might also add, that a computer scientist, no matter what field he is working in (research or on practical application) still has the basic education to perform either task. Which is what I quite like about certain branches of study. (like computer science, or neurology) It keeps the practical applications way further up-to-date to the latest technological developments in the labs.

[@kujmous]

On Error Resume Next -- oy

[@DarthStuticus]

What if the barber doesn't live in the village?

[@bandie9101]

the concept of 'not' is an illusion.

[@DanDart]

Disappointed that this video was sponsored by Microsoft

[@flyguille]

who shaves the barber?, nobody, he just does not shave.& DOT!.

[@johnfrancisdoe1563]

flyguille That violates the rule. If he doesn't shave himself, he must be shaved by the barber. The crazy rule does not allow unshaven men.

[@Kram1032]

Let's just use Universes then. Universe 0 contains everything small enough to not be a universe Universe 1 contains everything of the same size of Universe 0 Universe 2 contains everything of the same size of Universe 1... That way you get a hierarchy of sets (or categories or what have you) and avoid such self-referential paradoxes. You may only talk about "objects smaller than the n-th universe" for a perspective of the n-th universe. Such universes never contain themselves.

[@Vulcapyro]

"Let's just use Universes", doesn't define universes.

[@Vulcapyro]

Kram1032 Dude, a Universe set can be any set, that was my point. You didn't describe anything; you didn't even specify what the criteria for your universe is, so you can't even begin to talk about "everything small enough to not be a universe". There are a bunch of problems with what you're talking about.

[@lamudri]

The NBG (en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory) and MK (en.wikipedia.org/wiki/Morse%E2%80%93Kelley_set_theory) set theories do this, essentially, though they only have 2 “universes” (sets & proper classes). Obviously, infinite levels of classes would require infinite axioms, something which NBG cleverly avoids. I've been toying with the idea of infinite levels of classes, an instance of each of which can hold classes from any level strictly below. This seems necessary for discussing proper classes whilst using a language formalisation that relies on a set theory. Another fun alternative is positive set theory (en.wikipedia.org/wiki/Positive_set_theory), which takes away not. I'm not sure how practical it is, but it's as strong as MK.

[@lamudri]

I've got to say, I love the idea of a nightly build of a book! I don't have time to read it now, but I'll try to remember.

[@lamudri]

Where did Kram1032's comments go?

[@andy16005343]

mmhm. yeah. mmhm. I know some of these words. oh, yeah yeah yeah

[@cherrysclips5214]

One of my pet peeves is when a brit says "not" as if its universally correct. Even though its not. Not to mention they say not even when they should say zero. Because why have "zero" if you have "not"

[@thebigmacd]

The word is "naught" (or "nought"), and is a synonym of "zero". It is not "not", which is a negation.

[@anothergol]

I enjoy listening to those stories, however it reminds me of school. I've been programming for 20-25 years, and yet everything that's being said is like what was said at school, it's totally unrelated to practice & feels like it's describing another job. More precisely, it reminds me of that "pseudocode" that schools used to (& maybe still?) teach you to write. In practice, no one ever writes "pseudocode", never did, never met anyone who does. But if this is philosophy & not programming, then ok.

[@Vulcapyro]

It isn't programming, it's an area of theoretical computer science. The world of computers is not just programming. And what the heck pretty much everyone writes pseudocode at one time or another. I would not believe you if you were to say that every time you described the workings of a program, you wrote the code out verbatim.

[@iabervon]

This is all actually very important for programming language design, compiler implementation, program verification, and that sort of thing. Say, for example, that you're writing a system for routing packets in your kernel, which will accept rules from userspace and decide what to do with each packet based on those rules (perhaps as a firewall, perhaps a NAT router, etc.). You want userspace to provide the rules, but you don't want the rules to get the kernel into an infinite loop trying to handle a packet. So you have a validation pass that only lets userspace load rules that are going to halt. Oh, and you want to ensure that the validation pass doesn't go on forever, either. Is this possible? Actually, yes (and the Linux kernel has it). The key is that the rule-making language (BPF) is less powerful than a Turing machine. The theory here is directly applicable to making the rule language as useful as possible for the things people want to do while still being possible to analyze. On the other side, if you've wondered why your compiler says "This variable may be used uninitialized" instead of being able to say for sure one way or the other, it's because no compiler can possibly know for sure about every program, so it has to do one of: reject valid programs, accept invalid programs, or give a wishy-washy warning about some programs.

[@anothergol]

Vulcapyro I do, and I don't find pseudocode easier to lay down ideas, it's just another normalized (& useless) language that you have to remember, I don't see how that makes it easier. It doesn't mean you write perfect code immediately, the code still evolves while it's being written.

[@anothergol]

iabervon I don't see where a compiler needs all this paradox/recursivity thing. Compilers don't need to bother about that, and they don't - a deadlock is the programmer's fault. Actually, talking about deadlocks, this is where programming can get very complex and may require pseudocode (even though I'd rather say properly documented code, and code that fully works in your head first): multithreaded programming. It's the concept of things happening "at the same time", in parallel, that's a real challenge & a source of problems in practice. That would deserve a rhetorical debate. Lock-free multithreaded programming, if a new programmer had to delve into this, I probably wouldn't go straight to practical examples, even though the problem is both rhethorical (concept of things in parallel) & practical (what parallel even means, and which CPU operations are guaranteed to be atomic).

[@lamudri]

anothergol The compiler needs to terminate, even if its outputted program doesn't. Scala and C++ are examples of languages with Turing-complete compile-time features (probably a bad thing). Idris avoids this by only allowing provably total functions at compile time.

[@vipermagi5499]

I have a non-relevant problem with the "Barber Paradox." The barber is a position that is filled by a man, the man who is the barber can shave himself when he is not filling his official role as 'The Barber.' Just as everyone else in town can shave themselves. It doesn't actually change anything your saying, it just bothered me.

[@someguyontheinternet2521]

the barber can shave himself if he looks in the mirror because tecinaclly his mirror image is shaving him :)

[@Ureallydontknow]

An entire video without typesetting. I am disappoint. 😞

[@Teck_1015]

So what about paradoxes/undecidabilities that aren't self-referential? i.e.: The following statement is true. The previous statement is false.

[@lucinos19]

they are obviously self-referential. They are statements about statements.

[@mightyNosewings]

That paradox is indirectly self-referential.

[@robly17]

It is self-referential though. A refers to B, and B refers to A. Therefore, indirectly, A refers to itself. This applies to any number of steps, such as A refers to B refers to C refers to A.

[@Teck_1015]

More self-referential would be to say: "This statement is false", the statement referring to itself, unlike my previous comment where a statement refers to another statement is similar to a program making programs. Regardless, you all failed to answer the point of my comment, the question of the case in which the paradox is NOT self-referential, what occurs in a computer program in that case?

[@Vulcapyro]

Wyatt G That isn't "more" self-referential, it's just that if you follow the dots as a process one takes more steps. It doesn't mean anything. It might be similar to a program outputting a program, but then you didn't actually give an example of what you wanted to illustrate. Can you formalize the idea of a paradox that in no way has a statement refer to itself? It isn't really something you can answer if you can't even describe it.

[@RanEncounter]

The barber analogy is poor as the barber can and is allowed to shave himself. This is not the case in the original paradox.