Note that the halting problem restricted to the finite memory of our computers is actually decidable: 1) The state is 2) When we reach the same state by executing -> we have an infinite loop; 3) If we don't reach the same state, we will run out of states due to limited memory in a finite number of steps -> we don't have an infinite loop.
I feel that the Halting Problem is also why Windows gives you an option to wait when a program is "not responding". If a program doesn't communicate with Windows, it cannot tell if it's doing a lot/heavy work or it will never actually halt.
I mean considering space complexity (program will take up memory) it will halt but indirectly because it will be shutdown by the OS low level functionality because it is taking too RAM/Memory. But yeah you can make infinite loops and other functions that have no defined end and thereby it would not halt. But in the latter case looping is considered a rejection and is classified recursively enumerable language.
1. Accepts all java codes: Consider the compiling of Java down to bytecode and so on generates specific binary instructions. We know this language is turing decidable (a CFG generating particular string). 2. Rejects any inputs that cause infinite loops: Any input user gives to our program are we able to can it accept or reject in finite amount of computational steps? The halting problems says no it cannot be decided whether to accept or reject (halt) on input therefore runs the risk of looping. Therefore not turing decidable Can a machine exists as a turing decidable (1.) and non-turing decidable (2.) ----> Nope!
God damnit, this is not what I need at 5am🤯 I am not even a student of computer science.. 🤒Does it mean that due to the fact that codes have limitations, and computing has it also, we cannot solve everything by computers? Or does it that there will always be a new problem that cannot be solved? Or does it mean that we cannot tell the exact correct answer unless we run the test? WHAT IS THE FCKING HALT PROBLEM???😬😩😵
can u pls give answer for this question "Prepare a subroutine to move a TM head from its current position to the right, skipping over all 0’s until reaching a 1 or a blank. If the current position does not hold 0, then the TM should halt. You may assume that there are no tape symbol other than 0,1 and B(blank). Then , use this subroutine to design to TM that accepts all strings of 0’s and 1’s that do not have two 1’s in a row"
Note that the halting problem restricted to the finite memory of our computers is actually decidable:
1) The state is
2) When we reach the same state by executing -> we have an infinite loop;
3) If we don't reach the same state, we will run out of states due to limited memory in a finite number of steps -> we don't have an infinite loop.
I feel that the Halting Problem is also why Windows gives you an option to wait when a program is "not responding". If a program doesn't communicate with Windows, it cannot tell if it's doing a lot/heavy work or it will never actually halt.
I've wondered the same thing. But Windows sucks with all the bloatwares.
I mean considering space complexity (program will take up memory) it will halt but indirectly because it will be shutdown by the OS low level functionality because it is taking too RAM/Memory. But yeah you can make infinite loops and other functions that have no defined end and thereby it would not halt. But in the latter case looping is considered a rejection and is classified recursively enumerable language.
Shtup
true, you are right.
Thanks, Neso Academy, I like very much all the sequence and organization of your materials.
Amazing how you have connected it with the first video!
what the ... did you just repeat the statement in every way around without any real explanation?
exactly
Computerphile did a very good video on this topic
Boi I understood it.
lol yes
Sir, I Bow-down to your Work. Thank You So Much, sir!
Thanks Neso Academy
A Halting Problem is a PARADOX ! " No Algorithm Can Solve Halting Problem "
1. Accepts all java codes: Consider the compiling of Java down to bytecode and so on generates specific binary instructions. We know this language is turing decidable (a CFG generating particular string).
2. Rejects any inputs that cause infinite loops: Any input user gives to our program are we able to can it accept or reject in finite amount of computational steps? The halting problems says no it cannot be decided whether to accept or reject (halt) on input therefore runs the risk of looping. Therefore not turing decidable
Can a machine exists as a turing decidable (1.) and non-turing decidable (2.) ----> Nope!
thanks for such a pure explination
Thank you for teaching ....
Thanks
God damnit, this is not what I need at 5am🤯 I am not even a student of computer science.. 🤒Does it mean that due to the fact that codes have limitations, and computing has it also, we cannot solve everything by computers? Or does it that there will always be a new problem that cannot be solved? Or does it mean that we cannot tell the exact correct answer unless we run the test? WHAT IS THE FCKING HALT PROBLEM???😬😩😵
A better explanation can be found in the video made by Computerphile - Turing & The Halting Problem
When infinite loops are the problem why not call it Looping problem rather than a halting problem
Because halt means not looping (forever). Its still correct
can u pls give answer for this question "Prepare a subroutine to move a TM head from its current position to the right, skipping over all 0’s until reaching a 1 or a blank. If the current position does not hold 0, then the TM should halt. You may assume that there are no tape symbol other than 0,1 and B(blank). Then , use this subroutine to design to TM that accepts all strings of 0’s and 1’s that do not have two 1’s in a row"
Thankyou sir
The explanation that you're missing is in the next lesson.
But can you be specific when you say "Given a Program" ?
1 sentence, 7 minutes
sound is very low
please increase the volume while making the lecture ,your voice is somewhat in low
lol
#Excelent!
le my ass trying to find the four horsemen in the comments section
sir,could you explain the construction of turing machine for the string (0,1)*011?? expecting an expeditious reply
@@real-investment-banker do you have more examples of turing machine ? if you do please share . thanks
chandra singh kahan gaya ab dekh le bhai apna answer
Pata nahi bhai kaha gaya
@@tatebrother bhai paper to sab ke ho gaye ab kyon padh rahe ho?
@@daman666100 sab ke nahi hue श्याम!! VTU bangalore ATC on 7th
hi
मेरा दिमाग खराब हो रहा है बीसी
Last me padhai karte hai to bhai normal hai ye. Sabke saath hota hai 😂
stop repeating one line thousand times, just to increase video length -_-