32 ms·

Church-Turing Thesis Cannot Possibly Be True [video]

174 points by espeed 8y ago

olliej 8y ago
Are there Paper/slides anywhere? I shall repeat my complaint about AV only material on HN: not everyone (wants to/can/has time to) watch and listen to 10 minutes of reading spread out to 50 minutes. It continues to frustrate me.
- gabrielhn 8y ago
  Listen at 2x speed and skip ahead?
  - syrrim 8y ago
    >listen at 2x speed I'm trying 1.5x, but then when he is speaking it is too fast >skip ahead I skipped the introduction, but the standstill periods are too short, and you have no way of knowing when something interesting will happen, so skipping ahead entails missing things. This is where a copy of the slides is particularly useful: you can identify those slides you don't comprehend, or of particular interest, and sit through the speaking just for these portions.
    - olliej 8y ago
      Listening to things fast is a skill - you can do it but it requires practice. If you know any blind/vision impaired people who use screen readers you should ask them to use speaker for a bit while they’re browsing/navigating etc. It is absolutely incredible how fast some of them have the audio going at. (It also makes any pausing or lag in your application excrutiating. It turns out 10ms being “noticeable” is more a factor of how you interact with an application.
      - mrob 8y ago
        They've practiced with their specific text-to-speech program. The more familiar you are with a voice the faster you can understand it. The skill won't completely transfer to different speakers.
        olliej 8y ago
        For their standard reading speed that true (but it’s still an amazing thing to hear, and I think more devs should communicate with blind people just so they can grasp the sort of latencies involved). I would expect that the skill does translate to them being able to understand arbitrary speakers sped up more than a regular person could manage. I’d be curious if any HN readers using screen readers could confirm/tell me I’m talking nonsense :)
        antt 8y ago
        >I would expect that the skill does translate to them being able to understand arbitrary speakers sped up more than a regular person could manage. I’d be curious if any HN readers using screen readers could confirm/tell me I’m talking nonsense :) I use a text to speech program at ~850wpm and I also watch lectures sped up to x4 regular speed. So yes, it does generalize.
        gugagore 8y ago
        I think it may also be the case that (old-school, non-concatenated but generated) synthesized speech, with practice, is more intelligible at higher speeds than natural speech. The sounds are more distinct and consistent.
        olliej 8y ago
        The speech synthesis for screen readers is heavily tailored for that job (I remember the emphasis put on the new voiceover voices on Mac many years ago, and they apparently were noticeably superior to people who used them as screen readers at the high speed settings)
  - olliej 8y ago
    Doesn’t work for people who can’t listen. Doesn’t work for people who can’t see. Doesn’t work for people in environments where the above two are essentially true. 25 minutes is still longer than 10 minutes (transcript, slides would be even shorter although less informative), and I was being conservative about reading speed.
    - avodonosov 8y ago
      People who can't see whould be unable to read as well
      - RugnirViking 8y ago
        however, if it were written in text, they can read by using a screen reader, which is very established techology by now. This is not (as) available for a video if at least some component of the lecture requires being able to see
  - drb91 8y ago
    How do you scan forward for the interesting stuff? How do you search for a quote a friend sent you? What if you’re deaf? Or blind and can’t read the slides? Just transcribe it and include the slides! If you can afford the speaker you can afford to make it accessible.
- smhost 8y ago
  here are the captions printed out: https://txt.fyi/+/933087e8/ https://txt.fyi/+/933087e8/
- nabla9 8y ago
  I think these are relevant: http://web.eecs.umich.edu/~gurevich/Opera/209a.pdf http://web.eecs.umich.edu/~gurevich/Opera/209a.pdf http://web.eecs.umich.edu/~gurevich/Opera/210.pdf http://web.eecs.umich.edu/~gurevich/Opera/210.pdf
  - olliej 8y ago
    Can we replace the article link with these? :)
- azhenley 8y ago
  Would be cool if a web app existed that could take a video and produce not only a transcript but also a series of intelligently selected images from the video, basically producing a full document that stands alone.
  - olliej 8y ago
    I feel like transcribe + pull out slides would be a generally useful thing for conferences. Even a specialized piece of software that has the original slides and just records when slide changes happen and inserts the appropriate slide into the transcription. I’m convinced this would help conference videos that frequently do just have points where just the slide is shown (WWDC videos have this a lot - where frequently the speaker isn’t being shown). There should clearly be a standardized video codec for exactly this ;)
  - Rainymood 8y ago
    Pay me and I'll do it for you. If there is enough demand I'll look for ways to automate it.
- marssaxman 8y ago
  Seriously! I don't understand why people waste so much effort presenting information in such a high-overhead, low-bandwidth format. Wouldn't it be easier to just post the notes and skip all the AV folderol?
  - titzer 8y ago
    An echo of the Youtube effect; it's less work for the producer. Just turn on the cameras and start babbling, no editing, annotating, summarizing, or other further work required. (tbc not faulting the speaker here).
- dragonwriter 8y ago
  Yeah, speed aside, audio-video is much better for conveying emotion than information.
- hinkley 8y ago
  My coworkers are currently on this same bent and it drives me mad. They’d rather make a video than write an architecture document. And what happens when someone has a question or complaint about the middle of the video? How do you come back in a week to review the second to last part? Learn to take screenshots and do some light typesetting. Spell it out for people (in my case, they are literally getting paid to do the work).
TimTheTinker 8y ago
Overview pasted here: ———— The thesis asserts this: If an algorithm A computes a partial function f from natural numbers to natural numbers then f is partially recursive, i.e., the graph of f is recursively enumerable. The thesis has been formulated in 1930s. The only algorithms at the time were sequential algorithms. Sequential algorithms were axiomatized in 2000. This axiomatization was used in 2008 to prove the thesis for sequential algorithms, i.e., for the case where A ranges over sequential algorithms. These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learning algorithms, etc. The question whether the thesis is true in full generality is actively discussed from 1960s. We argue that, in full generality, the thesis cannot possibly be true.
- berti 8y ago
  > We argue that, in full generality, the thesis cannot possibly be true. If you could post a text summary of this part, we'd be very grateful.
  - TimTheTinker 8y ago
    I don't have the time to put that together, but here's a somewhat cleaned up (i.e. times and some newlines removed) paste of the closed captions. This may be helpful if you're good at scanning a lot of text. https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380fdb109c https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380f...
- olliej 8y ago
  I’m still unclear on whether probabilistic algorithms are “algorithms” in the strict sense - in that definition an algorithm should have deterministic behavior, which a probabilistic method does not have. But let’s say your “random” is a deterministic prng- does that then make the PA a deterministic algorithm? Basically the distinction can be best illustrated with bozo/bogo sort. The definition many people use is: 1. Randomly shuffle the input 2. See if it is sorted, if not go to 1. The problem, as explained to me by an algorithms lecturer a long time ago, is that the algorithm is not guaranteed to finish, and more over the same input may or may not result in it finishing on different runs. Per that lecturer a “correct” bozo sort is 1. Generate a list of every permutation of the input 2. Iterate the list until you find a sorted entry and return that. It has computable best case, worst case, and average case (all terrible). It is guaranteed that the same input will always produce the same output (terminate vs not terminate). Obviously you could optimize this if you had an algorithm that could shuffle an input such that you were guaranteed that if you shuffled it’s own output you were guaranteed to produce every ordering of the original input. Then you would get closer to: shuffle; check; repeat. But still note that there is no random involved :)
mwilcox 8y ago
What about the Church–Turing–Deutsch principle? https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93...
- tlb 8y ago
  That one's pretty aspirational. At present, we have no idea how to build a supercomputer that simulates exactly even a cubic nanometer-femtosecond of space. It's tempting to believe that we might someday figure out that physics is digital, but there is no workable theory for how.
  - kowdermeister 8y ago
    Not sure what your definition of simulation, but there is already one done on a supercomputer: https://www.youtube.com/watch?v=J3xLuZNKhlY https://www.youtube.com/watch?v=J3xLuZNKhlY
    - yorwba 8y ago
      That's a box of ≈21 cubic femtometers and the time resolution is one yoctosecond. The difference between that and a cubic nanometer-femtosecond is more than 25 orders of magnitude. And that's just simulating quantum chromodynamics. Add in the other parts of the Standard Model and scaling the simulation gets even more difficult.
      - kowdermeister 8y ago
        I'm pretty happy we can even simulate a box of ≈21 cubic femtometers :) Maybe they should turn RTX on.
scythe 8y ago
The talk begins: ANNOUNCER: So it's my distinct pleasure, and privilege, to host Yuri for a talk on a topic I have discussed with him since I was even a student: models of computation. And through the years, we have interacted in various ways, on both fundamentals of models of computation and then abstract state machine applications, and at this point, it's also probably the last talk that Yuri will give at this institution, as he is moving to Michigan next week. But I have no doubts that there will be many opportunities to interact with Yuri in the future. I hear that there's a birthday party coming up in a couple of years, and it was always a pleasure to participate in these events. So, without more adieu, please go ahead. YURI: Thank you very much. It's a pleasure for return for a day. [First slide appears] >My scholarly friend Nachum Dershowitz and I published a long paper >"A natural axiomatization of computability and proof of Church's thesis", Bulletin of Symbolic Logic, 2008 >where we proved Church's thesis for classical algorithms. >Here classical is not the counterpart to quantum as is common in quantum literature. By classical algorithms we mean traditional algorithms from antiquity to Turing's time, also known as sequential algorithms. >The claim that the Church-Turing thesis cannot be true in general is implicit in: >"What is an Algorithm?" SOFSEM 2012, Springer LNCS 7147 (2012) >The main goal of this talk is to clarify things and argue for the claim. YURI: In 2008 Nachum Dershowitz, my very learned scholarly friend and myself, we wrote this paper, we proved Church's thesis, and Turing's thesis, but on very technical-- they are slight differences, it's a technicality -- for classical algorithms. Now what do we mean by classical algorithms? Now quantum people hijack the word "classical" -- it became to mean non-quantum, but our meaning was classical in the sense: algorithms from time immemorial, certainly, until 1950s, 1960s. So, this is the algorithm that Church and Turing had in mind when they put forward their theses. So, another name for these classical algorithms was traditional algorithms, or sequential. I will call them mostly sequential, because the first sort of non-classical, non-traditional algorithms were parallel, and so there was this -- there was traditional or non-sequential. You can generalize, and generalize, then it's not completely obvious why it should be even true. YURI: I had this argument implicitly published years ago, but as you see: [Second slide appears] >There is a a problem with long scholarly papers: it takes time to read them, and there is a tendency to skim. >Peter Shor: The Dershowitz-Gurevich paper says nothing about probabilistic or quantum computation. It does write down a set of axioms about computation, and prove the Church-Turing thesis assuming those axioms. However, we're left with justifying the axioms. Neither probabilistic nor quantum computation is covered by these axioms (they admit this for probabilistic computation, and do not mention quantum computation at all), so it's quite clear to me these axioms are false in the real world, even though the Church-Turing thesis is probably true. >Nov, 22, 2010. https://cstheory.stackexchange.com/questions/what-would-it-mean-to-disprove-church-turing-thesis https://cstheory.stackexchange.com/questions/what-would-it-m... >The great hero of quantum computing has not read the paper. =========================================================== I hope this will help you decide whether or not to make time to watch the video, although I agree it would be helpful to have a complete transcription available.
joe_the_user 8y ago
This seems like really exotic stuff. It's one of those talks that seems to talk about things I know but then immediately jumps to theories and definitions I have never heard of. "Sequential algorithms were axiomatized in 2000" - This "axiomization" was apparently performed by the author of the talk, my Googling says. All links about things talked in this talk just seem to lead to other texts and such by this author. Might not be a good sign but maybe it's just a very hard to grasp realm. Anyway, broadly, the Church-Turing thesis is not a theorem and cannot be proven true or false (so said my professors and Wikidepia). Effectively, it is a definition of computation that has so far been accepted because nothing fundamentally different and more powerful than a Turing machine has been exhibited (there is a theorem that Turing machines, partial recursive functions and the lambda calculus are equivalent - and then there's the jump to "these are really general and I think that about covers it" but still, not a theorem, not provable). My hunch is the author is mixing in "higher-order" logic "version of Church-Turing" into their argument. Which is basically "cheating", switching to an effectively different question without making things clear. However, I simply don't know. This is basically opaque to my mere MA-level maths.
- joe_the_user 8y ago
  OK, yeah, reading more[1] so I think the author is indeed considering things like computation on real numbers where, for example, the value of square root of two can only be approximated by a Turing machine but where ruler-and-compass construction hypothetically can construct this exactly. So if you toss out the idea of computation involving digital computers, you can exhibit something not (exactly) Turing computable. If you have a chaotically behaving dynamic system and call it a computer, then you have something where computation becomes something in the eye of the beholder. I'm not sure what questions this answers but there you are. [1] https://www.researchgate.net/publication/221512843_What_Is_an_Algorithm https://www.researchgate.net/publication/221512843_What_Is_a...
  - perl4ever 8y ago
    "the value of square root of two can only be approximated by a Turing machine but where ruler-and-compass construction hypothetically can construct this exactly." Ruler and compass are made of atoms though. Or, if not atoms, planck units or something.
psiphon3 8y ago
i have new blogger templates on https://www.bloggerfunda.info https://www.bloggerfunda.info
austincheney 8y ago
I am so not a math person. From a math perspective perhaps this is important. From a computer perspective it completely misses the point. This work from Alonzo Church gave us https://en.m.wikipedia.org/wiki/Lambda_calculus https://en.m.wikipedia.org/wiki/Lambda_calculus which in turn provides recursive function abstraction and thus lexical scope. While this model of computation is older than OOP it currently seems to be having a modern renaissance in its influence of language design.
- austincheney 8y ago
  This many downvotes without any explanation is a true Reddit moment.
  - espeed 8y ago
    NB: Better to refrain from saying stuff like "it completely misses the point" unless you are certain you understand the point beyond the level presented.
starpilot 8y ago
I understood all of it.
abdulhaq 8y ago
A Turing machine can compute root 2 but it takes an infinite amount of time to do so. A ruler and compass can do it near instantaneously, but it takes forever to measure it.
- comboy 8y ago
  It also takes an infinitely precise ruler and other tech which at some level of precision is not in any way more trivial than an infinite amount of time. You can compute as many digits as you want, but when trying to measure it, at some point Heisenberg (or Planck to be more precise) will stop you.
rain1 8y ago
This is pretty misleading and click-baity! The formulation they use is quite esoteric and not what people usually think of the term to mean. The Church-Turing Thesis really just states that turing completeness is the strongest type of computational class we can expect to build (finite approximations of) in our universe. And this does seem to be true. I hope the "exciting" title of the talk they chose doesn't cause a lot of people to misunderstand this.
deleted 8y ago
[deleted]
Verdex_3 8y ago
There is a series of talks by Yuri Gurevich on Channel 9 where he talks about algorithms. While I haven't watched this particular video (yet), I did watch the other series a few times (3 videos IIRC). Anyway, in those videos Yuri seems to basically be saying that he doesn't think all algorithms from now to eternity will always be representable with turing machines. Which seems a bit more reasonable than the title here (Church-Turing cannot be true). It's a different way of saying when an old scientist says something is possible he's probably right and if he says something is impossible then he's probably wrong (only inverted ... ie saying church turing will never be irrelevant is hedging your bets against human progress). All that being said, I don't buy what Yuri is selling. Even quantum computing can be simulated with a classical computer (with exponential slowdown), so I'm not seeing what's going to turn out to be more fundamental at least in a theoretical sense. Practically people might not care (yes technically you can simulate that graphics card in lambda calculus, but practically you would never do that and the guys building these things probably don't care about the church turing thesis), but the effective computability definition feels pretty effective. Either way, I'm not going to loose too much sleep over it. At the end of the day I'm more interested in looking for ways to be more effective and I'm not really interested in whether or not what I'm doing fits into the current definition of effective computability.
avodonosov 8y ago
FWIW, Yuri Gurevich is famous for the Abstract State Machines formalism.
avodonosov 8y ago
This talk is Yuri Gurevich's answer to Peter Shor's (famous for Shor's algorithm) comment [1] regarding a previous Gurevich work. In that previous work Dershovich and Gurevich prove the Church-Turing thesis formally, using an axiomatisation of what "algorithm" is, which captures the meaning assumed in Church and Turing times. But Shor complains their axiomatisation does not include probabilistic algoriths, quantum algorithms. In this talk Gurevich argues that in full generality of the term "algorithm" the thesis can not be true. 1 - https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis https://cstheory.stackexchange.com/questions/88/what-would-i...
stevebmark 8y ago
Why would you share this? It's incomprehensible.

174 points by espeed 8y ago

Are there Paper/slides anywhere? I shall repeat my complaint about AV only material on HN: not everyone (wants to/can/has time to) watch and listen to 10 minutes of reading spread out to 50 minutes. It continues to frustrate me.

gabrielhn 8y ago
Listen at 2x speed and skip ahead?
- syrrim 8y ago
  >listen at 2x speed I'm trying 1.5x, but then when he is speaking it is too fast >skip ahead I skipped the introduction, but the standstill periods are too short, and you have no way of knowing when something interesting will happen, so skipping ahead entails missing things. This is where a copy of the slides is particularly useful: you can identify those slides you don't comprehend, or of particular interest, and sit through the speaking just for these portions.
  - olliej 8y ago
    Listening to things fast is a skill - you can do it but it requires practice. If you know any blind/vision impaired people who use screen readers you should ask them to use speaker for a bit while they’re browsing/navigating etc. It is absolutely incredible how fast some of them have the audio going at. (It also makes any pausing or lag in your application excrutiating. It turns out 10ms being “noticeable” is more a factor of how you interact with an application.
    - mrob 8y ago
      They've practiced with their specific text-to-speech program. The more familiar you are with a voice the faster you can understand it. The skill won't completely transfer to different speakers.
      - olliej 8y ago
        For their standard reading speed that true (but it’s still an amazing thing to hear, and I think more devs should communicate with blind people just so they can grasp the sort of latencies involved). I would expect that the skill does translate to them being able to understand arbitrary speakers sped up more than a regular person could manage. I’d be curious if any HN readers using screen readers could confirm/tell me I’m talking nonsense :)
        antt 8y ago
        >I would expect that the skill does translate to them being able to understand arbitrary speakers sped up more than a regular person could manage. I’d be curious if any HN readers using screen readers could confirm/tell me I’m talking nonsense :) I use a text to speech program at ~850wpm and I also watch lectures sped up to x4 regular speed. So yes, it does generalize.
      - gugagore 8y ago
        I think it may also be the case that (old-school, non-concatenated but generated) synthesized speech, with practice, is more intelligible at higher speeds than natural speech. The sounds are more distinct and consistent.
        olliej 8y ago
        The speech synthesis for screen readers is heavily tailored for that job (I remember the emphasis put on the new voiceover voices on Mac many years ago, and they apparently were noticeably superior to people who used them as screen readers at the high speed settings)
- olliej 8y ago
  Doesn’t work for people who can’t listen. Doesn’t work for people who can’t see. Doesn’t work for people in environments where the above two are essentially true. 25 minutes is still longer than 10 minutes (transcript, slides would be even shorter although less informative), and I was being conservative about reading speed.
  - avodonosov 8y ago
    People who can't see whould be unable to read as well
    - RugnirViking 8y ago
      however, if it were written in text, they can read by using a screen reader, which is very established techology by now. This is not (as) available for a video if at least some component of the lecture requires being able to see
- drb91 8y ago
  How do you scan forward for the interesting stuff? How do you search for a quote a friend sent you? What if you’re deaf? Or blind and can’t read the slides? Just transcribe it and include the slides! If you can afford the speaker you can afford to make it accessible.
smhost 8y ago
here are the captions printed out: https://txt.fyi/+/933087e8/ https://txt.fyi/+/933087e8/
nabla9 8y ago
I think these are relevant: http://web.eecs.umich.edu/~gurevich/Opera/209a.pdf http://web.eecs.umich.edu/~gurevich/Opera/209a.pdf http://web.eecs.umich.edu/~gurevich/Opera/210.pdf http://web.eecs.umich.edu/~gurevich/Opera/210.pdf
- olliej 8y ago
  Can we replace the article link with these? :)
azhenley 8y ago
Would be cool if a web app existed that could take a video and produce not only a transcript but also a series of intelligently selected images from the video, basically producing a full document that stands alone.
- olliej 8y ago
  I feel like transcribe + pull out slides would be a generally useful thing for conferences. Even a specialized piece of software that has the original slides and just records when slide changes happen and inserts the appropriate slide into the transcription. I’m convinced this would help conference videos that frequently do just have points where just the slide is shown (WWDC videos have this a lot - where frequently the speaker isn’t being shown). There should clearly be a standardized video codec for exactly this ;)
- Rainymood 8y ago
  Pay me and I'll do it for you. If there is enough demand I'll look for ways to automate it.
marssaxman 8y ago
Seriously! I don't understand why people waste so much effort presenting information in such a high-overhead, low-bandwidth format. Wouldn't it be easier to just post the notes and skip all the AV folderol?
- titzer 8y ago
  An echo of the Youtube effect; it's less work for the producer. Just turn on the cameras and start babbling, no editing, annotating, summarizing, or other further work required. (tbc not faulting the speaker here).
dragonwriter 8y ago
Yeah, speed aside, audio-video is much better for conveying emotion than information.
hinkley 8y ago
My coworkers are currently on this same bent and it drives me mad. They’d rather make a video than write an architecture document. And what happens when someone has a question or complaint about the middle of the video? How do you come back in a week to review the second to last part? Learn to take screenshots and do some light typesetting. Spell it out for people (in my case, they are literally getting paid to do the work).

TimTheTinker 8y ago

Overview pasted here: ———— The thesis asserts this: If an algorithm A computes a partial function f from natural numbers to natural numbers then f is partially recursive, i.e., the graph of f is recursively enumerable. The thesis has been formulated in 1930s. The only algorithms at the time were sequential algorithms. Sequential algorithms were axiomatized in 2000. This axiomatization was used in 2008 to prove the thesis for sequential algorithms, i.e., for the case where A ranges over sequential algorithms. These days, in addition to sequential algorithms, there are parallel algorithms, distributed algorithms, probabilistic algorithms, quantum algorithms, learning algorithms, etc. The question whether the thesis is true in full generality is actively discussed from 1960s. We argue that, in full generality, the thesis cannot possibly be true.

berti 8y ago
> We argue that, in full generality, the thesis cannot possibly be true. If you could post a text summary of this part, we'd be very grateful.
- TimTheTinker 8y ago
  I don't have the time to put that together, but here's a somewhat cleaned up (i.e. times and some newlines removed) paste of the closed captions. This may be helpful if you're good at scanning a lot of text. https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380fdb109c https://gist.github.com/RoyTinker/1a7e27cb4dbd468b45586a380f...
olliej 8y ago
I’m still unclear on whether probabilistic algorithms are “algorithms” in the strict sense - in that definition an algorithm should have deterministic behavior, which a probabilistic method does not have. But let’s say your “random” is a deterministic prng- does that then make the PA a deterministic algorithm? Basically the distinction can be best illustrated with bozo/bogo sort. The definition many people use is: 1. Randomly shuffle the input 2. See if it is sorted, if not go to 1. The problem, as explained to me by an algorithms lecturer a long time ago, is that the algorithm is not guaranteed to finish, and more over the same input may or may not result in it finishing on different runs. Per that lecturer a “correct” bozo sort is 1. Generate a list of every permutation of the input 2. Iterate the list until you find a sorted entry and return that. It has computable best case, worst case, and average case (all terrible). It is guaranteed that the same input will always produce the same output (terminate vs not terminate). Obviously you could optimize this if you had an algorithm that could shuffle an input such that you were guaranteed that if you shuffled it’s own output you were guaranteed to produce every ordering of the original input. Then you would get closer to: shuffle; check; repeat. But still note that there is no random involved :)

mwilcox 8y ago

What about the Church–Turing–Deutsch principle? https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93...

tlb 8y ago
That one's pretty aspirational. At present, we have no idea how to build a supercomputer that simulates exactly even a cubic nanometer-femtosecond of space. It's tempting to believe that we might someday figure out that physics is digital, but there is no workable theory for how.
- kowdermeister 8y ago
  Not sure what your definition of simulation, but there is already one done on a supercomputer: https://www.youtube.com/watch?v=J3xLuZNKhlY https://www.youtube.com/watch?v=J3xLuZNKhlY
  - yorwba 8y ago
    That's a box of ≈21 cubic femtometers and the time resolution is one yoctosecond. The difference between that and a cubic nanometer-femtosecond is more than 25 orders of magnitude. And that's just simulating quantum chromodynamics. Add in the other parts of the Standard Model and scaling the simulation gets even more difficult.
    - kowdermeister 8y ago
      I'm pretty happy we can even simulate a box of ≈21 cubic femtometers :) Maybe they should turn RTX on.

scythe 8y ago

The talk begins: ANNOUNCER: So it's my distinct pleasure, and privilege, to host Yuri for a talk on a topic I have discussed with him since I was even a student: models of computation. And through the years, we have interacted in various ways, on both fundamentals of models of computation and then abstract state machine applications, and at this point, it's also probably the last talk that Yuri will give at this institution, as he is moving to Michigan next week. But I have no doubts that there will be many opportunities to interact with Yuri in the future. I hear that there's a birthday party coming up in a couple of years, and it was always a pleasure to participate in these events. So, without more adieu, please go ahead. YURI: Thank you very much. It's a pleasure for return for a day. [First slide appears] >My scholarly friend Nachum Dershowitz and I published a long paper >"A natural axiomatization of computability and proof of Church's thesis", Bulletin of Symbolic Logic, 2008 >where we proved Church's thesis for classical algorithms. >Here classical is not the counterpart to quantum as is common in quantum literature. By classical algorithms we mean traditional algorithms from antiquity to Turing's time, also known as sequential algorithms. >The claim that the Church-Turing thesis cannot be true in general is implicit in: >"What is an Algorithm?" SOFSEM 2012, Springer LNCS 7147 (2012) >The main goal of this talk is to clarify things and argue for the claim. YURI: In 2008 Nachum Dershowitz, my very learned scholarly friend and myself, we wrote this paper, we proved Church's thesis, and Turing's thesis, but on very technical-- they are slight differences, it's a technicality -- for classical algorithms. Now what do we mean by classical algorithms? Now quantum people hijack the word "classical" -- it became to mean non-quantum, but our meaning was classical in the sense: algorithms from time immemorial, certainly, until 1950s, 1960s. So, this is the algorithm that Church and Turing had in mind when they put forward their theses. So, another name for these classical algorithms was traditional algorithms, or sequential. I will call them mostly sequential, because the first sort of non-classical, non-traditional algorithms were parallel, and so there was this -- there was traditional or non-sequential. You can generalize, and generalize, then it's not completely obvious why it should be even true. YURI: I had this argument implicitly published years ago, but as you see: [Second slide appears] >There is a a problem with long scholarly papers: it takes time to read them, and there is a tendency to skim. >Peter Shor: The Dershowitz-Gurevich paper says nothing about probabilistic or quantum computation. It does write down a set of axioms about computation, and prove the Church-Turing thesis assuming those axioms. However, we're left with justifying the axioms. Neither probabilistic nor quantum computation is covered by these axioms (they admit this for probabilistic computation, and do not mention quantum computation at all), so it's quite clear to me these axioms are false in the real world, even though the Church-Turing thesis is probably true. >Nov, 22, 2010. https://cstheory.stackexchange.com/questions/what-would-it-mean-to-disprove-church-turing-thesis https://cstheory.stackexchange.com/questions/what-would-it-m... >The great hero of quantum computing has not read the paper. =========================================================== I hope this will help you decide whether or not to make time to watch the video, although I agree it would be helpful to have a complete transcription available.

joe_the_user 8y ago

This seems like really exotic stuff. It's one of those talks that seems to talk about things I know but then immediately jumps to theories and definitions I have never heard of. "Sequential algorithms were axiomatized in 2000" - This "axiomization" was apparently performed by the author of the talk, my Googling says. All links about things talked in this talk just seem to lead to other texts and such by this author. Might not be a good sign but maybe it's just a very hard to grasp realm. Anyway, broadly, the Church-Turing thesis is not a theorem and cannot be proven true or false (so said my professors and Wikidepia). Effectively, it is a definition of computation that has so far been accepted because nothing fundamentally different and more powerful than a Turing machine has been exhibited (there is a theorem that Turing machines, partial recursive functions and the lambda calculus are equivalent - and then there's the jump to "these are really general and I think that about covers it" but still, not a theorem, not provable). My hunch is the author is mixing in "higher-order" logic "version of Church-Turing" into their argument. Which is basically "cheating", switching to an effectively different question without making things clear. However, I simply don't know. This is basically opaque to my mere MA-level maths.

joe_the_user 8y ago
OK, yeah, reading more[1] so I think the author is indeed considering things like computation on real numbers where, for example, the value of square root of two can only be approximated by a Turing machine but where ruler-and-compass construction hypothetically can construct this exactly. So if you toss out the idea of computation involving digital computers, you can exhibit something not (exactly) Turing computable. If you have a chaotically behaving dynamic system and call it a computer, then you have something where computation becomes something in the eye of the beholder. I'm not sure what questions this answers but there you are. [1] https://www.researchgate.net/publication/221512843_What_Is_an_Algorithm https://www.researchgate.net/publication/221512843_What_Is_a...
- perl4ever 8y ago
  "the value of square root of two can only be approximated by a Turing machine but where ruler-and-compass construction hypothetically can construct this exactly." Ruler and compass are made of atoms though. Or, if not atoms, planck units or something.

psiphon3 8y ago

i have new blogger templates on https://www.bloggerfunda.info https://www.bloggerfunda.info

austincheney 8y ago

I am so not a math person. From a math perspective perhaps this is important. From a computer perspective it completely misses the point. This work from Alonzo Church gave us https://en.m.wikipedia.org/wiki/Lambda_calculus https://en.m.wikipedia.org/wiki/Lambda_calculus which in turn provides recursive function abstraction and thus lexical scope. While this model of computation is older than OOP it currently seems to be having a modern renaissance in its influence of language design.

austincheney 8y ago
This many downvotes without any explanation is a true Reddit moment.
- espeed 8y ago
  NB: Better to refrain from saying stuff like "it completely misses the point" unless you are certain you understand the point beyond the level presented.

starpilot 8y ago

I understood all of it.

abdulhaq 8y ago

A Turing machine can compute root 2 but it takes an infinite amount of time to do so. A ruler and compass can do it near instantaneously, but it takes forever to measure it.

comboy 8y ago
It also takes an infinitely precise ruler and other tech which at some level of precision is not in any way more trivial than an infinite amount of time. You can compute as many digits as you want, but when trying to measure it, at some point Heisenberg (or Planck to be more precise) will stop you.

rain1 8y ago

This is pretty misleading and click-baity! The formulation they use is quite esoteric and not what people usually think of the term to mean. The Church-Turing Thesis really just states that turing completeness is the strongest type of computational class we can expect to build (finite approximations of) in our universe. And this does seem to be true. I hope the "exciting" title of the talk they chose doesn't cause a lot of people to misunderstand this.

deleted 8y ago

[deleted]

Verdex_3 8y ago

There is a series of talks by Yuri Gurevich on Channel 9 where he talks about algorithms. While I haven't watched this particular video (yet), I did watch the other series a few times (3 videos IIRC). Anyway, in those videos Yuri seems to basically be saying that he doesn't think all algorithms from now to eternity will always be representable with turing machines. Which seems a bit more reasonable than the title here (Church-Turing cannot be true). It's a different way of saying when an old scientist says something is possible he's probably right and if he says something is impossible then he's probably wrong (only inverted ... ie saying church turing will never be irrelevant is hedging your bets against human progress). All that being said, I don't buy what Yuri is selling. Even quantum computing can be simulated with a classical computer (with exponential slowdown), so I'm not seeing what's going to turn out to be more fundamental at least in a theoretical sense. Practically people might not care (yes technically you can simulate that graphics card in lambda calculus, but practically you would never do that and the guys building these things probably don't care about the church turing thesis), but the effective computability definition feels pretty effective. Either way, I'm not going to loose too much sleep over it. At the end of the day I'm more interested in looking for ways to be more effective and I'm not really interested in whether or not what I'm doing fits into the current definition of effective computability.

avodonosov 8y ago

FWIW, Yuri Gurevich is famous for the Abstract State Machines formalism.

avodonosov 8y ago

This talk is Yuri Gurevich's answer to Peter Shor's (famous for Shor's algorithm) comment [1] regarding a previous Gurevich work. In that previous work Dershovich and Gurevich prove the Church-Turing thesis formally, using an axiomatisation of what "algorithm" is, which captures the meaning assumed in Church and Turing times. But Shor complains their axiomatisation does not include probabilistic algoriths, quantum algorithms. In this talk Gurevich argues that in full generality of the term "algorithm" the thesis can not be true. 1 - https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis https://cstheory.stackexchange.com/questions/88/what-would-i...

stevebmark 8y ago

Why would you share this? It's incomprehensible.