What is the Entscheidungsproblem and why did Alan Turing & Alonzo church determine it to be impossible?
Most broad description I’ve got is “a challenge to create an algorithm that accepted formal language input, a logical statement in that language, and answered whether or not the statement expression was universally true or false for the language,” which I still don’t understand.
Thanks!
In: Mathematics
So the question is, “I wrote a program and you wrote a program, do they do exactly the same thing?” In the discussion you may read they use term “lamda calculus (function).” This means in English, a program.
A computer can’t determine that in most cases. Which is sort of surprising.
EDIT: why can’t you? Because you can’t anticipate an infinite variety of inputs. So you can do a truth table which has limited number of inputs. Just not all programs.
A related concept is a computer can’t determine if a program will run to completion without errors. A computer can’t calculate that by shortcut, you have to run the program and find out.
Latest Answers